Stacking Cups

시간 제한2초메모리 제한2048 MB

요약
지름이 커지는 n개의 컵을 포개어 쌓을 때 탑 높이가 목표 h가 되는 배치 순서를 찾고, 불가능하면 impossible을 출력한다.
난이도

보통10점 중 6점

유형
그리디, 수학, 구현, 정렬
정답자
아직 제출이 없습니다

문제

You have a collection of nn cylindrical cups, where the iith cup is 2i−12i−1 cm tall. The cups have increasing diameters, such that cup ii fits inside cup jj if and only if i<ji < j. The base of each cup is 11 cm thick (which makes the smallest cup rather useless as it is only 11 cm tall, but you keep it for sentimental reasons).

After washing all the cups, you stack them in a tower. Each cup is placed upright (in other words, with the opening at the top) and with the centers of all the cups aligned vertically. The height of the tower is defined as the vertical distance from the lowest point on any of the cups to the highest. You would like to know in what order to place the cups such that the final height (in cm) is your favorite number. Note that all nn cups must be used.

For example, suppose n=4n = 4 and your favorite number is 99. If you place the cups of heights 77, 33, 55, 11, in that order, the tower will have a total height of 99, as shown in Figure J.1.

Figure J.1: Illustration of Sample Output 1.

입력

The input consists of a single line containing two integers nn and hh, where nn (1≤n≤2⋅1051 ≤ n ≤ 2 \cdot 10^5) is the number of cups and hh (1≤h≤4⋅10101 ≤ h ≤ 4 \cdot 10^{10}) is your favorite number.

출력

If it is possible to build a tower with height hh, output the heights of all the cups in the order they should be placed to achieve this. Otherwise, output impossible. If there is more than one valid ordering of cups, any one will be accepted.

예제2

  1. 예제 1

    입력
    4 9
    
    예상 출력
    7 3 5 1
    
  2. 예제 2

    입력
    4 100
    
    예상 출력
    impossible