Backward Digit Sums

프로그램 명: backward

제한시간: 1 초

존과 그이 소들은 지적인 게임을 하는 것을 즐긴다. 그들은 특정한 순서로 1 에서 N ( 1 <= N <= 10 ) 까지의 수를 적는다 그리고 인접한 수의 합 을 다음 줄에 적는다. 이 것을 수가 하나가 남을 때까지 반복한다.

다음은 , N = 4 인 경우의 한 예이다.

    3   1   2   4
      4   3   6
        7   9
         16

존의 뒤에 있는 소들은 조금 더 어려운 게임을 시작했다. 마지막 수와 N 으로 시작 수들을 결정하는 게임이다.

불행히도 이 게임은 존의 수능력을 약간 벗어난다. 농부 존을 도와 주는 것이 문제이다.

두 개의 정수 N 과 마지막 수가 주어진다.

N 까지의 수로 주어진 마지막 수를 만들 수 있는 수들을 출력한다. 만약 답이 여러개이면 사전식으로 먼저 나오는 것을 출력한다.

3 2 1 4 , 3 1 2 4 두 가지 모두 가능하지만 3 1 2 4 가 사전순으로 더 빨라 답이다.

출처: USACO 2006 February