| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 378 | 194 | 164 | 57.746% |
도시가 완성된 뒤, 사람들은 그 빛을 기념하기 위한 의식을 열었다. 마을의 광장에는 작은 빛의 점들이 놓였고, 각각은 고유한 빛을 머금은 채 조용히 빛났다.
이제, 의식의 다음 단계가 시작된다. 각 빛은 정해진 방향으로 흘러가며, 새로운 자리를 비추기 시작한다. 빛은 그 이동 경로를 따라 퍼지며, 그 길이와 흐름은 서로 겹치지 않도록 조율되어야 한다.
그들이 정리한 빛의 방향과 흐름을 되짚고, 빛이 퍼져나가는 장면을 다시 완성해 보아라.
광장의 바닥은 격자로 이루어져 있으며, 위아래로는 총 $H$행이며 좌우로는 충분히 넓다. 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 칸을 $(r,c)$로 표기한다.
사람들은 이곳에 $N$개의 빛을 배치했다. 의식의 흐름에 따라, 각 빛은 오른쪽 방향(열 번호가 증가하는 방향)으로 일정 거리만큼 이동해야 한다.
빛의 움직임을 구현하는 것은 어려운 일이기 때문에, 몇 가지 제약 조건이 있다.
예를 들어, $H=2,ドル $N=4$이고, 빛의 시작 위치가 각각 $(1,1) ,(1,3) ,(2,2) ,(2,3)$인 경우를 생각해 보자. 아래 그림에서 각 빛 판의 위치는 서로 다른 색의 정사각형으로 표시되어 있다.
이때 다음과 같은 방식으로 이동 거리를 배정하면 모든 조건을 만족하게 된다.
| 번호 | 시작 위치 | 이동 거리 | 최종 위치 |
|---|---|---|---|
| 1ドル$ | $(1, 1)$ | 2ドル$ | $(1, 3)$ |
| 2ドル$ | $(1, 3)$ | 1ドル$ | $(1, 4)$ |
| 3ドル$ | $(2, 2)$ | 3ドル$ | $(2, 5)$ |
| 4ドル$ | $(2, 3)$ | 4ドル$ | $(2, 7)$ |
아래는 빛의 이동 과정을 시간 순서대로 나타낸 그림이다. 각 그림은 이동이 시작된 시점, 이동 중간의 시점, 이동이 끝난 시점의 빛의 위치를 나타낸다.
빛의 흐름이 겹치지 않도록 이동 거리를 배정할 수 있는지 판단하고, 가능하다면 그 방법을 구하라.
첫 줄에 두 정수 $H$와 $N$이 공백으로 구분되어 주어진다.
이후 $N$개의 줄에 걸쳐, 각 빛의 시작 위치를 나타내는 두 정수 $r_i,ドル $c_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 빛의 시작 위치가 $(r_i,c_i)$라는 뜻이다.
만약 조건을 만족하도록 빛의 이동 거리를 배정할 수 있다면, 첫째 줄에 YES를 출력한다.
둘째 줄에는 $N$개의 정수 $B_1,B_2,\cdots ,B_N$을 공백으로 구분해 출력한다. 이는 $i$번째 빛이 오른쪽으로 $B_i$만큼 움직여야 한다는 의미이다. 가능한 방법이 여러 가지라면 그중 아무것이나 출력해도 좋다.
만약 조건을 만족하도록 빛의 이동 거리를 배정할 수 없다면, 첫째 줄에 NO를 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | $N \le 9$ |
| 2 | 5 | $c_1 = c_2 = \cdots = c_N$ |
| 3 | 32 | $H = 1,ドル $N \le 1000$ |
| 4 | 11 | $H = 1$ |
| 5 | 40 | 추가 제한 조건이 없다. |
2 4 1 1 1 3 2 2 2 3
YES 2 1 3 4
10 3 7 1000000000 9 1000000000 3 1000000000
YES 2 1 3
1 5 1 1 1 3 1 5 1 7 1 9
YES 5 4 3 2 1
Contest > BOJ User Contest > BCF > BCF 2025 III번