시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
20 초 | 256 MB | 46 | 21 | 20 | 51.282% |
브리즈번 시는 돌연변이로 거대해진 웜뱃(호주에 사는 너구리 비슷한 동물)에 장악당했다. 당신의 임무는 사람들을 구조하는 것이다.
브리즈번 시의 도로는 커다란 격자 모양으로 되어 있다. 동서 방향으로 놓인 수평 도로는 R 개가 있고, 북쪽에서 남쪽 방향으로 차례로 번호가 0, …, (R - 1) 로 매겨져 있다. 또한, 남북 방향으로 놓인 수직 도로는 C 개가 있고, 서쪽에서 동쪽 방향으로 차례로 번호가 0, …, (C - 1) 로 매겨져 있다. 다음 그림은 이렇게 번호가 매겨진 도로의 예이다.
웜뱃은 북쪽에서부터 쳐들어오고 있고, 사람들은 남쪽으로 도망친다. 사람들은 가로 방향으로는 어느 쪽이든 움직일 수 있지만, 세로 방향으로는 안전한 방향인 남쪽으로만 움직일 수 있다.
수평 도로 P 와 수직 도로 Q 의 교차로는 (P, Q) 로 표현한다. 두 교차로 사이 세그먼트에는 웜뱃들이 있을 수 있고, 몇 마리의 웜뱃이 있는지는 시간이 흐르면서 변할 수 있다. 여러분의 임무는 북쪽(수평 도로 0 번)의 주어진 교차로에 도착한 사람을 남쪽(수평 도로 R - 1 번)의 주어진 교차로로 가는 길을 알려주는 것인데, 이 경로를 지날 때 가능한 한 적은 수의 웜뱃을 만나야 한다.
먼저, 격자의 크기와 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지가 주어진다. 다음에는 E 개의 이벤트가 차례로 주어지는데, 각 이벤트는 아래 두 가지 중 하나의 형태이다.
change
: 어떤 도로 세그먼트에 있는 웜뱃의 마릿수가 바뀐다.escape
: 사람 한 명이 수평 도로 0 번의 주어진 교차로로 도착하고, 이 사람을 가장 적은 수의 웜뱃을 만나면서 수평 도로 R - 1 의 주어진 교차로로 보내는 경로를 구해야 한다.이러한 이벤트는 다음과 같이 정의되는 함수 init()
, changeH()
, changeV()
, escape()
을 사용하여 처리해야 한다.
위 그림은 수평 도로가 R = 3 개, 수직 도로가 C = 4 개, 그리고 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지 주어진 지도의 처음 상황이다. 다음 순서대로 이벤트가 발생한다고 하자.
change
이벤트가 두 번 발생한다. 수직 도로 0 의 가장 위 세그먼트에 있는 웜뱃의 수가 5 마리로 바뀌고, 수평 도로 1 의 가운데 세그먼트에 있는 웜뱃의 수가 6 마리로 바뀐다. 아래 그림의 동그라미를 친 숫자를 확인해보자.다음 조건을 만족하는 함수 init()
, changeH()
, changeV()
, escape()
을 구현한 파일을 제출하시오.
구현해야 하는 함수: init()
void init(int R, int C, int H[5000][200], int V[5000][200]);
설명
도로의 초기 상태가 이 함수를 통해 전달되며, 당신이 필요로 하는 전역변수 및 자료구조를 이 함수 내에서 초기화할 수 있다. 이 함수는 단 한 번만 호출되며, changeH()
, changeV()
, 또는 escape()
가 입력되기 전에 호출될 것이다.
파라미터
구현해야 하는 함수: changeH()
void changeH(int P, int Q, int W);
설명
이 함수는 교차로 (P, Q) 와 (P, Q + 1) 사이의 수평 도로 세그먼트 위의 웜뱃의 마릿수를 바꿀 때 호출되어진다.
파라미터
구현해야 하는 함수: changeV()
void changeV(int P, int Q, int W);
설명
이 함수는 교차로 (P, Q) 와 (P + 1, Q) 사이의 수직 도로 세그먼트 위의 웜뱃의 마릿수를 바꿀 때 호출된다.
파라미터
구현해야 하는 함수: escape()
int escape(int V1, int V2);
설명
이 함수는 사람이 교차로 (0, V1) 에서 (R - 1, V2) 로 지나갈 때 만나는 웜뱃 마릿수의 최소값을 계산하여야 한다.
파라미터
다음 예제 세션은 위의 예시를 나타낸 것이다.
Function Call | Returns |
---|---|
init(3, 4, [[0,2,5], [7,1,1], [0,4,0]], [[0,0,0,2], [0,3,4,7]]) |
|
escape(2, 1) |
2 |
escape(3, 3) |
7 |
changeV(0, 0, 5) |
|
changeH(1, 1, 6) |
|
escape(2, 1) |
5 |
change
는 최대 500번 (changeH()
또는 changeV()
호출)escape()
는 최대 200,000번 호출번호 | 배점 | 제한 |
---|---|---|
1 | 9 | C = 1 |
2 | 12 | R,C ≤ 20 이고 |
3 | 16 | R,C ≤ 100 이고 |
4 | 18 | C = 2 |
5 | 21 | C ≤ 100 |
6 | 24 | 추가적인 입력 제한 사항이 없다. |
당신의 컴퓨터에 있는 샘플 그레이더는 입력을 파일 wombats.in
에서 읽어들이는데, 포맷은 다음과 같아야 한다.
R
C
H[0][0]
… H[0][C-2]
H[R-1][0]
… H[R-1][C-2]
V[0][0]
… V[0][C-1]
V[R-2][0]
… V[R-2][C-1]
E
C = 1 인 경우, 수평 도로에 존재하는 웜뱃의 마릿수를 나타내기 위해서 (줄 2 부터 R + 1 까지) 빈 줄들을 사용해야 할 필요는 없다.
각 이벤트는 다음 중 하나의 형식을 따라야 한다.
changeH(P, Q, W)
의 표현: 1 P Q W
changeV(P, Q, W)
의 표현: 2 P Q W
escape(V1, V2)
의 표현: 3 V1 V2
예를 들어, 위의 예시는 아래와 같이 입력되어야 한다.
3 4 0 2 5 7 1 1 0 4 0 0 0 0 2 0 3 4 7 5 3 2 1 3 3 3 2 0 0 5 1 1 1 6 3 2 1
C/C++: 당신의 프로그램은 #include "wombats.h"
명령어를 통해 헤더 파일을 추가시켜야 한다.
Olympiad > International Olympiad in Informatics > IOI 2013 > Day 1 3번
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)