저울 추 고르기

문제

2
100
1000000000

3 8 89 
1 5 13 89 233 1597 28657 75025 196418 514229 5702887 24157817 267914296 701408733 

1
325631899

1 3 8 21 89 233 610 1597 4181 46368 121393 3524578 14930352 39088169 267914296 

1
150128012

5 55 144 610 2584 6765 28657 75025 196418 514229 2178309 5702887 39088169 102334155 

입력 조건

• 가장 먼저 손님의 수 T가 첫째 줄에 주어진다. T는 1 이상 20 이하의 자연수다.

• 이어서 둘째 줄부터 T+1번째 줄까지 각 손님이 말한 무게가 한 줄에 하나씩 주어진다. 각 무게는 1 이상 1,000,000,000 이하의 자연수다. 한 줄에 수가 하나씩 오므로 입력은 모두 T+1줄이다.

• 추의 무게는 입력으로 주어지지 않는다. 1과 2에서 시작해 바로 앞의 두 무게를 더해 가며 늘어나는 규칙으로 직접 만들어 쓴다.

출력 조건

• 손님마다 한 줄씩, 올리는 추의 무게를 작은 것부터 차례대로 입력에 주어진 순서대로 출력한다.

• 각 수 뒤에 공백을 하나 붙여서 출력한다. 그래서 줄의 마지막 수 뒤에도 공백이 하나 남는다.

• 한 손님의 답을 적은 뒤에는 줄을 한 번 바꾼다. 마지막 줄 다음에 빈 줄을 더 붙이지는 않는다.

• 채점은 출력을 기대값과 글자 하나까지 견준다. 줄 끝의 공백이 없으면 추를 맞게 골랐어도 틀린 답으로 처리된다. 예를 들어 손님이 말한 무게가 1이면 출력해야 하는 글자는 1과 공백과 줄바꿈의 세 글자다.

요구사항

• 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
• 추의 무게는 1과 2로 시작해 바로 앞의 두 무게를 더해 가며 늘어납니다. 같은 무게의 추는 하나뿐이라 두 번 올릴 수 없습니다
• 올린 추의 무게를 모두 더한 값이 손님이 말한 무게와 정확히 같아야 하고, 그 가운데 추의 개수가 가장 적어야 합니다
• 한 줄에 한 손님의 답을 작은 무게부터 출력하며, 줄의 순서는 입력에 주어진 순서와 같습니다
• 각 수 뒤에 공백을 하나 붙이므로 줄의 마지막 수 뒤에도 공백이 하나 남습니다. 아래 예시의 각 줄 끝에는 눈에 보이지 않는 공백이 하나씩 있습니다
• 채점은 출력을 기대값과 글자 하나까지 견줍니다
• 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
• 쓸 수 있는 말은 파이썬, 자바스크립트입니다
• 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
• 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
• 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
• 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
• 케이스 15개를 전부 통과해야 해결입니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

2
100
1000000000

3 8 89
1 5 13 89 233 1597 28657 75025 196418 514229 5702887 24157817 267914296 701408733

1
325631899

1 3 8 21 89 233 610 1597 4181 46368 121393 3524578 14930352 39088169 267914296

1
150128012

5 55 144 610 2584 6765 28657 75025 196418 514229 2178309 5702887 39088169 102334155