천상낙원

개와 땅다람쥐 (Dog and Gopher)

ACM 퀴즈
넓은 마당에 개와 땅다람쥐가 있다. 개는 땅다람쥐를 잡아먹으려고 하고, 땅다람쥐는 땅 속에 있는 여러 개의 땅다람쥐 구멍을 통해서 안전하게 도망가려고 한다.

개와 땅다람쥐는 둘 다 수학 전공은 아니지만 그리 멍청하지도 않다. 땅다람쥐는 구멍 한 개를 정한 다음 그 구멍을 향해 일정한 속도로 직선으로 뛰어간다. 개는 보디 랭귀지를 파악하는데 매우 능숙해서 그 땅다람쥐가 어느 구멍으로 들어가기로 했는지 정확하게 파악할 수 있다. 개는 땅다람쥐의 두배의 속도로 같은 구멍으로 들어가기로 했는지 정확하게 파악할 수 있다. 개는 땅다람쥐의 두배의 속도로 같은 구멍을 향해 뛰어간다. 땅다람쥐는 개가 구멍에 먼저 도착하면 잡혀 먹히고, 그렇지 않으면 도망칠 수 있다.

땅다람쥐로부터, 어떤 구멍으로 숨어야 할지 결정하는데 도움을 줄만한 프로그램을 만들어 달라는 요청을 받았다.

입력
한 입력 파일에 여러 개의 테스트 케이스가 입력될 수 있다. 각 테스트 케이스의 첫째 줄에는 정수 한 개와 부동소수점수 네 개가 입력된다. 정수 n은 구멍의 개수를 나타낸다. 네 개의 부동소수점수는 땅다람쥐가 있는 위치의 (x, y) 좌표와 개가 있는 위치의 (x, y) 좌표를 나타낸다. 그 아래로는 n줄에 걸쳐서 땅다람쥐 구멍의 (x, y) 좌표를 나타내는 부동소수점수가 두 개씩 입력된다. 모든 거리는 미터 단위로, 밀리리터 단위까지 (즉 소수점 셋째 자리까지) 반올림한 값으로 입력된다. 파일 종료 문자가 입력되면 입력이 종료되며, 서로 다른 테스트 케이스 사이에는 빈 줄이 입력된다.

출력
각 테스트 케이스마다 한 줄씩 결과를 출력한다. 땅다람쥐가 도망칠 수 있으면 "The gopher can escape through the hole at (x, y)."라고 출력한다, 이때 밀리미터 단위까지 반올림한 값으로 구멍의 좌표를 출력한다. 두 개 이상의 구멍으로 도망칠 수 있으면 더 먼저 입력된 구멍을 출력한다. 한 테스트 케이스에 입력될 수 있는 구멍의 개수는 최대 1,000개고, 모든 좌표는 -10,000 이상, +10,000이하다.

입력예
1 1.000 1.000 2.000 2.000
1.500 1.500
2 2.000 2.000 1.000 1.000
1.500 1.500
2.500 2.500

출력예
The gopher cannot escape.
The gopher escape through the hole at (2.500, 2.500).

'ACM 퀴즈' 카테고리의 다른 글

ACM/ICPC 2005 서울대회 출제 문제  (0) 2006.09.14
체스판 위의 개미 (Ant on a Chessboard)  (0) 2006.03.26
큰 것이 더 똑똑하다? (Is Bigger Smarter?)  (0) 2006.03.26
,

체스판 위의 개미 (Ant on a Chessboard)

ACM 퀴즈
어느 날 앨리스라는 개미가 M × M 체스판에 올라갔다. 앨리스는 체스판에 있는 모든 셀을 방문하려고 한다. 그래서 판 한 쪽 구석에서 시작해서 체스판을 한 꺼풀씩 훑어나가기로 했다. 앨리스는 (1, 1)자리부터 움직이기 시작했다. 처음에는 한 칸 위로 올라간 다음, 오른쪽으로 한 칸 이동하고, 다시 한 칸 아래로 내려왔다. 그리고 나서 한 칸 오른쪽으로 움직여서 두 칸 위로 올라가고, 두 칸 왼쪽으로 움직였다. 이런 식으로 매번 한 행, 그리고 한 열씩을 더 움직였다. 예를 들어 앨리스가 25단계를 움직인 경로를 표시해보면 다음과 같다. 여기에서 각 숫자는 앨리스가 각 셀을 방문한 순서를 나타낸다.

2524232221
1011121320
9871419
2361518
1451617

앨리스는 여덟 번째 단계에서는 (2, 3) 위치에 있었고, 20번째 단계에서는 (5, 4) 위치에 있었다. 단계수가 주어졌을 때, 체스판이 매우 커서 움직일 수 있는 위치에 제한이 없다고 할 때, 앨리스의 위치를 결정하는 프로그램을 만들어야 한다.

입력
입력 파일은 여러 줄로 구성되는데, 각 줄마다 단계 번호를 나타내는 정수 N (1≤N≤10^9)이 하나씩 입력된다. 0이 입력되면 입력이 종료된다.

출력
입력된 값에 대해 해당 단계에서의 앨리스의 위치 (x, y)를 나타내는 두 정수를 출력한다. x는 열 번호, y는 행 번호를 나타낸다. 두 정수 사이에는 스페이스가 한 개 들어간다.

입력 예
8
20
25
0

출력 예
2 3
5 4
1 5

'ACM 퀴즈' 카테고리의 다른 글

개와 땅다람쥐 (Dog and Gopher)  (0) 2006.04.14
큰 것이 더 똑똑하다? (Is Bigger Smarter?)  (0) 2006.03.26
주근깨 (Freckles)  (0) 2006.03.04
,

큰 것이 더 똑똑하다? (Is Bigger Smarter?)

ACM 퀴즈
어떤 사람은 코끼리가 더 똑똑하다고 생각한다. 그런 생각이 틀렸다는 것을 증명하기 위해, 일련의 코끼리들을 분석해서 체중은 증가하는 순서로, IQ는 감소하는 순서로 된 가장 긴 순서열을 뽑아보자.

입력
한 줄에 한 마리씩, 여러 코끼리에 대한 정보가 입력된다. 파일 종료문자가 입력되면 입력이 끝난다. 각 코끼리에 대한 정보는 한 쌍의 정수로 입력되는데, 첫번째 정수는 체중을 킬로그램 단위로 나타낸 것이고, 두번째 정수는 IQ에 100을 곱한 값이다. 두 정수는 모두 1이상 1000이하다. 최대 1000마리의 코끼리에 대한 정보가 입력될 수 있다. 체중이 같은 코끼리가 두 마리 이상 있을 수 있으며, IQ가 같은 코끼리가 두 마리 이상 있을 수도 있다. 그리고 체중과 IQ가 모두 똑같을 수도 있다.

출력
첫째 줄에는 찾아낸 코끼리 순서열의 길이를 나타내는 정수 n을 출력한다. 그 밑으로는 n줄에 걸쳐서 각 코끼리를 찾아내는 양의 정수를 하나씩 출력한다. i번째 데이터 행으로 입력된 숫자들을 W[i], S[i]라고 표기해보자. 찾아낸 n마리의 코끼리의 순서열이 a[1], a[2], ..., a[n]이라면 다음과 같은 관계가 성립해야 한다.
W[a[1]] < W[a[2]] < ... < W[a[n]] 이고, S[a[1]] < S[a[2]] < ... < S[a[n]]
이러 관계가 만족되면서 n값은 최대한 큰 값이어야 한다. 모든 부등호에는 등호는 포함되지 않는다. 즉 체중은 반드시 증가해야 하며 (같으면 안됨), IQ는 감소해야 한다(IQ도 같으면 안됨).
조건이 맞으면 아무 답이나 출력해도 된다.

입력 예
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

출력 예
4
4
5
9
7

'ACM 퀴즈' 카테고리의 다른 글

체스판 위의 개미 (Ant on a Chessboard)  (0) 2006.03.26
주근깨 (Freckles)  (0) 2006.03.04
두 색으로 칠하기 (Bicoloring)  (0) 2006.02.22
,

주근깨 (Freckles)

ACM 퀴즈
invalid-file


딕 반 다이크 쇼라는 TV 프로그램에서, 딕의 아들 리치가 등에 있는 주근깨들을 연결하는 선을 그어서 자유의 종을 그리는 에피소드가 나온 적이 있다.

딕의 등을 여러 (x, y) 위치에 주근깨가 있는 평면이라고 생각해보자. 지금 우리는 리치가 최소한의 잉크로 점을 연결할 수 있는 방법을 알려줘야 한다. 리치는 점 사이에 직선을 긋는 식으로 점을 연결한다. 그리고 각 직선을 그을 때마다 펜을 등에서 뗀다. 이 일이 끝나고 나면 등에 있는 모든 주근깨가 연결되어야 한다.


입력
첫 줄에는 테스트 케이스의 개수를 나타내는 양의 정수가 입력되고, 그 다음 줄은 빈 줄이다.
각 테스트 케이스의 첫째 줄에는 0보다 크고 100이하의 정수 n이 입력되는데, 이 정수는 딕의 등에 있는 주근깨 개수를 뜻한다. 각 주근깨마다 한 줄씩 그 주근깨의 위치를 나타내는 좌표가 입력된다.
서로 다른 테스트 케이스 사이에는 빈 중이 하나씩 입력된다.

출력
각 테스트 케이스에 대해 모든 주근깨를 연결하기 위해 잉크로 연결해야 하는 선 길이의 합을 소수점 둘째 자리까지 출력한다. 서로 다른 테스트 케이스에 대한 결과 사이에는 빈 줄을 하나씩 출력한다.

입력예
1

3
1.0 1.0
2.0 2.0
2.0 4.0

출력예
3.41

참고사항
1. 각 점(노드)이 모두 연결된 그래프에서 최소신장트리를 구하는 문제.
2. 프림 알고리즘 / 크루스칼 알고리즘

'ACM 퀴즈' 카테고리의 다른 글

큰 것이 더 똑똑하다? (Is Bigger Smarter?)  (0) 2006.03.26
두 색으로 칠하기 (Bicoloring)  (0) 2006.02.22
작은 비숍 (Little Bishops)  (0) 2006.02.22
,

두 색으로 칠하기 (Bicoloring)

ACM 퀴즈
invalid-file


평면 위에 지도가 있을 때, 각 영역을 인접한 다른 영역과 구분할 수 있게 서로 다른 색으로 칠하고자 한다면, 네 가지 색만 있으면 된다는 4색 정리라는 것이 있다. 이 정리는 100년이 넘게 증명되지 않은 채로 남아 있다가 1976년에 컴퓨터의 도움을 받아서 증명될 수 있었다. 여기에서는 조금 더 쉬운 문제를 풀면 된다. 어떤 연결 그래프가 주어졌을 때 그 그래프를 두 색으로 칠할 수 있는지, 즉 모든 정점을 빨간색 또는 검은색으로 칠할 때 인접한 정점이 같은 색으로 칠해지지 않게 할 수 있는지 알아보자. 문제를 간단하게 하기 위해 그래프가 연결 그래프고, 무방향 그래프며, 자체 루프가 없다고(즉 (x,x)같이 한 정점에서 출발해서 그 정점으로 바로 연결되는 모서리가 없다고) 가정하자.


입력
여러 테스트 케이스가 입력될 수 있다. 각 테스트 케이스의 첫째 줄에는 정점의 개수 n(1≤n≤200)이 입력된다. 각 정점에는 0부터 n-1까지의 번호가 붙는다. 그 다음 줄에는 모서리의 개수 l이 입력된다. 그 밑으로 l개의 줄이 입력되며, 각 줄에는 모서리를 나타내는 두개의 정점 번호가 들어있다. n자리에 0이 입력되면 입력이 끝난 것이며, 그 줄은 처리하지 않는다.

출력
입력된 그래프가 두 색으로 칠할 수 있는 그래프인지 판단하고 아래 예에 나온 형식에 맞게 결과를 출력하라.

입력예
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0

출력예
NOT BICOLORABLE.
BICOLORABLE.

'ACM 퀴즈' 카테고리의 다른 글

주근깨 (Freckles)  (0) 2006.03.04
작은 비숍 (Little Bishops)  (0) 2006.02.22
빛, 더 많은 빛 (Light, More Light)  (0) 2006.02.05
,

작은 비숍 (Little Bishops)

ACM 퀴즈
invalid-file


비숍은 체스 게임에서 사용되는 말 가운데 하나로, 대각선 방향으로만 움직일 수 있다. 한 비숍이 다른 비숍이 움직일 수 있는 경로 위에 있으면 그 두 비숍은 "서로 공격할 수 있는 위치에 있다"고 부른다. 아래 그림에서 검은 칸은 B1이라는 비숍이 현재 공격할 수 있는 위치를 나타낸다. B1과 B2는 서로 공격할 수 있는 위치에 있지만 B2와 B3는 서로 공격할 수 없는 위치에 있다.


n과 k라는 두 정수가 주어졌을 때, n×n 체스판 위에 k개의 비숍을 서로 공격할 수 없는 위치에 배치하는 방법의 가지 수를 구하라.


입력
한 입력 파일에 여러 테스트케이스가 들어있을 수 있다. 각 테스트케이스가 한 줄을 차지하며, 각 줄마다 두 정수 n(1≤n≤8)과 k(1≤k≤n2)가 입력된다.

출력
각 테스트 케이스마다 주어진 크기의 체스판에 주어진 개수의 비숍을 서로 공격할 수 없는 위치에 배치하는 경우의 수를 출력한다. 결과는 한줄에 하나씩 출력한다. 이 값이 1015보다 작다고 가정해도 된다.

입력예
8 6
4 4
0 0

출력예
5599888
260

'ACM 퀴즈' 카테고리의 다른 글

두 색으로 칠하기 (Bicoloring)  (0) 2006.02.22
빛, 더 많은 빛 (Light, More Light)  (0) 2006.02.05
피보나치 수의 개수 (How many Fibs?)  (0) 2006.02.05
,

빛, 더 많은 빛 (Light, More Light)

ACM 퀴즈
invalid-file


우리 학교에는 복도 불을 켜고 끄는 마부라는 사람이 있다. 전구마다 불을 켜고 끄는 스위치가 있다. 불이 꺼져 있을 때 스위치를 누르면 불이 켜지고 다시 스위치를 누르면 불이 꺼진다. 처음에는 모든 전구가 꺼져 있다.

마부라는 사람은 특이한 행동을 한다. 복도에 n개의 전구가 있으면, 복도를 n번 왕복한다. i번째 갈때 그는 i로 나누어 떨어지는 위치에 있는 스위치만 누른다. 처음 위치로 돌아올 때는 아무 스위치도 건드리지 않는다. i번째 왕복은 복도를 한 번 갔다가 오는 것으로 정의된다. 마지막 전구의 최종 상태를 알아내자. 관연 그 전구는 켜져 있을까 아니면 꺼져 있을까?


입력
복도에 있는 n번째 전구를 나타내는 232-1이하의 정수가 입력된다. 0은 입력의 끝을 의미하며 그 값은 처리하지 않는다.

출력
그 전구가 켜져 있으면 "yes"를, 꺼져 있으면 "no"를 출력한다. 테스트 케이스마다 한 줄에 하나씩 출력한다.

입력예
3
6241
8191
0

출력예
no
yes
no

참고사항
1. 약수의 갯수가 홀수이면 전구가 켜지게 됩니다. 그러므로 n이 어떤 정수의 제곱이 되는지만 확인하면 됩니다.
2. 도데체 어떤 문제가 있어서 PE가 나오는지 모르겠습니다.

'ACM 퀴즈' 카테고리의 다른 글

작은 비숍 (Little Bishops)  (0) 2006.02.22
피보나치 수의 개수 (How many Fibs?)  (0) 2006.02.05
자리올림 (Primary Arithmetic)  (0) 2006.01.19
,

자리올림 (Primary Arithmetic)

ACM 퀴즈
invalid-file


초등학생들이 여러 자리 수의 덧셈을 배울 때는 한번에 한 자리씩 오른쪽에서 왼쪽으로 계산하도록 배운다. 그런데 그 자리 숫자의 합이 10을 넘어갈 때 윗자리 숫자에 1을 더해주는 것을 배울 때 많은 학생들이 힘들어한다. 일련의 덧셈 문제가 주어졌을 때 자리를 올리는 횟수를 세어서 선생님들이 학생을 가르치는데 도움을 줄 수 있는 프로그램을 만들어야 한다.


입력
각 행에는 열자리 미만의 부호가 없는 정수가 두개씩 입력된다. 마지막 줄에는 '0 0' 이 입력된다.

출력
마지막 줄을 제외한 각 줄에 대해 주어진 두 수를 더할 때 자리를 올려야 하는 횟수를 계산한 다음 아래에 주어진 형식대로 결과를 출력한다.

입력 예
123 456
555 555
123 594
0 0

출력 예
No carry operation.
3 carry operations.
1 carry operation.

참고사항
1. 각 자리수의 합에서 carry가 발생하는지 확인한다.
2. 자리수의 합을 구할 때 carry 또한 더해준다.
3. 둘중에 큰 수의 자리수까지 반복한다. (carry가 더해지므로 계속하여 carry가 발생할 수도 있다.)
4. 두개 이상이면 s를 뒤에 붙여줘야 함에 주의한다.

'ACM 퀴즈' 카테고리의 다른 글

피보나치 수의 개수 (How many Fibs?)  (0) 2006.02.05
비토와 친척들 (Vito's family)  (0) 2006.01.14
WERTYU  (0) 2006.01.13
,

티스토리툴바