Tổng độ lồng
Đề bài
Mô tả
Một dãy ngoặc được gọi là đúng nếu có thể chèn thêm các ký tự + và 1 vào dãy đó để thu được một biểu thức số học hợp lệ. Ví dụ, (()()) là dãy ngoặc đúng vì ta có thể viết thành ((1+1)+(1+1)). Các dãy ()()(), (()), () cũng là dãy ngoặc đúng, còn )(, ((), ())(() thì không.
Với một dãy ngoặc đúng, độ lồng của một dấu ngoặc mở là số cặp ngoặc bao quanh nó. Chẳng hạn trong dãy ()(()), dấu ngoặc mở thứ nhất có độ lồng , dấu thứ hai có độ lồng , dấu thứ ba có độ lồng ; tổng độ lồng của cả dãy là .
Cho hai số nguyên và . Hãy xây dựng một dãy ngoặc đúng gồm ký tự (tức có đúng dấu ngoặc mở) sao cho tổng độ lồng của tất cả các dấu ngoặc mở bằng đúng .
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và .
Dữ liệu ra
In ra dãy ngoặc đúng thỏa mãn yêu cầu. Nếu có nhiều đáp án, in ra dãy nào cũng được.
Nếu không tồn tại dãy nào thỏa mãn, in ra Impossible.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 | (())() | Ba dấu ngoặc mở có độ lồng lần lượt là , , , tổng bằng . Dãy ()(()) cũng là một đáp án hợp lệ. |
| 2 5 | Impossible | Với , tổng độ lồng lớn nhất đạt được là (ứng với dãy (())), nhỏ hơn . |
| 4 6 | (((()))) | Độ lồng của bốn dấu ngoặc mở lần lượt là , tổng bằng . Đây cũng là tổng lớn nhất có thể với . |
Bình luận