맨 위 정수가 주어질때, 아래 두 수의 합이 위 정수가 되는 피라미드 만들기

17802번: Integral Pyramid (acmicpc.net)

 

 

가장 위의 정수가 주어지고, 몇줄로 구성해야하는지 주어지고,

 

현재 정수 x는 바로 아래 줄의 2개의 정수 합으로 구성되도록 만든다.

 

현재 줄이 n개라면 아래 줄은 n+1개로 구성되어야한다.

 

예를 들어 15가 맨 위에 있고 3줄로 구성해야한다면

 

 15

 8 7

3 5 2

 

어떻게 할 수 있을까?

 

그냥 생각했을 때는 맨 위의 정수부터 시작해서 아래로 내려가도록 구성해야할 것 같다

 

맨 아래에서 위로 올라오기는 어려울 것 같다 이 말이지

 

그러면 맨 위의 정수를 절반으로 나눠서 15면 8과 7로 나누고...

 

8은 4와 4로 나눈 다음... 우측의 4와 7을 비교해서 7은 4와 3으로 나누고...

 

789를 6줄로 나누는 것도

 

789를 절반으로 해서 394, 395

 

394는 197, 197이고 197을 395와 비교해서 197,198

 

789

394 395

197 197 198

 

그러면 197을 다시 99,98로 나누고 98을 197과 비교해서 98,99로 나누고 198을 99와 비교해서 99,99로 나누면...

 

그러다가 중간에 음수가 나오면 안되는거다 이렇게 생각했는데

 

이렇게 하면 되는것도 안되는 경우가 있더라

 

반례가 있다는거

 

 

놀라운? 방법이 있는데 위에서 아래로 내려간다는 생각을 하지 말고 아래에서 위로 올라간다는 생각을 해보자

 

아래에서 위로는 어떻게 올라감?

 

맨 아래를 그냥 1,1,1,1,1,...,1로만 채워

 

그러면 그 윗줄은 2,2,2,2,2,...,2

 

그 윗줄은 4,4,4,4,4,...4

 

......

 

맨 윗줄은 $2^{n-1}$로 될거임

 

그러면 목표로 하는 맨 위의 정수를 알고 있기 때문에, $2^{n-1}$과 비교해서 부족한지 더 큰지를 알 수 있다

 

즉 맨 위 정수 x가 $2^{n-1}$보다 작다면 불가능하다.

 

최소의 양의 정수 1부터 시작해서 올라왔으니까 n줄로 만들 수 있는 가장 작은 경우가 $2^{n-1}$인데 이것보다 작으면 불가능

 

x가 크거나 같다면, 그 차이 $x - 2^{n-1}$을 바로 아랫줄의 0번 정수 $2^{n-2}$에 더해주면 된다.

 

그러면 $2^{n-2} + x - 2^{n-1}$과 $2^{n-2}$의 합으로 x가 되기 때문에 문제가 없다.

 

이제 0번 정수인 $2^{n-2} + x - 2^{n-1}$이 원래 $2^{n-2}$에서 커졌으므로, 그 아랫줄과 비교해서 조정을 해줘야한다.

 

$2^{n-3} + 2^{n-3} = 2^{n-2}$가  $2^{n-2} + x - 2^{n-1}$가 되었으므로, 마찬가지로 $x - 2^{n-1}$을 0번 정수에 더해줘야한다.

 

즉 모든 줄의 0번 정수에 $x - 2^{n-1}$을 더해주면 된다.

 

예를 들어 789가 맨 위에 있고 6줄로 만들고 싶다면

 

32

16 16   

8  8 8  

4  4 4 4

2  2 2 2 2

1 1 1 1 1 1     

 

마지막 줄이 32인데, 목표는 789여야 하므로, 789 - 32 = 757을 각 줄의 0번에 더해주면

 

789

773 16

765 8 8

761 4 4 4

759 2 2 2 2

758 1 1 1 1 1

 

이렇게 하면, 바로 아래 두 정수의 합이 바로 위의 정수가 되면서, n줄로 구성되어 있고 

 

맨 위 정수는 목표로 하는 정수 x가 되었으며, 현재 m개가 있다면 바로 아래 줄은 m+1개로 구성되어있는 형태이다.

 

생각하는 것보다 절반으로 나눠서 구성하는게 어렵다는걸 보여주는 문제

 

#맨 위의 정수가 x이고, n줄로 구성된 정수 피라미드 만들기
#현재 바로 아래 두 정수의 합이 현재 정수가 된다
n,x = map(int,input().split())

if n == 1:
    
    print(x)

else:
    
    #맨 아래 줄을 1,1,1,1...,1 n개로 구성하고
    #계속 더해가면 맨 위 정수는 2^n-1
    #이것이 최솟값인데, x가 이것보다 작으면 불가능
    if 2**(n-1) > x:
        
        print('impossible')
    
    else:
        
        
        answer = [[1]*n]

        v = 1

        for i in range(n-1,0,-1):

            row = [v*2]*i
            v *= 2
            answer.append(row)
        
        #목표로 하는 x와 2^n-1의 차이를 각 줄의 0번 정수에 더하면 끝
        diff = x - 2**(n-1)
        
        for i in range(n-1,-1,-1):
            
            answer[i][0] += diff
            
            print(*answer[i])