Xếp chồng cốc
Đề bài
Mô tả
Bạn có một bộ chiếc cốc hình trụ, chiếc cốc thứ cao cm. Đường kính các cốc tăng dần, sao cho cốc lọt vào trong cốc khi và chỉ khi . Đáy của mỗi cốc dày cm (vì vậy chiếc cốc nhỏ nhất khá vô dụng do chỉ cao 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ả chiếc cốc.
Ví dụ, giả sử và con số yêu thích của bạn là . Nếu đặt các cốc có chiều cao theo đúng thứ tự đó thì tòa tháp có tổng chiều cao : cốc nằm dưới cùng (từ độ cao đến ); cốc lọt vào trong, nằm trên đáy cốc (từ đến ); cốc không lọt vào cốc nên đáy của nó tựa lên miệng cốc (từ đến ); cốc lọt vào trong cốc và nằm trên đáy cốc (từ đến ).
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và , trong đó là số cốc và 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 , 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
- .
- .
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 cm. |
| 4 100 | impossible | Tòa tháp cốc cao nhất khi đặt các cốc chồng lên nhau từ nhỏ đến lớn, cao . |
| 3 6 | 1 5 3 | Cốc ở độ cao đến ; cốc không lọt vào cốc nên tựa lên miệng cốc (từ đến ); cốc lọt vào trong cốc , nằm trên đáy cốc (từ đến ). Tháp cao cm. |
Bình luận