정수 피라미드

면접 대비

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

요약
n과 x가 주어질 때 파스칼 덧셈 피라미드의 꼭대기 값이 x가 되도록 모든 칸을 1 이상의 정수로 채울 수 있는지 판정하고, 가능하면 피라미드를 출력한다.
난이도

보통10점 중 6점

유형
조합론, 수학, 그리디, 백트래킹
정답자
아직 제출이 없습니다

문제

파스칼 삼각형은 조합론의 경이로운 대상이며, 집에서도 쉽게 만들 수 있다.

가장 아래쪽 행에는 n개의 수가 있다. 그 위의 행은 어긋나게 놓여 있고 n − 1개의 수가 있으며, i번째 수는 아래 행의 i번째 수와 i + 1번째 수의 합이다.

가장 아래쪽 행에는 임의의 양의 정수를 넣을 수 있지만, 가장 위쪽 행의 단 하나의 칸은 주어진 x와 같아야 한다. 이것이 가능한가?

입력

  • 유일한 줄에 행의 수 n (1 ≤ n ≤ 20)과 가장 위에 필요한 값 x (1 ≤ x ≤ 109)가 주어진다.

출력

피라미드를 만들 수 있다면, 가장 위쪽 행부터 시작하여 각 행의 모든 수를 출력한다. 모든 수는 1 이상이어야 한다.

그렇지 않으면 impossible을 출력한다.

예제3

  1. 예제 1

    입력
    3 15
    예상 출력
    15
8 7
3 5 2

  2. 예제 2

    입력
    6 789
    예상 출력
    789
394 395
209 185 210
117 92 93 117
70 47 45 48 69
45 25 22 23 25 44

  3. 예제 3

    입력
    20 1
    예상 출력
    impossible