수들의 합 6

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

요약
1부터 N까지의 순열로 만든 파스칼 삼각형 형태의 합계 삼각형에서 맨 아래 값이 주어질 때, 사전순으로 가장 작은 맨 위 행을 복원합니다.
난이도

보통10점 중 5점

유형
조합론, 백트래킹, 수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

맨 윗줄에 11부터 NN까지의 수가 한 번씩 임의의 순서로 적혀 있다. 둘째 줄부터는 파스칼의 삼각형처럼 바로 위 두 수를 더한 값이 아래 칸에 놓인다. 예를 들어 N=4N = 4이고 맨 윗줄이 3 1 2 4이면 다음과 같은 삼각형이 만들어진다.

3 1 2 4
 4 3 6
  7 9
   16

NN과 삼각형의 맨 아래에 있는 수가 주어질 때, 맨 윗줄에 적힌 수들을 구하는 프로그램을 작성하시오. 답이 여러 개이면 사전순으로 가장 앞서는 것을 출력한다.

입력

첫째 줄에 두 정수 NN(1≤N≤101 \le N \le 10)과 FF가 주어진다. NN은 맨 윗줄에 적힌 수의 개수이고, FF는 삼각형의 맨 아래에 있는 수로 1,000,0001{,}000{,}000 이하의 자연수이다.

출력

첫째 줄에 맨 윗줄에 들어갈 NN개의 수를 공백으로 구분하여 출력한다. 답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

예제1

  1. 예제 1

    입력
    4 16
    
    예상 출력
    3 1 2 4