루미 알고리즘

#1117플래티넘점프점프

KOI 2025 2차코딩고등부 1번출제 박수찬이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

점프

원제: 점프

문제

2 이상의 NN에 대해 11부터 NN까지의 번호가 붙은 NN개의 정점이 번호 순서대로 일직선상에 놓여있고, 각 i(1≤i≤N−1)i(1 \le i \le N - 1)에 대해 정점 ii와 i+1i + 1을 양방향으로 잇는 간선이 있는 상황을 고려하자.

예를 들어, N=5N = 5인 경우에는 아래 그림과 같이 정점과 간선이 배치된다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

정올이는 이 그래프 위에서 점프하여 이동할 수 있다. 정올이가 어느 한 정점에서 다른 정점으로 점프하면, 그 사이에 있는 모든 간선을 한 번씩 지나간다.

예를 들어:

  • 정올이가 정점 44에서 22로 점프했다면, 정올이는 정점 33과 44 사이의 간선과 정점 22와 33 사이의 간선을 각각 한 번씩 지나간다.
  • 정올이가 정점 33에서 44로 점프했다면 정점 33과 44 사이의 간선을 한 번 지나간다.

정올이는 정점 11에서 시작해 N−1N - 1번의 점프를 거쳐 정점 NN에 도착했고, 그 과정에서 모든 정점을 정확히 한 번씩 방문했다. (처음에 정점 11에 있었던 것도 방문으로 간주한다.)

다시 말해, 정올이가 정점들을 방문한 순서를 p1→p2→⋯→pN−1→pNp_1 \to p_2 \to \cdots \to p_{N-1} \to p_N 이라고 할 때, p1=1p_1 = 1이고, pN=Np_N = N 이며, {p1,p2,⋯ ,pN}={1,2,⋯ ,N}\{p_1, p_2, \cdots, p_N\} = \{1, 2, \cdots, N\}이다.

이때, 정올이가 점프하는 과정에서 각 i(1≤i≤N−1)i(1 \le i \le N - 1)에 대해 정점 ii와 i+1i + 1 사이 간선을 지나간 횟수를 cic_i라고 하자.

예를 들어, 정올이가 (p1=1)→(p2=3)→(p3=4)→(p4=2)→(p5=5)(p_1 = 1) \to (p_2 = 3) \to (p_3 = 4) \to (p_4 = 2) \to (p_5 = 5) 순서로 방문했다면, c1=1c_1 = 1, c2=3c_2 = 3, c3=3c_3 = 3, c4=1c_4 = 1이 된다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

정올이가 정점들을 방문하면서 각 간선을 지난 횟수를 나타내는 수열 c=(c1,c2,⋯ ,cN−1)c = (c_1, c_2, \cdots, c_{N-1})이 주어졌을 때, 이로부터 정올이의 방문 순서 p1,p2,⋯ ,pNp_1, p_2, \cdots, p_N을 구하는 프로그램을 작성하라.

주어지는 수열 cc는 항상 어떤 방문 순서에 의해 만들어진 것이므로, 이를 만족하는 방문 순서는 항상 존재한다. 만약 가능한 방문 순서가 여러 가지라면 아무것이나 하나 구하면 된다.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤200 0002 \le N \le 200\,000
  • 1≤i≤N−11 \le i \le N - 1인 모든 ii에 대해 1≤ci≤10181 \le c_i \le 10^{18}
  • 가능한 방문 순서가 존재하는 입력만 주어진다.

부분문제

  1. (10점) N≤10N \le 10.
  2. (10점) 1≤i≤N−11 \le i \le N - 1인 모든 ii에 대해 ci≤3c_i \le 3.
  3. (15점) N≥4N \ge 4 이며, 22 이상 N−2N - 2 이하의 어떤 정수 MM이 존재해, c1≤c2≤⋯≤cMc_1 \le c_2 \le \cdots \le c_M 이고 cM≥cM+1≥⋯≥cN−1c_M \ge c_{M+1} \ge \cdots \ge c_{N-1} 이다. 다시 말해, cic_i가 단조 증가하다가 단조 감소하는 형태를 가진다.
  4. (35점) N≤300N \le 300.
  5. (30점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 정점의 개수 NN이 주어진다.

두 번째 줄에 N−1N - 1개의 정수 c1,c2,⋯ ,cN−1c_1, c_2, \cdots, c_{N-1}이 공백을 사이에 두고 주어진다. 이때, cic_i는 정점 ii와 i+1i + 1 사이의 간선을 지나간 횟수를 의미한다.

출력 형식

정올이의 가능한 방문 순서 p1,p2,⋯ ,pNp_1, p_2, \cdots, p_N을 공백으로 구분하여 출력한다. 만약 가능한 방문 순서가 여러 가지라면 아무것이나 하나 출력한다.

예제

예제 1

입력
5
1 3 3 1
출력
1 3 4 2 5

예제 2

입력
7
1 3 3 5 3 1
출력
1 6 2 3 5 4 7

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.