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 0, dấu thứ hai có độ lồng 0, dấu thứ ba có độ lồng 1; tổng độ lồng của cả dãy là 1.

Cho hai số nguyên n và k. Hãy xây dựng một dãy ngoặc đúng gồm 2n ký tự (tức có đúng n 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 k.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên n và k.

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

  • 1≤n≤3·105
  • 0≤k≤1018

Ví dụ

Input Output Giải thích
3 1 (())() Ba dấu ngoặc mở có độ lồng lần lượt là 0, 1, 0, tổng bằng 1. Dãy ()(()) cũng là một đáp án hợp lệ.
2 5 Impossible Với n=2, tổng độ lồng lớn nhất đạt được là 1 (ứng với dãy (())), nhỏ hơn 5.
4 6 (((()))) Độ lồng của bốn dấu ngoặc mở lần lượt là 0,1,2,3, tổng bằng 0+1+2+3=6. Đây cũng là tổng lớn nhất có thể với n=4.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0