Link Sub: http://www.spoj.com/PTIT/problems/BCBASEAD/
Người Gửi: Sai
- Problem:
Thay vì thực hiện cộng các số nguyên thập phân một cách nhàm chán, người ta muốn tăng tính hấp dẫn của phép tính này bằng cách biểu diễn lại toán hạng và cả kết quả theo dạng tập hợp cơ sở. Trong cách biểu diễn này, các số nguyên không âm sẽ được biểu diễn như sau:
- Số 0 được biểu diễn là tập rỗng {}
- Số nguyên n>0 sẽ được biểu diễn bởi một tập hợp trong đó chứa tất cả biểu diễn của các số nguyên không âm nhỏ hơn n theo thứ tự tăng dần.
Ví dụ, 4 số đầu tiên sẽ được biểu diễn như sau:
0 => {}
1 => {{}}
2 => {{},{{}}}
3 => {{},{{}},{{},{{}}}}
Với cách biểu diễn này, kích thước của tập hợp (số phần tử trong tập) sẽ chính là giá trị số nguyên cần biểu diễn.
Bạn hãy viết chương trình viết ra kết quả của phép cộng hai số nguyên được biểu diễn ở dạng tập hợp cơ sở như trên.
InputDòng đầu tiên ghi số bộ test, không lớn hơn 1000. Mỗi bộ test gồm 2 dòng, mỗi dòng chứa biểu diễn của một số nguyên không âm. Chỉ bao gồm các ký tự { hoặc } hoặc dấu phẩy (,) . Giả sử tổng của hai số nguyên trong mỗi bộ test đều không lớn hơn 15,
Output
Với mỗi bộ test, in ra màn hình trên một dòng biểu diễn kết quả của phép cộng.
Example:
Với mỗi bộ test, in ra màn hình trên một dòng biểu diễn kết quả của phép cộng.
Input
3
{}
{}
{{}}
{{},{{}}}
{{},{{}},{{},{{}}}}
{{}}
Output:
{}
{{},{{}},{{},{{}}}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}
- Solution:
- Với hai dữ kiện bai đầu là {}=0 và {{}}=1. - Theo quy tắc trên ta có thể tính được: 2, 3, 4,... thành các xâu.
- Vì đề cho tổng không qua 15 nên chỉ cần tính đến số 15 là ok - Khi cộng cơ sở thì chỉ cần tìm chỉ số và cộng chỉ số của các xâu = SUM rồi in ra xâu có chỉ số SUM.