Informatica Online Judge

  Steins;Gate [0650 / 028A]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 11   Total Tried : 18


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

이 세상에는 n개의 세계가 존재한다고 한다. 각 세계를 s1, s2, ... sn이라고 하자. 당신은 현재 sn 세계에 존재하고 있다고 한다. 그런데 당신에게 그 전 세계로 넘어갈 수 있는 기회가 주어진다고 한다. 당신의 목표는 s1세계와 s0세계의 경계인 Steins;Gate을 통과하여 s0에 도달하는 것이다. 그런데 막상 다른 세계로 넘어가려니 고민이 되기 시작한다. 그래서 이전 세계로 넘어가기 위한 결정을 내리기 위해 충분한 시간이 필요하다. 때문에 당신은 타임리프를 하기로 결심한다.

각각의 세계에서는 타임리프를 할 수 있는 횟수가 제한되어 있다. 당신은 이 횟수안에는 타임리프를 끝내고 이전 세계로 도약한다고 한다. 그런데 여기서 특별한 규칙이 있다. 타임리프를 할 때마다 바로 이전 세계선의 타임리프 제한 횟수는 타임리프를 한 횟수만큼 감소한다고 한다. 예를 들어 어떤 세계에서 타임리프를 3번째로 시행할 경우 그 이전 세계의 타임리프 제한횟수는 3회가 감소한다. 다시 말해서 그 이전 세계의 타임리프 제한횟수는 총 6회(1+2+3)회 감소하는 것이다.



타임리프를 할 때는 어떤 세계에서도 타임리프를 할 수 있는 기회가 0보다 작아지지 않도록 한다. 세계의 도약은 언제든 가능하다.

예외적으로 첫번째 세계, s1에서 타임리프를 할 때는 이전의 세계선이 n번째 세계, sn이라고 생각한다. 예를 들어, s1까지 왔을 때 타임리프 제한 횟수가 5회인데 sn의 타임리프 제한 횟수가 1회라면 s1에서는 타임리프를 최대 1회를 시행하고 s0로 넘어간다. 이러한 규칙을 가지고 있다고 할 때 s0에 도달할 때 까지 타임리프를 할 수 있는 최대횟수를 구한다. 또한 총 타임리프의 횟수를 최대로 할 수 있는 각 세계의 타임리프 횟수를 구한다. 최대 횟수에 해당하는 경우를 출력한다.

Input

첫 번째 줄에 오카베가 D메일을 보낸 횟수, 즉 세계선의 개수 n(8이하의 자연수)이 주어진다.
두 번째 줄에 각 세계선의 타임리프 제한 횟수(각 제한 횟수는 100이하)가 차례대로 주어진다.

Output

n번째 세계선에서 출발하여 마지막 D메일을 취소하기까지의 오카베가 타임리프를 할 수 있는 최대 횟수를 출력한다.

그 다음 줄부터 최대 횟수에 대한 타임리프 하는 경우를 출력한다. 만약 최대 횟수가 여러 개 존재한다면, 그 중 사전 순으로 가장 빠른 것을 출력한다.

IO Example

입력
3
3 4 6

출력
5
2 1 2

예시 설명
3번째 세계(s3)에서 타임리프 2회, 2번째 세계(s2)에서 타임리프 1회, 1번째 세계(s1)에서 타임리프 2회를 시행하는 경우로 총 타임리프 횟수 5가 s0에 도달할 때까지 타임리프를 할 수 있는 최대 횟수이다.

출제 : 임정호(GSHS-29th, 2012알고리즘수행평가)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]