Một dãy số có thể được biểu diễn bởi một mẫu rút gọn theo nhiều cách. Trong bài toán này ta quan tâm đến các dãy số với các phần tử được sắp xếp tăng dần và có hiệu bằng nhau của hai phần tử liên tiếp bất kỳ trong dãy. Khi đó mẫu rút gọn bao gồm ba thành phần: phần tử nhỏ nhất, phần tử lớn nhất và hiệu của hai phần tử liên tiếp. Ví dụ dãy số L = {10, 13, 16, 19, 22} được biểu diễn bởi mẫu rút gọn L = 10 − 22/3.
Cho N dãy, mỗi dãy có tên gọi được ký hiệu bởi một chữ cái viết hoa trong bảng chữ cái tiếng Anh, các dãy số có thể được tính toán trong một biểu thức bởi các toán tử và ký hiệu sau:
• các ký tự tương ứng với các dãy số đã cho;
• các dấu ngoặc;
• toán tử hợp hai dãy số, ký hiệu bởi ‘+’. Ta gọi hợp của 2 dãy A và B là tập tất cả các số có trong A và B. Ví dụ: A = {4, 8, 12, 16}, B = {11, 14, 17, 20, 23}, A + B = {4, 8, 11, 12, 14, 16, 17, 20, 23};
• toán tử giao giữa hai dãy số, ký hiệu bởi dấu ‘*’. Ta gọi hợp của 2 dãy A và B là tập tất cả các số xuất hiện trong cả A và B. Ví dụ: A = {2, 3, 4, 5, 6, 7}, B = {1, 2, 3, 4, 5}, A ∗ B = {2, 3, 4, 5}. Biết rằng thứ tự ưu tiên tính toán trong biểu thức là: dấu ngoặc rồi đến toán tử giao ‘*’ rồi đến toán tử hợp ‘+’.
Yêu cầu: Cho biết mẫu rút gọn của mỗi dãy số và một biểu thức, hãy cho biết dãy số là kết quả tính toán biểu thức đó.
Dữ liệu vào
• Dòng đầu tiên chứa một số nguyên N là số lượng dãy số;
• Mỗi dòng trong số N dòng tiếp theo là mô tả mẫu rút gọn của một dãy số;
• Dòng thứ N + 2 mô tả biểu thức cần tính.
Kết quả
• Dòng đầu tiên chứa một số nguyên là số lượng phần tử của dãy số kết quả tìm được;
• Dòng thứ hai ghi ra các phần tử được sắp xếp tăng dần của dãy số đó, cách nhau bởi dấu cách.
Input
3
A=2-8/2
C=11-23/3
B=4-16/4
A*(B+C)
Output
2
4 8
Input
3
A=2-7/1
B=1-5/1
C=3-9/3
B*A+A*C
Output
5
2 3 4 5 6
Giải thích
• Trong ví dụ thứ nhất, các dãy số là:
A = {2, 4, 6, 8}
B = {4, 8, 12, 16}
C = {11, 14, 17, 20, 23}
Biểu thức được tính toán như sau:
B + C = {4, 8, 11, 12, 14, 16, 17, 20, 23} và
A ∗ (B + C) = 4, 8
• Trong ví dụ thứ hai, các dãy số là:
A = {2, 3, 4, 5, 6, 7}
B = {1, 2, 3, 4, 5}
C = {3, 6, 9}
Biểu thức được tính toán như sau:
B ∗ A = {2, 3, 4, 5},
A ∗ C = {3, 6}, và
B ∗ A + A ∗ C = {2, 3, 4, 5, 6}
Hạn chế
• 1 < N ≤ 16;
• Các phần tử trong dãy là các số nguyên trong khoảng từ 0 đến 109 ;
• Số lượng phần tử trong một dãy không quá 10000;
• Số lượng các ký tự trong một biểu thức trong khoảng từ 3 đến 1000;
• Các mẫu rút gọn trong dữ liệu vào không có dấu cách giữa các ký tự;
• Dữ liệu đảm bảo dãy số kết quả không phải là dãy rỗng.
Nguồn: ĐPT '1819