trang chủ / đề bài / icpcwf25_j

Xếp chồng cốc

Đề bài

Mô tả

Bạn có một bộ n chiếc cốc hình trụ, chiếc cốc thứ i cao 2i−1 cm. Đường kính các cốc tăng dần, sao cho cốc i lọt vào trong cốc j khi và chỉ khi i<j. Đáy của mỗi cốc dày 1 cm (vì vậy chiếc cốc nhỏ nhất khá vô dụng do chỉ cao 1 cm, nhưng bạn vẫn giữ nó vì lý do kỷ niệm).

Sau khi rửa xong, bạn xếp tất cả các cốc thành một tòa tháp. Bạn lần lượt đặt từng cốc vào tháp, mỗi cốc đều đặt đứng (nói cách khác, miệng cốc hướng lên trên) và tâm của mọi cốc thẳng hàng theo phương thẳng đứng. Mỗi cốc được thả xuống cho đến khi chạm vào các cốc đã đặt trước đó. Chiều cao của tháp là khoảng cách theo phương thẳng đứng từ điểm thấp nhất đến điểm cao nhất của các cốc. Bạn muốn biết phải đặt các cốc theo thứ tự nào để chiều cao cuối cùng (tính bằng cm) đúng bằng con số yêu thích của mình. Lưu ý rằng phải dùng tất cả n chiếc cốc.

Ví dụ, giả sử n=4 và con số yêu thích của bạn là 9. Nếu đặt các cốc có chiều cao 7,3,5,1 theo đúng thứ tự đó thì tòa tháp có tổng chiều cao 9: cốc 7 nằm dưới cùng (từ độ cao 0 đến 7); cốc 3 lọt vào trong, nằm trên đáy cốc 7 (từ 1 đến 4); cốc 5 không lọt vào cốc 3 nên đáy của nó tựa lên miệng cốc 3 (từ 4 đến 9); cốc 1 lọt vào trong cốc 5 và nằm trên đáy cốc 5 (từ 5 đến 6).

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên n và h, trong đó n là số cốc và h là con số yêu thích của bạn.

Dữ liệu ra

Nếu có thể xếp được tòa tháp có chiều cao h, in ra chiều cao của tất cả các cốc theo thứ tự chúng được đặt vào tháp. Ngược lại, in ra impossible. Nếu có nhiều thứ tự hợp lệ, in ra thứ tự nào cũng được chấp nhận.

Ràng buộc

  • 1≤n≤2·105.
  • 1≤h≤4·1010.

Ví dụ

Input Output Giải thích
4 9 7 3 5 1 Đây là tòa tháp được mô tả trong đề, cao 9 cm.
4 100 impossible Tòa tháp 4 cốc cao nhất khi đặt các cốc chồng lên nhau từ nhỏ đến lớn, cao 1+3+5+7=16<100.
3 6 1 5 3 Cốc 1 ở độ cao 0 đến 1; cốc 5 không lọt vào cốc 1 nên tựa lên miệng cốc 1 (từ 1 đến 6); cốc 3 lọt vào trong cốc 5, nằm trên đáy cốc 5 (từ 2 đến 5). Tháp cao 6 cm.

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