| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 199 | 72 | 50 | 36.765% |
너에게서는 멸종된 과일 향기가 난다
투룸 신축 빌라 보증금 이천에 월세 구십, 어떻게 해야 너를 웃길 수 있을까 하는 생각, 두 시간 동안의 폭우, 일주일 동안의 아침, 유리병 속 무한히 터지는 기포
-고선경, [샤워젤과 소다수]
세로로 길쭉한 유리병 하나가 있다. 이 속에서 기포가 무한히 터지고 있다.
과학자 정우가 이 현상에 호기심을 느끼고 계속해서 관찰한 결과 다음과 같은 사실을 알아냈다. 먼저, 유리병을 세로로 $N$등분하여 가장 아래에 위치한 $1$번째 구역부터 가장 위에 위치한 $N$번째 구역까지 총 $N$개의 구역으로 나눌 수 있다. 각 구역마다 최대 $M$개의 기포가 존재할 수 있다. 처음에는 어느 구역에도 기포가 존재하지 않고, $1$초마다 유리병 내에서 다음 두 현상이 순서대로 번갈아 가며 일어난다.
그림 1. (a) 유리병을 $N$개의 구역으로 나눈 모습. (b) $1$번째 구역과 $N$번째 구역에서 각각 기포 이동이 일어나는 모습.
정우는 유리병 속 기포의 움직임을 모델링하는 프로그램을 만들려 한다. $t$초가 지난 후, 즉 기포 생성과 기포 이동이 각각 $t$번 일어난 후 유리병 속에 남은 모든 기포의 수를 $S(t)$라 하자. 관찰을 진행한 시간 $T$가 주어질 때, $S(1), S(2), \cdots, S(T)$의 값을 구하시오.
첫째 줄에 유리병을 이루는 구역의 수 $N$, 각 구역마다 존재할 수 있는 최대 기포의 수 $M$, 관찰을 진행한 시간 $T$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 100\,000$, $1 \leq T \leq 50\,000$)
둘째 줄부터 $T$개의 줄에 걸쳐, $i$번째 기포 생성에 대해 기포가 생성되는 구역의 번호 $y_i$와 그 구역에서 생성되는 기포의 수 $k_i$가 공백으로 구분되어 주어진다. ($1 \leq y_i \leq N$, $0 \leq k_i \leq M$)
$T$개의 줄에 걸쳐, $i$번째 줄에 $S(i)$의 값을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $N, T \leq 1\,000$ |
| 2 | 30 | 모든 $i$에 대해 $y_i=1$이다. |
| 3 | 50 | 추가 제약 조건이 없다. |
6 100 6 3 20 2 40 4 60 3 80 1 100 5 100
12 24 44 66 73 92
$1$초가 지난 후 각 구역마다 존재하는 기포의 수는 $[0, 4, 4, 4, 0, 0]$이다.
$2$초가 지난 후 각 구역마다 존재하는 기포의 수는 $[8, 8, 8, 0, 0, 0]$이다.
$3$초가 지난 후 각 구역마다 존재하는 기포의 수는 $[2, 3, 14, 13, 12, 0]$이다.
$4$초가 지난 후 각 구역마다 존재하는 기포의 수는 $[0, 18, 20, 22, 4, 2]$이다.
$5$초가 지난 후 각 구역마다 존재하는 기포의 수는 $[23, 27, 11, 8, 4, 0]$이다.
$6$초가 지난 후 각 구역마다 존재하는 기포의 수는 $[9, 11, 8, 23, 21, 20]$이다.
6 100 2 1 100 1 100
40 52
$\lfloor\cdot\rfloor$는 바닥 함수로, 주어진 실수 이하의 최대 정수를 나타내는 함수이다.
University > 광주과학기술원 > 2024 GIST 알고리즘 마스터즈 F번