BCBASEAD spoj PTIT - Phép cộng cơ sở

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCBASEAD/

1. Đề bài BCBASEAD spoj

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.

Input

Dò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

Input:
3
{}
{}
{{}}
{{},{{}}}
{{},{{}},{{},{{}}}}
{{}}

Output:
{}
{{},{{}},{{},{{}}}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}

2. Hướng dẫn BCBASEAD spoj PTIT

– Mình không biết bài này chưa chuẩn test hay chưa chuẩn đề nữa, bởi ở cấu trúc test đề nói “hai số nguyên trong mỗi bộ test đều không lớn hơn 15” vậy tức là khả năng lớn nhất output sẽ là 30. tuy nhiên mình thử kiểm tra thì test của PTIT cho output luôn nhỏ hơn 15. với giới hạn tổng hai số nhỏ luôn ko quá 15 thì các bạn có thể tham khảo gợi ý sau:

– tính trước các kết quả, với số 0 thì sẽ là {}, tương tự 5 sẽ là {{},{{}},{{},{{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}} chẳng hạn, v.v….. như vậy chỉ cần duyệt bình thường là được.

3. Code tham khảo BCBASEAD spoj PTIT

const   fi='';
        nmax=1000;
type    data=longint;
var
        f:text;
        A:array[0..35] of ansistring;
        n:data;
        s1,s2:ansistring;

procedure docfile;
var     i,j,test,t1,t2:data;
begin
        assign(f,fi); reset(f);
        readln(f,test);
        for i:=1 to test do
                begin
                        readln(f,s1);
                        readln(f,s2);
                        for j:=0 to 15 do
                                if s1=a[j] then
                                        begin
                                                t1:=j;
                                                break;
                                        end;
                        for j:=0 to 15 do
                                if s2=a[j] then
                                        begin
                                                t2:=j;
                                                break;
                                        end;
                        writeln(a[t1+t2]);
                end;
        close(f);
end;

procedure tinh;
var     i,j:data;
begin
        A[0]:='{';
        A[1]:='{{}';
        for i:=2 to 15 do
                a[i]:=a[i-1]+','+A[i-1]+'}';
        for i:=0 to 15 do
                a[i]:=a[i]+'}';
end;

begin
        tinh;
        docfile;
end.

BCBASEAD spoj PTIT – Phép cộng cơ sở