4
1 1 0 0
1 1 0
0 0
1
10 <- 히드라가 총 열 마리
1 1 1 1 1 2 2 3 3 4 <- 1번 멀티에 히드라가 다섯 마리 있다. 8번 히드라는 3번 멀티에 있다.이 문제는 국제 정보 올림피아드를 패러디한 것이며, 저작권은 이 홈페이지 운영자가 가집니다. 문제가 정보 올림피아드 연습용 문제/예상 문제만한 완성도를 갖춘 것은 아니기 때문에, 그냥 유머로 즐겨 주세요. :-)
질럿은 프로토스의 기본 유닛으로, 맷집만 믿고 무작정 달려가 목표물을 팔뚝에 있는 칼날로 열나게 때리는 유닛이다. 우리는 질럿을 잔뜩 몰고 초반 러시를 시도했다. 그런데 상대 역시 프로토스이고, 대등한 숫자의 질럿으로 수비를 하고 있었다. 게이머는 질럿들을 선택하며 공격 명력을 내린다. 하지만 질럿들은 이런 명령만 내려서는, 구체적으로 누가 누구를 공격해야 할지 알지 못한다.
두 편이 모두 N마리의 질럿이 서로 다른 위치에 있다. 우리 편의 각 질럿이 정확하게 서로 다른 상대편 질럿을 맡되, 각 질럿들 사이 거리의 총합이 최소가 되도록 질럿을 짝지어 주는 프로그램을 작성하라. 단, 맵은 허허벌판이어서 장애물은 아무것도 없다.
입력 파일 이름은 zealot.in이다. 첫줄에는 질럿 숫자 N(2<=N<=500)이 있고 다음 N줄에는 우리편 i째 질럿의 x, y 좌표가 들어있다. 그 뒤에는 상대편 질럿 N마리의 위치가 뒤따른다. 모든 좌표는 -200부터 200 사이인 정수이다.
3 0 0 1 2 0 5 2 3 3 5 0 -2
출력 파일 이름은 zealot.out이다. N줄을 출력하여, 각 줄에는 우리편 i째 질럿에 대응하는 상대편 질럿의 번호를 출력하면 된다. (1...N) 다시 한번 말하지만 각 질럿들이 맡은 상대편 질럿을 찾아가는데 드는 거리의 총합이 최소가 되어야 한다.
2 3 1
프로그램의 실행 제한 시간은 3초이다. 심사 때 부분 점수는 없다.
저그의 대공 공격 유닛인 뮤탈리스크는 한 번 공격으로 근처에 있는 목표물에까지 약간 타격을 줄 수 있다. 우리는 이를 흔히 쓰리 쿠션이라고 부른다. 뮤탈리스크가 어떤 건물을 한번 공격했다. 그러면 그 건물(제 1 건물)은 c1만큼 타격을 입으며, 제 2 건물은 c2만큼, 마지막으로 제 3 건물은 c3만큼 타격을 입는다. 어떤 경우건 c1>c2>c3임이 보장된다. 건물은 체력이 0이 되면 파괴돼 없어진다. 제 2와 제 3 건물은 다음과 같은 조건대로 선택할 수 있다.
체력이 다른 건물들이 일렬로 늘어서 있다. 인접한 건물 사이의 거리는 1이다. 우리는 이 "쓰리 쿠션"을 최대한 활용하여 최소한의 공격 횟수로 모든 건물을 파괴하고 싶다. 건물은 시간이 지나도 공격을 당하지 않는 한 체력이 변하지 않는다.
입력 파일 이름은 three.in이다. 첫 줄에는 뮤탈리스크의 공격력 c1, c2, c3 (1 <= c1 < c2 < c3 <= 30)가 들어있다. 둘째줄에는 건물의 개수(정확히 말해서 줄의 개수) n이 있다. (1<=n<=256) 그리고 다음 n줄에는 각 건물의 체력 h (0<=h<=3000)이 왼쪽부터 나온다.
9 3 1 5 2 10 5 0 6
출력 파일 이름은 three.out이다. 첫 줄에는 모든 건물을 파괴하기 위해 필요한 최소한의 공격 횟수 o를 출력한다. 다음 o줄에는 뮤탈리스크의 공격을 나타내는 숫자 세 개를 적는다. 첫째 숫자는 제 1 건물의 번호이다.(1이 가장 왼쪽 건물) 둘째 숫자는 제 1 건물에 대한 제 2 건물의 상대 위치로, -1(왼쪽) 아니면 1이다. 셋째 숫자는 둘째 건물에 대한 셋째 건물의 상대 위치로, -2, -1, 1, 2 중 하나가 될 수 있다. 다만, 주변에 건물이 없어서 둘째 공격이나 셋째 공격을 할 수 없었다면 그 자리는 그냥 0으로 채우도록 한다.
3 <- 2 10 5 0 6 2 1 -2 <- 1 1 2 0 6 1 1 1 <- 0 0 0 0 6 5 0 0 <- 0 0 0 0 0
프로그램의 실행 제한 시간은 4초이다. 뮤탈리스크가 규칙을 벗어나는 공격을 시도하면 그 답안의 점수는 0점이 된다. 모든 건물이 파괴되어 있지 않아도 0점을 받는다. 문제 지시 사항을 바르게 지켰다면 점수는 다음과 같이 계산된다.
최적해(실제로 가장 적은 공격 횟수)가 A, 여러분이 구한 횟수가 B라고 하자.
랜덤 유저를 맞아 섬 맵에서 일대일 게임을 시작한 저그 유저 왕저그 씨. 여느 저그 플레이어와 마찬가지로 초반에 오버로드로 적진 정찰을 시작한다. 그런데 상대편은 랜덤 테란이었고, 운나쁘게도 적진에 도달하기도 전에 오버로드는 마린을 만나고 만다. 마린은 오버로드를 일점사하고, 오버로드는 필사적으로 물 위로 도망치는데... 당신은 왕저그 씨를 도와야 한다.
지도는 기본적으로 정사각형 격자 모양이다. 지형은 땅(G) 아니면 물(W)이며, 언덕 같은 것은 없다. 오버로드는 어디든지 다닐 수 있지만 마린은 물 위에는 다닐 수 없다. 우리가 조종해야 하는 오버로드는 한 마리이며, 적인 마린은 최소 1명에서 최대 N명까지 있을 수 있다. 지도에서 마린은 M으로 표시되며, 처음에 마린이 있는 곳은 당연히 땅(G)이다.
오버로드는 한 번에 상하좌우 한 칸씩 움직일 수 있다. 반면 마린은 한 번에 5x5 범위 어디든지 움직일 수 있다(아래 그림에서 짙은 회색). 마린의 무기인 가우스 소총은 마린을 중심으로 하여 9x9범위에 있는 오버로드를 공격할 수 있다(아래 그림에서 옅은 회색).
|
W |
|
|||||||
|
W |
|
|||||||
|
W |
|
|||||||
|
M |
W |
|
||||||
|
W |
|
|||||||
|
W |
G |
|||||||
|
W |
|
|||||||
|
|
|
편의상 마린은 범위 안에만 들면 물을 뛰어넘을 수도 있다고 가정하자. 예를 들어 마린은 위와 같은 상황에서도 G가 있는 곳으로 이동할 수 있다.
이 문제의 풀이는 라이브러리를 사용하여 채점 프로그램과 의사 소통하는 방식으로 진행된다. 당신은 지도를 읽어들여 지형과, 오버로드와 마린이 있는 곳을 파악한 뒤, 라이브러리의 start()함수를 호출한다. 그 다음부터 오버로드가 먼저 움직이면, 마린들이 오버로드를 따라 움직이면서 한 차례가 끝난다. 마린들이 이동해서 오버로드가 자기 공격거리 안에 들면, 그런 마린의 수만큼 오버로드의 에너지가 줄어들게 된다. 오버로드는 에너지가 0이 되면 죽는다.
이번 문제는 파일로 입출력하는 게 아니라 라이브러리와 의사 소통을 하면서 오버로드를 조종하는 것이다. overlord라는 라이브러리가 제공된다.
int start();
function start : integer;
가장 먼저 호출해야 한다. 이 함수는 지금 맵에 있는 마린 수를 되돌려준다. 마린 수 M은 1<= M <= 100이다.
void get_size(int *x, int *y);
procedure get_size(var x,y: integer);
이번 심사에서 쓰이는 지도의 크기를 x, y에 되돌려 준다. (15 <= x,y <= 150)
int get_at(int x, int y);
function get_at(x, y: integer);
지도의 x, y위치에 현재 무엇이 있는지 되돌려준다. 좌표는 1부터 시작한다. -1은 바다, 0은 땅, 1부터 M까지의 수는 여기에 그 번호에 해당하는 마린이 있음을 나타낸다. (물론 땅임)
게임 초기에는 모든 마린이 제각기 다른 위치에 있지만, 게임이 진행되고 나서는 한 곳에 여러 마린이 동시에 있을 수도 있게 된다. 그러므로 수험자는 게임이 시작되고 나서는 뒤에서 설명할 get_marine_pos로 각 마린들의 위치를 파악하고 있어야 한다.
void get_overlord_pos(int *x, int *y);
procedure get_overlord_pos(var x,y: integer);
현재 오버로드의 위치를 되돌린다. 좌표는 1부터 시작한다.
int move_overlord(char dir);
function move_overlord(dir: char): integer;
실제로 게임을 진행하는 함수로, 오버로드를 옮긴다. dir은 'U', 'D', 'L', 'R', 'H'중 하나이다. H는 오버로드를 움직이지 않고 그냥 두겠다는 뜻이다.
오버로드가 움직이고 나면 컴퓨터 마린들도 한 번씩 움직인다. 몇 번째 마린이 위치를 어디로 옮겼는지 알려면 아래에 나오는 get_marine_dir함수를 호출하도록 한다. 그리고 이 시점에서 오버로드를 공격할 수 있는 마린의 수만큼 오버로드는 체력이 1씩 감소하게 된다.
이 함수의 리턴값은 다음과 같다.
void get_marine_dir(int num, int *x, int *y);
procedure get_marine_dir(num: integer, var x,y: integer);
num째 마린이 가장 최근에 move_overlord()함수 호출 후 얼마만큼 움직였는지를 x, y에 저장해 준다. (-2 <= x, y <= 2) x와 y는 이전 위치에 대한 상대 좌표이다. num은 1부터 시작하는 정수이다.
int get_energy();
function get_energy: integer;
지금 오버로드의 에너지를 되돌린다. (0<=n<=200) 함수값이 0이면 오버로드는 죽은 것이다. 게임을 처음 시작할 때 오버로드의 에너지를 확인하기 위해 호출해도 되고, 게임 도중에 오버로드가 타격을 어느정도 입었는지 알기 위해서 호출해도 된다.
이 문제에서 특별히 출력해야 할 사항은 없다. move_overlord()가 1을 되돌릴 때까지 오버로드를 잘 조종하기만 하면 된다.
패스트 다템이란, 상대방이 디텍팅 능력이 제대로 갖춰지지 않았을 때 소수의 다크템플러를 빨리 러쉬시켜 승부를 보는 전술이다. 이번 문제는 이것을 좀더 확장하여, 최대한 빠르게 원하는 갯수만큼 다크템플러를 만드는 빌드 오더를 계산하는 프로그램을 작성하는 것이다.
초기에 당신은 미네랄이 50 있으며, 프로브 네 마리가 미네랄을 모으고 있다, 단 넥서스의 개수 N은 입력 파일에 따라 다르다. 맵의 자원은 무한이며, 초기 생명체 한계는 9*N이다.
여러분이 게임 도중 할 수 있는 동작은 다음과 같다.
입력 파일 이름은 darktem.in이다. 첫째 줄에는 게임 초기 넥서스 개수 N (1<=N<=12)이 있다. 둘째 줄에 만들고자 하는 다크템플러 수 K (1<=K<=128)가 들어있다. 단, 어떤 경우에도 게임 초기에는 미네랄 50에 프로브는 네 마리가 있다. 넥서스 개수는 처음 정신력 한계와, 한 번에 동시에 생산할 수 있는 프로브 수에만 영향을 준다.
2 4 <- (^^;;)
출력 파일 이름은 darktem.out이며, 적절한 빌드 오더가 들어있다. 명령이나 숫자는 빈 칸, 줄바꿈 문자, 탭 등 어떤 공백문자로 구분해도 좋다. 마지막 번째 다크템플러를 소환하는 명령(K)으로 출력을 끝내면 된다. 아래는 파일런과 어시밀레이터를 하나씩 짓는 빌드 오더의 한 예이다.
P 게임 시작하자마자 프로브 생산. 미네랄 0. 현재 프로브는 네 마리 25 25초 동안 모인 미네랄 양은 20*4 + 5*5 (이제 20초 후 프로브는 다섯 마리가 됐다.) = 105 P P 넥서스가 두 개이므로 프로브 두 마리를 동시에 생산시킨다. 미네랄 5 20 20*5 미네랄이 100이 모였다. Y 파일런 소환 15 프로브 일곱 마리가 15초 동안 모은 미네랄은 15*7=105 A 어시밀레이터 소환
섬 맵에 자리잡은 저그 기지에 N개의 멀티가 있다. 각 기지는 나이두스 동굴로 연결돼 있어서, 나이두스 동굴을 유한 번 거치기만 하면 어떤 기지에서도 본진으로 이동할 수 있다. 한 기지에 나이두스 동굴이 두 개 이상 있을 수도 물론 있다. 그리고 i째 멀티에는 H(i)마리의 히드라가 기지를 지키고 있다.
그런데 운나쁘게도 하필 히드라가 한 마리도 없던 본진이 공격을 받게 됐다. 본진에는 하이브, 그레이터 스파이어 등 각종 중요한 건물이 밀집해 있다. 여러분은 다른 곳에 있던 히드라들을 최대한 빨리 본진으로 옮겨야 한다.
히드라 한 마리가 나이두스 동굴 하나를 통과하여 다른 기지로 가는 데 걸리는 시간은 1이다. 동굴 하나에는 한 번에 히드라 한 마리만 들어갈 수 있다. 게이머의 컨트롤 속도는 무한대라고 생각하자. ^^;; 여러 곳에 있는 히드라들은 병목 현상을 최소화하면서 일사불란하게 움직여야 한다. 저그 기지를 보고 가장 효율적으로 히드라들을 지휘하는 방법을 계산하는 프로그램을 작성하라.
입력 파일 이름은 nydus.in이다. 첫줄에는 멀티의 개수 N (2<=N<=128)이 들어있다. 다음줄에는 본진과 N개의 멀티가 서로 나이두스 동굴로 연결돼 있는지의 여부가 N개의 숫자로 나와 있다. (1: 예, 0: 아니오) 그다음 N-1줄에는 1부터 N-1째 멀티에 대한 정보로, i째 멀티가 i+1째 멀티부터 마지막 N째 멀티와 연결돼 있는지의 여부가 나온다. 즉, 나이두스 동굴은 양방향으로 통하기 때문에 중복하는 정보는 제공하지 않는다는 말이다.
그다음 줄에는 히드라의 총 마릿수 M (1<=M<=2000)가 있고, 다음 줄에는 각 히드라가 초기에 자리잡고 있는 멀티 번호 H(i)가 나온다. 아래 입력 파일의 경우 본진과 멀티가 그림과 같이 연결돼 있다는 의미가 된다.
출력 파일 이름은 nydus.out이다. 첫 줄에는 모든 히드라가 본진으로 이동하는 데 걸리는 총 시간 T를 출력한다. 그리고 다음 T줄에는 그 시각에 행해지는 히드라의 동작을 모두 출력하도록 한다. 히드라 번호와, 그 히드라가 이동하는 멀티 번호를 한 쌍으로 하여 출력한다. 본진으로 이동하는 것은 숫자 0으로 표현하면 된다.
5 1 0 6 0 8 1 2 2 10 3 <- 1번 멀티에 있던 1번 히드라, 2번 멀티에 있던 6번 히드라가 본진에 도착. 2번 히드라는 2번 멀티로 이동 2 0 3 0 9 1 4 2 4 0 5 0 10 1 8 2 <- 이제 1번 멀티에 9, 10번: 2번 멀티에 8, 7번 히드라가 남았다. 9 0 7 0 <- 차례대로 본진으로 이동 8 0 10 0
이 프로그램의 실행 제한 시간은 3초이다. 출력 파일에 지금 히드라가 바로 이동할 수 없는 멀티로 이동하라는 지시가 있거나, 지시대로 하고도 모든 히드라가 본진에 있지 않으면 그 답안은 0점을 받는다. 일단 임무를 바르게 완수했다면, 점수는 다음과 같이 계산된다.
심사진이 알고 있는 가장 짧은 시간을 A라고 하고, 답안 프로그램이 모든 히드라를 옮기는 데 걸린 시간을 B라고 하자. 그러면,
테란의 황제를 꿈꾸고 있는 테란 유저 임 묘한 씨가 무한 맵에서 게임을 하고 있다. 그런데 가뜩이나 좁은 공간에 건물을 잔뜩 짓다 보니 SCV를 비롯한 자기 지상 유닛들이 기지를 나가지도 못하게 되어 버렸다. 그는 유닛 컨트롤에 비해 빌드를 잘 못해서 건물을 다 지은 SCV가 건물 사이에 갇히는 것과 같은 실수를 잘 저지른다. 임씨는 문득, 맵 모양을 보고 적합한 기지 모양을 계산해 주는 프로그램이 있으면 좋을 거라는 생각을 했다.
임 묘한 씨가 무한 맵에서 즐겨 쓰는 유닛은 배틀크루저+고스트+골리앗이다. 지도를 보고 임씨가 건물을 원하는 갯수만치 짓되, 건물을 가장 적은 횟수만큼 띄우고도 SCV가 A지점에서 B지점까지 갈 수 있도록 건물을 배치하는 프로그램을 작성하라. (물론 건물을 전혀 띄우지 않고도 길을 낼 수 있다면 더 좋음)
맵은 정사각형 격자 모양이며, 각 칸은 건물을 지을 수 있는 평지 G와 건물을 지을 수 없는 거친 땅 W로 나뉘어 있다. 우리가 지어야 하는 건물은 다음과 같은 모양을 가진 여섯 종류의 건물로 정해져 있다. 각 건물의 수효는 입력 데이터에 따라 다르다. 건물이 차지하는 곳에는 거친 땅이 없어야 한다. 건물끼리 서로 겹쳐서도 물론 안 된다. SCV도 거친 땅은 거쳐 갈 수 없다. 각 건물의 모양은 아래와 같다.
단, 모든 애드온 건물은 띄울 수 없다. SCV는 2x2칸을 차지하는 정사각형 모양이며, 한 번에 좌우상하로 한 칸씩 움직일 수 있다. 건물의 위치를 나타낼 때는 *표가 차지하는 곳을 나타내도록 하자. SCV의 위치 역시 좌측 상단의 위치로 나타내도록 한다.
입력 파일 이름은 build.in이다. 첫 줄에는 지도의 가로, 세로 크기를 나타내는 X, Y가 있다. (10<= X, Y <=150) 그리고 다음 Y줄에는 각 칸의 지형을 나타내는 문자 P, G가 공백 없이 X개만큼 있다. 그리고 SCV가 지나갈 수 있게 길을 내야 하는 통로의 시작과 끝은 A와 B로 표현된다. (입력 파일 예제에 나와있는 대로이다.) A와 B가 차지하는 곳에 건물이 있어서도 안 된다.
그 다음줄에는 A부터 F건물까지 지어야 하는 건물의 개수를 나타내는 정수 여섯 개가 있다. 0 <= B_A <= 20이며, 0 <= B_B <=4임이 보장된다. B_A에 해당하는 건물은 유닛 생산 건물인 바락, 팩토리, 스타포트+컨트롤 타워이며, B_B에 해당하는 건물은 그 밖의 아모리(아카데미), 사이언스 퍼실리티 건물이다.
본 문제에서는 입력 파일이 요구하는 건물을 일단 모두 지을 수 있게 맵이 배정된다. 또한, 띄울 수 없는 건물 때문에 SCV가 A에서 B로 이동하지 못하게 되는 일도 없다. 이 문제의 임무는 SCV가 최대한 다니기 쉽게 그 건물을 배치하는 것이다.
16 14 가로 16, 세로 14인 맵 PPPPPPWWWWWWPPPP PPPAAPWWWWWWPPPP WWPAAPPPPPPPPPPP WWPPPPPPWWWWWWWP WWWWPPPPPPPWWWWW WWWWPPPPPPPWWWWW WWWWPPPPPPPPPWWP PPPPPPPPPPPPPWWP BBPPPPPPPPPPPPPP BBPPPPPPPPPPPPPP PPPPPPPPPPPPPPPP PPPPPPPPPPWPPPPP PPPPPPPWPPWPPPPP PPPPPWPPPPWPPPPP 1 0 1 1 0 0 바락, 아모리, 스타포트를 하나씩 지어라는 요구
출력 파일 이름은 build.out이다. 여섯 줄을 출력하되, 각 줄에 A부터 F건물의 위치를 나타내는 좌표쌍을 출력하면 된다. 한 종류의 건물을 여러 개 짓는 경우가 있으므로, 한 종류의 건물에 대한 위치 출력이 끝나면 -1을 출력하도록 한다. 물론 그 건물을 지어라는 요구가 없었다면 그냥 -1만 출력하면 될 것이다. 좌측 상단 좌표는 1, 1이다.
12 11 -1 바락을 여기에 짓는다. 바락을 두 개 이상 지어야 한다면 -1 앞에 계속 다른 바락의 좌표를 출력하면 된다. -1 3 10 -1 아모리를 지을 위치 6 6 -1 스타포트를 지을 위치 -1 -1
이렇게 건물을 지으면 SCV는 스타포트 본건물을 한 번 띄워 주기만 하면 A 위치에서 B 위치로 이동할 수 있다. (물론 이 예제에서는 이렇게밖에 짓는 방법이 없다.) 위의 입출력 결과를 알기 쉽게 그림으로 나타내 보면 아래와 같다. 초록색은 거친 땅, 분홍색은 스타포트, 빨간색은 바락, 파란색은 아모리를 나타낸다.
프로그램의 실행 제한 시간은 5초이다. 심사 때 부분 점수는 없다.