Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo Problem A. Dungeon Input file: Output file: Time limit: Memory limit: second 56 megabytes 당신은 Just Ordinary Inventions사를 아는가? 이 회사의 업무는, 그저 평범한 발명(just ordinary inventions) 를 하는것이다. JOI군은, Just Ordinary Invention사가 개발한 최신 게임을 하고 있다. 이 게임은, 몇개의 방과 몇개의 길로 구성된 던전을 탐험하는 게임이다. 길은 던전 내의 서로 다른 개의 방을 연결하고 있으며, 양방향으로 이동 가능 하다. 어떤 다른 개의 방에 대해서도, 그들을 연결하는 길은 최대 하나 밖에 없고, 양쪽에 같은 방이 있는 길은 존재하지 않는다, 또한 던전에 있는 어떤 개의 방도, 몇개의 길을 이용하면 서로 이동할 수 있다는 것을 알고 있다. 각 방끼리는 매우 유사하며, 동일한 갯수의 길이 나오는 방 끼리는,방 모습을 보는 것 만으로는 구별할 수 없다. 이 게임에서는 공략을 돕기 위해 각 방마다 표적과 받침대가 준비되어있다. 방에서 나오는 길은, 표적을 기준으로 첫번째, 두번째, 로 셀 수 있다. 게임 중 던전의 구조가 바뀌지는 않는다. 따라서, 같은 방에서 같은 번호의 길을 통해 이동하면 항상 같은 방에 도착한다. 받침대는 플레이어가 색을 변경할 수 있는 구슬이 하나 있다. 보석의 색은 색, 색,, 색 X중 하나 이며, 게임 시작시 각 방 보석의 색은 색 이다. 보석의 색은 플레이어가 색을 변경하지 않는 한 바뀌지 않는다. JOI군은, 만약 던전에 구조, 즉 던전의 방들이 어떻게 길로 연결되어 있는가에 대해 알면, 이 게임은 간단히 공략이 될 것이라 느꼈다. 하지만, JOI군이 여러가지로 시도해봐도 던전의 구조를 알 수 없었다. 그래서 당신은 JOI군을 대신해서 던전의 구조를 결정하는 프로그램을 작성하기로 했다. 던전을 탐험하고, 던전의 구조를 결정하는 프로그램을 작성하여라. 단, JOI군은 던전의 구조를 완전히 아는것을 원치 않았기 때문에, 프로그램은 던전의 구조를 직접 답하는 대신, 이상 R이하의 정수 i에 대해, 최소 i개의 길을 이용해서 개의 방을 이동할 수 있는 쌍이 몇개 있는가 (단, 방의 순서만 바꾼 것은 같은 쌍으로 본다.)를 답해야 한다. 던전을 탐험하기 위해, 당신에게는 다음의 라이브러리가 제공된다. 현재 있는 방에서, 나가는 길이 몇개 있는지를 알 수 있다. 현재 방 받침대에 장식되어 있는 보석의 색을 알 수 있다. 현재 방 받침대에 장식되어 있는 보석의 색을 지정한 색으로 바꿀 수 있다. (같은 색으로도 바꿀 수 있다.) 그 후, 방에서 나와, 길을 하나 선택하고, 그 길을 이용해 다른 방으로 이동한다. 마지막으로 사용한 길이, 현재 있는 방에서 몇번째 길인지 알 수 있다. Interaction Protocol 당신은, JOI군에게 답할 방법을 담은 개의 프로그램을 작성해야 한다. 프로그램은 dungeon.h를 include 해야 한다. 프로그램에는, 다음의 함수가 구현되어 있어야 한다. void Inspect(Int R) 이 함수는, 처음 번만 실행된다. 인자 R은, 이상 R이하의 각 정수 i에 대해, 최소 i개의 길을 이용해서 개의 방을 이동할 수 있는 쌍이 몇개 있는가 (단, 방의 순서만 바꾼 것은 같은 쌍으로 본다.)를 답해야 하는 것을 의미한다. 또한, 당신은 다음 함수를 불러 질문에 대한 답을 해야 한다. void Answer(int D, int A) 인자 D, A는, 이 함수 호출을 할 때, 최소 D개의 길을 이용해서 개의 방을 이동할 수 있는 쌍은 A개가 있다. 라는 답을 의미한다. Page of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo 단, Answer를 호출 할 때는, 다음의 조건을 만족해야 한다. D는 이상 R이하의 정수여야 한다. 이것을 만족하지 않을 경우 오답 []이 된다. Answer를 같은 인자 D로 번 이상 호출하면 안된다. 이것을 만족하지 않은 경우 오답 []가 된다. Answer는 정확히 R번 호출되어야 한다. 이것을 만족하지 않은 경우, 오답 []이 된다. A는 최소 D개의 길을 이용해서 개의 방을 이동할 수 있는 쌍의 갯수여야 한다. 이것을 만족하지 않은 경우 오답 []가 된다. 추가로, 프로그램 중에 다음 함수를 호출할 수 있다. void Move(int I, int C) 인자 I는, 플레이어가 이동하기 위해서 고른 길의 번호를 의미한다. 이 함수가 호출된 직후, 플레이어는 현재 있는 방에서 I번째 길을 이용해 다른 방으로 이동한다. 인자 C는, 방을 이동하기 전에, 현재 방 받침대에 있는 보석의 색을 색 C로 바꾸는 것을 의미한다. 단, Move를 호출할 때, 다음 조건을 만족해야 한다. 인자 I는, 플레이어가 현재 있는 방에서 나올 수 있는 길의 수를 K라 할 때, 이상 K이하의 정수여야 한다. 이것을 만족하지 않은 경우 오답 [5]가 된다. 인자 C는, 보석의 색의 종류가 X종류라고 할 때, 이상 X이하의 정수여야 한다. X는 Subtask 에 따라 결정된다. 이것을 만족하지 않은 경우 오답 [6]이 된다. Move를 500 000번 이상 호출해서는 안된다. 이것을 만족하지 않은 경우 오답 []이 된다. int NumberOfRoads() 이 함수는, 플레이어가 현재 있는 방에서 나가는 길의 갯수를 반환한다. int LastRoad() 이 함수는, 플레이어가 마지막에 사용한 길을, 현재 있는 방에서 몇번째 길인지를 반환한다. 단, Move가 한번도 호출되지 않았을 경우, -을 반환한다. int Color() 이 함수는, 플레이어가 현재 있는 방에 위치해있는 보석의 색을 반환한다. 함수 Inspect를 호출 한 후, 답에 대한 판단을 한다. 내부 사용을 위해서 다른 함수를 구현하거나, 글로벌 변수를 선언하는것은 자유이다. 하지만, 당신의 제출은 표준 입출력이나, 다른 함수에 접근하면 안 된다. 작성한 프로그램을 테스트하기 위한 채점 프로그램 샘플이, 콘테스트 사이트에서 다운로드 받을 수 있는 아카이브 안에 있다. 이 아카이브는, 제출해야하는 파일의 샘플도 들어있다. 채점 프로그램 샘플은 개의 파일이다. 이 파일은 grader.c 혹은 grader.cpp이다. 작성한 프로그램을 테스트 하기 위해서는, 다음의 커맨드를 실행한다. C의 경우 gcc -std=c -O -o grader grader.c dungeon.c -lm C++의 경우 g++ -std=c++ -O -o grader grader.cpp dungeon.cpp 컴파일에 성공하면, grader라는 이름의 파일이 생성된다. 실제의 채점 프로그램은, 채점 프로그램 샘플과는 다르므로 주의한다. 채점 프로그램의 샘플은 단일 프로세스로 실행된다. 이 프로그램은, 표준입력에서 입력을 받아서, 표준출력으로 결과를 출력한다. 채점 프로그램 샘플은, 표준입력에서 다음과 같은 데이터를 읽는다. Input Page of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo 첫째 줄에는, 정수 N, X, R이 공백으로 구분되어 들어온다. 이것은, 던전이 방, 방,, 방 N 의 N 개의 방으로 되어 있고, 보석의 색은 X종류 이며, 프로그램이 답해야 하는 값이 R개 임을 의미한다. 다음 N 개의 줄의 i 번째 줄 ( i N )에는, 정수 Di 가 들어오고, 방 i에서 Di 개의 나가는 길이 있다는 것을 의미한다. i번째 줄에는 Di 개의 정수 Ti, Ti,, TiDi 가 공백으로 구분되어 들어온다. 이것은, 방 i에서 나가는 j ( j Di )번째 도로를 써서 이동한 방의 번호가 Ti j라는 것을 의미한다. 다음 R개의 줄의 j번째 줄 ( j R)에는, 정수 Aj 가 쓰여 있다. 이것은, 최소 j개의 길을 이용해서 개의 방을 이동할 수 있는 쌍은 Aj 개가 있다. 는 것을 의미한다. 즉, 각 j( j R)에 대해, Answer 의 인수 D를 j, 인수 A를 Aj 로 해서 호출 한 경우, 채점 프로그램이 정답으로 생각하고, 다른 경우 오답으로 생각한다는 것을 의미한다. 채점 프로그램은, 플레이어의 초기 위치를 방 로 하여, 당신이 작성한 함수를 호출한다. Output 프로그램의 실행이 정상적으로 종료된 경우, 채점 프로그램 샘플은 표준출력으로 다음의 정보를 첫째 줄에 출력한다. (따옴표는 출력되지 않는다.) 정답일 경우, 함수 Move를 호출한 횟수가 "Accepted : #move = 8"처럼 출력한다. 오답일 경우, 오답의 종류를 "Wrong Answer []"처럼 출력한다. Constraints 모든 입력데이터는 다음의 조건을 만족한다. N, Di, Tij 의 의미에 대해서는 채점 프로그램의 샘플 입력을 참고하여라. N 00 X 00 R 00 Di N ( i N ) Tij N 이며 Tij 6= i ( i N, j Di ) Ti, Ti,, TiDi 는 서로 다르다. 각 i, j ( i N, j Di )에 대해, TTij k = i를 만족하는 k ( k DTij )가 존재한다. 어떤 개에 방에 대해서도, 몇개의 길을 쓰면 서로 이동할 수 있다. 이하에서, 입력데이터의 방의 수를 N, 길의 수를 M 이라 한다. Subtask ( points) 다음의 조건을 만족한다. N 50 M 00 X = 00 Subtask (50 points) 다음의 조건을 만족한다. Page of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo N 50 M 00 X= Subtask (0 points) 다음의 조건을 만족한다. X = 을 만족한다. 이 Subtask에서는 다음에 따라 점수가 정해진다. 이 Subtask의 모든 테스트데이터에 대해, 다음의 최댓값을 L이라 한다. Move의 호출 횟수를 C라고 할 때, C M 이 때, 이 Subtask의 득점은 L 일 때, 56점. < L 일 때, b0 Lc점. < L 6일 때, b5 L c점. 6 < L일 때, 0점. 여기서 bxc는 x를 넘지 않는 최대의 정수로 한다. 채점 시스템 상에서, 프로그램이 정상적으로 종료되었을 경우 채점 결과를 Accepted로 표시한다. 단 Subtask C 에서 6 < M 인 테스트케이스에 대해서는, 결과가 오답으로 표시됨에 주의하라. Example 다음은 채점 프로그램 샘플이 입력받은 입력 예제와, 그에 대응되는 함수 호출 예이다. 0 interaction Function call Inspect() NumberOfRoads() LastRoad() Move(, ) Color() LastRoad() NumberOfRoads() Move(, ) Color() Answer(, ) Answer(, ) Answer(, 0) Return value - 이 예제의 함수 호출은, 반드시 의미 있는 호출은 아니라는 점에 주의하라. Page of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo Problem B. Sushi Input file: Output file: Time limit: Memory limit: 9 seconds 56 megabytes 회전초밥집 JOI는 초밥을 담은 접시를 원모양의 컨베이어 벨트로 운반하고 있다. 컨베이어 벨트는 반시계방향으로 돌고 있다. 현재, 가게 내에는 손님 부터 손님 N 까지 N 명의 손님이 있고, 손님은 컨베이어 벨트에 시계 반대방향으로 앉아있다. 손님 N 옆에는 손님 이 앉아있다. 손님은, 한 사람이 한 개씩 접시를 갖고 있다. 각 접시에는 가치라고 불리는 숫자가 정해져 있어서, 가게를 나갈 때에 손님은 자신이 가지고 있는 접시의 가치와 같은 양의 돈을 지불한다. 회전초밥집 JOI에서는, 색다른 타임 세일을 하고 있다. 이 타임세일에는, Q번에 나누어 차례대로 요리사로부터 접시가 제공된다. i ( i Q)번째 접시의 내용은 개의 수 (Si, Ti, Pi )로 표시된다. 타임세일의 룰은 다음과 같다. 타임 세일이 시작하기 직전, 요리사는 컨베이어 벨트에 있는 접시를 모두 회수한다. 이하의 을 i =,,, Q까지 반복한다.. 요리사가 손님 Si 앞 위치 컨베이어 벨트에, 가치 Pi 의 접시를 놓는다.. 접시는 손님 Si 의 위치 부터 손님 Ti 의 위치 까지 컨베이어 벨트 위를 이동한다. 각각의 손님은, 자신의 앞에 접시에 대해, 다음 행동을 한다. 만약, 그 접시의 가치가 자신이 갖고 있는 접시의 가치보다 작으면, 자신의 접시와 컨베이어 벨트의 접시를 교환한다. 만약, 그 접시의 가치가 자신이 갖고 있는 접시의 가치 이상이면, 접시를 교환하지 않는다. 접시가 Ti 에 도착한 후, 요리사가 그 접시를 회수한다. 당신은 요리사 밑에서 장인수업을 듣고 있는 제자이고, 가게 접시의 설거지를 맡고 있다. 회전초밥집 JOI 의 접시의 가치에 따라 설거지 방법이 다르다. 당신은 설거지를 준비하기 위해서, 타임세일 Q번에 대해, 요리사가 어떤 가치의 접시를 회수하는지 알고 싶다. 각각의 손님이 타임세일 직전에 가지고 있는 접시의 정보와, 타임세일에 제공될 접시의 정보가 주어졌을 때, 요리사가 회수하는 각 접시의 가치를 구하는 프로그램을 작성하라. (추가 사항) Si = Ti 인 경우, 손님 Si 만이, 번째 행동을 진행하게 된다. Input 표준 입력으로, 다음의 데이터가 들어온다. 첫째 줄에는, 정수 N, Q가 공백으로 구분되어 들어온다. 이는, 손님의 수가 N 명이며, 타임세일에 제공될 접시의 수가 Q개 라는 것을 의미한다. 다음 N 개의 줄의 i번째 줄( i N )에는, 정수 Xi 가 입력으로 들어온다. 이는, 손님 i가 타임세일 직전에 가치 Xi 의 접시를 가지고 있다는 것을 의미한다. 다음 Q개의 줄의 i번째 줄에는, 정수 Si, Ti, Pi 가 공백으로 구분되어 들어온다. 이는, io번째 제공되는 접시가 (Si, Ti, Pi )로 표시됨을 의미한다. Output 출력은 Q개의 줄로 되어있다. 표준 출력에 i번째 줄 ( i Q)에, i번째로 요리사가 회수하는 접시의 가치를 의미하는 정수를 출력하여라. Constraints 모든 입력데이터는 다음의 조건을 만족한다. Page 5 of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo N 00 000 Q 5 000 X i 000 000 000 ( i N) S i N ( i Q) T i N ( i Q) O i 000 000 000 ( i Q) Subtask (5 points) 다음의조건을만족한다. N 000 Q 000 Subtask (5 points) 다음의조건을만족한다. S i = ( i Q) T i = N ( i Q) Subtask (80 points) 추가제한조건이없다. Examples 6 8 6 5 9 5 6 5 8 9 8 8 6 5 손님 부터손님 6 이가지고있는접시의가치는, 각각의접시가제공된후다음과같이바뀐다. 번째접시가제공된후, 8, 5, 6,, 5, 9 번째접시가제공된후, 8, 5, 6,,, 5 번째접시가제공된후,, 5, 6,,, 5 번째접시가제공된후,, 5, 6,,, 5 Page 6 of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo 5 번째접시가제공된후,, 5, 6,,, 5 6 번째접시가제공된후,, 5, 5,,, 번째접시가제공된후,, 5,,,, 5 5 입력예제 는, Subtask 의조건을만족한다. 0 0 9 5 8 9 0 6 8 5 9 0 8 0 6 8 6 6 9 6 9 6 9 0 8 0 9 Page of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo This page is intentionally left blank Page 8 of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo Problem C. Telegraph Input file: Output file: Time limit: Memory limit: second 56 megabytes JOI군도는, 태평양에 떠있는 작은 섬나라이다. JOI군도에는, N 개의 섬이 있고, 부터 N 까지의 번호가 붙어 있다. JOI군도는, 섬끼리 통신을 주로 무선통신을 한다. 각각의 섬에는 전파의 발신기와 수신기가 하나씩 있다. 발신기는 전방향으로 전파를 발신하는 것이 가능하지만, 수신기는 특정한 방향에서 오는 전파밖에 받지 못한다. 그래서, 각각의 수신기는, 특정한 하나의 섬에서 밖에 전파를 수신하지 못한다. 단, 수신기의 방향을 바꾸는 것으로, 어느 섬에서 전파를 수신할 것인지 바꾸는 것은 가능하다. 현재, 섬 i( i N )의 수신기는 섬 Ai (Ai 6= i)에서 오는 전파를 수신하는 것이 가능하다. 그리고, 섬 i의 수신기의 방향을 바꾸는데 드는 비용은, 어느 방향으로 바꾸든 Ci 이다. JOI군도에는, 공공사업으로 전보 서비스를 하고 있다. 섬 i ( i N )에서, 전파를 섬 j ( j N, j 6= i) 의 수신기가 받는 것이 가능 할 때, 섬 i에서 섬 j에 무선통신을 통해 전보를 보내는 것이 가능하다. 그리고, 전보는 몇개의 섬을 경유해도 된다. 즉, 섬 i, 섬 j, 섬 k ( i, j, k N, i, j, k는 서로 다르다.)에 대해, 섬 i 에서 섬 j에 전보를 보낼 수 있고, 섬 j에서 섬 k에 전보를 보낼 수 있으면, 섬 i에서 섬 k에 전보를 보낼 수 도 있다. 무선통신 이외에 방법으로 전보를 보내는것은 불가능하다. JOI군도의 통신장관인 당신은, 임의의 섬에서 임의의 섬으로 정보를 보낼수 있도록 하고 싶다. 그러기 위해서, 몇개의 섬의 수신기의 방향을 바꿔야 할 수도 있다. 몇개의 섬의 수신기의 방향을 바꾸는데 드는 비용은, 각각의 수신기의 방향을 바꾸는 데 쓰는 비용의 총합이다. 임의의 섬에서 임의의 섬으로 전보를 보낼 수 있도록 하기 위해 드는 비용의 최소치를 계산하여라. JOI 제도의 섬의 수와 각각의 섬의 수신기에 대한 정보가 주어졌을 때, 임의의 섬에서 임의의 섬으로 전보를 보낼 수 있도록 하기 위해 드는 비용의 최소치를 구하는 프로그램을 작성하라. Input 표준 입력으로 다음의 데이터가 들어온다. 첫째 줄에는, 정수 N 이 들어온다. 이것은, JOI군도에 N 개의 섬이 있다는 것을 의미한다. 다음 N 개의 줄의 i번째 줄( i N )에는, 정수 Ai, Ci 가 공백으로 구분되어 들어온다. 이는, 섬 i의 수신기는, 현재 섬 Ai 에서 전파를 수신하는 것이 가능하고, 방향을 바꾸는데 드는 비용이 Ci 라는 것을 의미한다. Output 표준 출력에, 임의의 섬에서 임의의 섬으로 전보를 보낼 수 있게 하는 비용의 최솟값을 첫째 줄에 출력하여라. Constraints 모든 입력데이터는 다음의 조건을 만족한다. N 00 000 Ai N ( i N ) Ai 6= i ( i N ) Ci 000 000 000 ( i N ) Subtask (0 points) 다음의 조건을 만족한다. Page 9 of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo N 0 Subtask (0 points) 다음의 조건을 만족한다. N 5 Subtask (0 points) 다음의 조건을 만족한다. N 000 Subtask (0 points) 추가 제한조건이 없다. Examples 섬 의 수신기의 방향을 바꿔, 섬 에서 오는 전파를 받을수 있게 한다. 이렇게 하면 임의의 섬에서 임의의 섬으로 전보를 보내는 것이 가능하고, 비용은 가 된다. 어떻게 수신기의 방향을 바꿔도 비용을 보다 낮추는 것은 불가능하기 때문에, 를 출력한다. 5 6 일단, 섬 의 수신기의 방향을 바꿔 섬 에서 오는 전파를 받을수 있게 한다. 그리고, 섬 의 수신기의 방향을 바꿔 섬 에서 오는 전파를 받을 수 있게 한다. 이렇게 하면 임의의 섬에서 임의의 섬으로 전보를 보내는 것이 가능하고, 비용은 + = 5가 된다. 어떻게 수신기의 방향을 바꿔도 비용을 5보다 낮추는 것은 불가능하기 때문에, 5를 출력한다. 섬 과 섬 의 수신기의 방향을 바꾸면 된다. 0 Page 0 of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo 어떤섬의수신기의방향도바꾸지않아도된다. Page of
Japanese Olympiad in Informatics 05/06 Spring Training Camp/Qualifying Trial Contest Day, March 9 5, 06, Komaba/Yoyogi, Tokyo This page is intentionally left blank Page of