천상낙원

주근깨 (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
,

피보나치 수의 개수 (How many Fibs?)

ACM 퀴즈
invalid-file


피보나치 수는 다음과 같은 식으로 정의된다.

f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2) (n≥3)

a와 b라는 수가 주어졌을 때 [a, b] 구간에 있는 피보나치 수의 개수를 계산하라.


입력
입력에는 여러 개의 테스트 케이스가 들어있다. 각 테스트 케이스는 두 개의 음이 아닌 정수 a와 b가 입력될 때 앞부분에 불필요한 0은 전혀 붙지 않는다.

출력
각 테스트 케이스마다 a≤f(i)≤b인 피보나치 수 f(i)의 개수를 한 줄에 하나씩 출력한다.

입력예
10 100
1234567890 9876543210
0 0

출력예
5
4

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

빛, 더 많은 빛 (Light, More Light)  (0) 2006.02.05
자리올림 (Primary Arithmetic)  (0) 2006.01.19
비토와 친척들 (Vito's family)  (0) 2006.01.14
,

자리올림 (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
,

비토와 친척들 (Vito's family)

ACM 퀴즈
invalid-file


유명한 갱스터인 비토 데드스톤이 뉴욕으로 이사를 간다. 뉴욕에는 그의 가족들이 매우 많이 살고 있는데 그들은 모두 라마피아 거리에 살고 있다. 그는 친척들을 자주 만나러 갈 계획이기 때문에 친척들과 가까운 곳에 집을 구하기로 했다.

비토는 모든 친척집과의 거리 총합이 가장 작은 곳에 집을 구하고 싶어하는데, 하필이면 당신에게 그 문제를 해결하기 위한 프로그램을 만들어내라는 협박 편지를 보내왔다.


입력
입력은 여러 개의 테스트 케이스로 구성된다. 첫번째 줄에는 테스트 케이스의 개수가 들어있다. 각 테스트 케이스마다 친척집의 수를 나타내는 정수 r(0 < r < 500)과 각 친척집의 번지수를 나타내는 정수 s1, s2, ..., si, ... sr(0 < si < 30,000)이 입력된다. 친척 중에는 같은 번지에 살고 있는 사람들도 있다는 점에 주의하자.

출력
각 테스트 케이스에 대해 비토가 원하는 위치에 집을 구했을 경우에 그 집으로부터 각 친척집까지의 거리의 총합을 출력해야 한다. 번지 수가 si와 sj인 두 집 사이의 거리는 dij = | si - sj |로 구한다.

입력 예
2
2 2 4
3 2 4 6

출력 예
2
4

참고사항
1. 두 친척집 사이에 비토의 집이 있다면 거리의 총합은 동일하다. 또한 최소값을 갖는다.
2. 같은 번지에 살고 있는 사람들도 각각 거리를 구해 더해주어야한다.

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

자리올림 (Primary Arithmetic)  (0) 2006.01.19
WERTYU  (0) 2006.01.13
유쾌한 점퍼 (Jolly jumpers)  (2) 2006.01.12
,

WERTYU

ACM 퀴즈
invalid-file



타이핑을 하다보면 키보드에서 양손을 모두 원래 위치보다 오른쪽으로 한 칸 이동한 상태에서 키를 눌러서 오타가 나오는 경우가 종종 있다. 그러면 'Q'는 'W', 'J'는 'K' 같은 식으로 오른쪽에 있는 키가 입력된다. 이런 식으로 입력된 메시지가 주어졌을 때 원래 메시지로 복구시켜야 하는 임무가 주어졌다.


입력
입력은 여러 줄의 텍스트로 구성된다. 각 줄에는 숫자, 스페이스, 대문자('Q', 'A', 'Z' 제외), 위에 나와있는 구두 기호(역따옴표(`)제외)가 들어갈 수 있다. 단어가 붙어있는 키(Tab, BackSp, Control 등)는 입력에 들어있지 않다.

출력
위에 나와있는 QWERTY 키보드를 기준으로 하여 각 글자나 기호를 바로 왼쪽에 있는 키에 해당하는 글자나 기호로 바꿔야 한다. 입력에 있는 스페이스는 그대로 둔다.

입력예
O S, GOMR YPFSU/

출력예
I AM FINE TODAY.

참고사항
1. 시간초과에 유의한다.

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

비토와 친척들 (Vito's family)  (0) 2006.01.14
유쾌한 점퍼 (Jolly jumpers)  (2) 2006.01.12
The 3n + 1 problem  (7) 2006.01.12
,

티스토리툴바