Bài 3: Cây nhị phân (10 điểm)
Cho 2 xâu ký tự S và T trong đó nếu xâu nào khác rỗng thì chỉ gồm các ký tự thuộc tập hợp {‘U’,
‘L’, ‘R’}.
Xét một cây nhị phân vô hạn, mỗi nút trên cây có đúng một nút cha và hai nút con (nút cha của nút
gốc là chính nó). Xuất phát từ nút gốc, ta có thể di chuyển trên cây đã cho nhờ xâu S bằng cách
duyệt lần lượt các ký tự của xâu S theo quy tắc: ‘L’ là chuyển sang nút con trái, ‘R’ là sang nút con
phải và ‘U’ là chuyển về nút cha. Quá trình này kết thúc tại nút nào đó X. Đương nhiên, nếu S là
xâu rỗng thì X chính là nút gốc.
Ký hiệu là tập hợp tất cả các xâu con của xâu T (mỗi xâu con của T nhận được từ T bằng cách
xoá bỏ một số tuỳ ý các ký tự của nó; xâu rỗng và bản thân T đều là xâu con của T).
Trang 2/3
Yêu cầu: Hãy cho biết số nút khác nhau trên cây có thể di chuyển đến được, bắt đầu từ nút X, bằng
cách di chuyển trên cây nhờ tất cả các xâu trong .
Dữ liệu vào: Vào từ file văn bản BTREE.INP:
Dòng đầu ghi số nguyên T (T ≤ 50), là số lượng bộ dữ liệu vào.
Mỗi bộ dữ liệu vào gồm 2 dòng liên tiếp trong đó mỗi dòng bắt đầu bằng ký tự ‘#’ và tiếp
theo là xâu S (dòng đầu) hoặc xâu T (dòng tiếp theo). Độ dài mỗi xâu S, T đều không vượt
quá 100000 (10 5 ).
Kết quả: Ghi ra file văn bản BTREE.OUT các số nguyên, mỗi số trên một dòng, là kết quả tìm
được tương ứng với bộ dữ liệu vào. Các kết quả cần được lấy là dư của phép chia cho 100000000
(10 8 ).
Ví dụ:
BTREE.INP BTREE.OUT
3
5
1
#
#LL
6
#LR
8
#LU
#RLL
#RLUL
Ràng buộc:
30% test ứng với 30% điểm của bài có tổng độ dài các xâu S và T không vượt quá 22.
50% test ứng với 50% điểm của bài có xâu S là xâu rỗng (độ dài bằng 0).
90% test ứng với 90% điểm của bài có hạn chế bộ nhớ chương trình là 32MB.
5% test ứng với 5% điểm của bài có hạn chế bộ nhớ chương trình là 2MB.
5% test ứng với 5% điểm của bài có hạn chế bộ nhớ chương trình là 1MB.
Thời gian hạn chế cho mỗi file test là 01 giây.
– HẾT –
Họ và tên thí sinh: ...
Số báo danh: ...
Trang 3/3
Bạn đang xem bài 3: - Đề thi Olympic truyền thống 30/4 năm 2018 môn Tin học - 11
