루미 알고리즘

#1100플래티넘색깔 모으기색깔 모으기

KOI 2024 2차코딩초등부 3번, 중등부 2번출제 정보올림피아드위원회이 문제가 어렵다면 — 배우는 순서 보기

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

색깔 모으기

원제: 색깔 모으기

문제

2N2N개의 공과 N+1N + 1개의 상자가 있다. 공들의 색깔은 1,2,⋯ ,N1, 2, \cdots, N 중 하나이며, 각 색깔에 대해 그 색깔로 칠해진 공은 정확히 22개 있다. 각 상자는 공을 최대 22개까지 가지고 있을 수 있다. 처음에는 첫 번째 상자부터 NN번째 상자에 각각 22개의 공이 들어 있고, N+1N + 1번째 상자는 비어 있다. ii번째 상자의 위에 있는 공의 색깔은 AiA_i이고, 아래에 있는 공의 색깔은 BiB_i이다.

한 상자에서 다른 상자로 공을 옮길 수 있는데, 상자의 가장 위에 있는 공을 빼서 다른 상자의 가장 위에 넣는 작업을 할 수 있다.

여러분은 같은 색으로 칠해진 22개의 공이 같은 상자에 들어가도록 공을 옮겨야 한다. 이때, 공을 옮기는 작업을 할 때마다 다음 두 조건 중 하나를 만족해야 한다.

  • 옮겨서 공을 놓으려는 상자가 완전히 비어 있어야 한다.
  • 옮겨서 공을 놓으려는 상자에 공이 정확히 하나 들어 있고, 이동하려는 공과 해당 상자에 있는 공의 색깔이 같아야 한다.

색깔이 같은 공이 같은 상자에 들어가도록 하기 위해 필요한 공의 이동 횟수의 최솟값을 구하는 프로그램을 작성하라.

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

예를 들어, 위 그림에서 아래와 같이 공을 옮기면 66번의 이동으로 색깔이 같은 공이 같은 상자에 들어가게 되고, 공을 66번보다 적게 옮겨서 목표를 달성하는 것은 불가능하다.

  • 네 번째 상자의 색깔이 33인 공을 여섯 번째 상자로 옮긴다.
  • 세 번째 상자의 색깔이 22인 공을 네 번째 상자로 옮긴다.
  • 첫 번째 상자의 색깔이 44인 공을 세 번째 상자로 옮긴다.
  • 두 번째 상자의 색깔이 33인 공을 여섯 번째 상자로 옮긴다.
  • 다섯 번째 상자의 색깔이 55인 공을 두 번째 상자로 옮긴다.
  • 다섯 번째 상자의 색깔이 11인 공을 첫 번째 상자로 옮긴다.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤200 0001 \le N \le 200\,000
  • 1≤Ai,Bi≤N1 \le A_i, B_i \le N
  • 각 ii (1≤i≤N1 \le i \le N)에 대해서 A1,A2,⋯ ,AN,B1,B2,⋯ ,BNA_1, A_2, \cdots, A_N, B_1, B_2, \cdots, B_N중 정확히 22개의 값이 ii와 같다.

부분문제

  1. (2점) N≤2N \le 2
  2. (23점) N≤20N \le 20
  3. (15점) 색이 같은 공이 같은 상자에 들어가도록 공을 옮기는 방법이 존재한다.
  4. (15점) N≤2 000N \le 2\,000
  5. (45점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 NN이 주어진다.

두 번째 줄부터 NN개의 줄에 걸쳐 각 상자에 들어 있는 두 공들의 색깔이 주어진다. NN개의 줄 중 ii번째 줄에는 Ai,BiA_i, B_i가 공백으로 구분되어 주어진다.

출력 형식

첫 번째 줄에 색깔이 같은 공이 같은 상자에 들어가도록 하기 위해 필요한 공의 이동 횟수의 최솟값을 출력한다.

단, 불가능하다면 −1-1을 출력한다.

예제

예제 1

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

예제 2

입력
2
1 1
2 2
출력
0

예제 3

입력
4
2 1
3 1
2 4
3 4
출력
-1

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.