미친 과학자

면접 대비

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

요약
각 j에 대해 측정값이 j 이하인 개수 P(j)가 주어질 때, 원래의 비감소 측정값 수열을 복원한다.
난이도

쉬움10점 중 3점

유형
배열, 누적 합, 구현
정답자
아직 제출이 없습니다

문제

한 미친 과학자가 여러 번의 실험을 수행했으며, 각 실험은 nn개의 단계로 이루어져 있다. 각 단계마다 측정을 한 번씩 했고, 그 결과는 크기가 최대 kk인 양의 정수였다. 모든 실험은 측정값이 단조 비감소가 되도록 설계되었다. 즉, 각 측정값은 그보다 앞선 모든 측정값보다 작지 않다. 예를 들어 n=13n = 13, k=6k = 6인 어떤 실험의 측정값은 다음과 같다.

1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 6

nn은 항상 kk보다 컸기 때문에 측정값 수열에는 보통 같은 값이 여러 번 반복된다. 과학자는 미쳤기 때문에 데이터를 독특한 방식으로 기록했다. nn개의 측정값을 모두 기록하는 대신, 과학자는 길이가 kk인 수열 PP를 기록했다. 여기서 1≤j≤k1 \le j \le k에 대해 P(j)P(j)는 측정값이 jj 이하인 단계의 개수를 뜻한다. 위 실험의 측정값은 다음 PP 수열로 기록되었다.

2, 7, 7, 8, 12, 13

측정값이 11 이하인 것이 두 개, 22 이하인 것이 일곱 개, 33 이하인 것이 일곱 개, ...이기 때문이다.

과학자는 결국 완전히 미쳐서 이런 PP 수열들이 가득한 공책을 남겼다. 각 PP 수열로부터 원래의 측정값을 복원하는 프로그램을 작성하라.

입력

입력은 여러 개의 PP 수열로 이루어지며, 한 줄에 하나씩 주어진다. 각 줄은 PP 수열의 길이인 정수 kk로 시작하고, 그 뒤에 수열의 kk개 값이 이어진다. 입력의 끝은 00 하나만 있는 줄로 표시된다. 모든 원래 실험은 1≤k<n≤261 \le k < n \le 26을 만족한다.

출력

각 PP 수열에 대해, 복원한 원래 실험의 측정값을 공백 하나로 구분하여 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    6 2 7 7 8 12 13
    1 4
    3 4 4 5
    3 0 4 5
    5 2 2 4 7 7
    0
    
    예상 출력
    1 1 2 2 2 2 2 4 5 5 5 5 6
    1 1 1 1
    1 1 1 1 3
    2 2 2 2 3
    1 1 3 3 4 4 4