ACM-ICPC 2010년도 인터넷 예선 문제 - 1 . Three Bowling Pin

Programming/Algorithm 2010. 10. 6. 23:51

acm 홈페이지에서 문제가 없어졌네요 ;
파일 없는데 .. 인쇄해 둔 것만 있구..

혹시 이거 문제 올렸다고 저작권 같은 문제가 생기진 않겠죠 ? ' - ' ) ;;;
뭐 이미 예선 결과도 다 나오고 했으니까 .. 올려도 문제 없을거라 믿고 올립니다.

어쨌든 이 문제는 볼링 점수 계산기를 짜는겁니다.
전체 10 프레임에 , 기본적으로 한 프레임당 투구를 두번하죠.
기본적으로 쓰러트린 핀의 수만큼 점수가 올라갑니다.
단 , 스페어 처리시 (프레임의 첫 투구에서는 핀을 다 쳐내지 못했는데 두번째 투구에서 남은 모든 핀을 쳐내는 것)  
해당 프레임이후 다음 투구까지의 점수가 + 됩니다.
스트라이크 처리시에는(프레임의 첫 투구에서 모든 핀을 쳐내는 것) 다음 두번의 투구까지의 점수가 +됩니다.
때문에 10번째 프레임에서 스페어 혹은 스트라이크가 나왔을때는 점수 계산을 위해 추가 투구가 필요합니다.

이게 기본 볼링룰이죠 ..
다만 이 문제에서는 볼링핀이 3개입니다.

보기 편하게 '/'로 각 프레임을 나눴을때
1 2 / 3 / 2 1 / 2 0 / 1 0  / 2 0 / 0 1 / 1 2 / 0 1 / 3 1 1

각 프레임의 점수는
6 / 6 / 5 / 2 / 1 / 2 / 1 / 3 / 1 / 5

따라서 최종 점수는
12 + 7 + 3 + 4 + 6 = 32

입력
입력의 첫째는 언제나 그렇듯 테스트케이스의 수( 1<= T <= 100 )를 입력합니다.
각 테스트 케이스의 첫 줄은 총 투구 횟수가 입력됩니다.
다음으로 그 투구 횟수만큼 각 투구 결과를 표기합니다. (위의 예에선 1 2 3 2 1 .... 3 1 1 )

출력
점수를 출력합니다.
단, 만약 핀은 3개인데 5개를 넘어뜨린다던가 하는 말도 안되는 입력 상황에서는 error를 출력합니다.

Problem A 였던만큼 가장 쉬운 문제였겠죠 ?
그냥.. 요구하는대로 짜면 됩니다.;;;;

ACM-ICPC 2010년도 O.T. 문제 2 - Delivery

Programming/Algorithm 2010. 10. 4. 14:59


우리네 농부들은 예로부터 콩을 수확하기 위해 땅을 파고 콩 세 알을 묻었다. 한 알은 땅에 사는 벌레가 먹고, 한 알은 하늘을 날아다니다 먹이를 찾아 들르는 새가 먹고, 나머지 남은 한 알이 자라면 인간이 거두어들여 먹었다.
ICPC(Impressive Crab Porridge Corporation)는 게살죽을 전문적으로 팔면서 동시에 이웃 사랑을 직접 실천하는 사회적 기업이다. 어운동에 위치한 ICPC는 주변 정남대학교와 가기대학교 학생들이 자주 찾는데 게살죽의 인상적인 맛을 알고 나서 단골이 된 학생이 많다. 몸이 안 좋을 때에 특히 생각나는데, 배달도 가능하다. 특히 밤샘 연구로 건강을 챙기기 힘든 주변 학교의 독거 대학원생들이 식사를 거르지 않도록 죽을 배달하는 무상 급식 사업을 벌이고 있다. 이는 나라의 미래에 조금이라도 보탬이 되고자 하는 사장 조송범씨의 사회적 기업 정신이다.
학생들의 생활에 조금이라도 보탬이 되도록 배달 아르바이트는 학생만을 대상으로 고용을 하는데, 맛있는 죽을 한정된 수의 고객에게 제공하다 보니 수지타산을 맞추기 빠듯하여 한 명의 배달원 만을 고용하고 있다. 이 한 명의 배달원이 주문 배달도 하면서 무상 급식 사업까지 도와준다. 특히 배달에 있어서 사장 조성범씨의 깐깐함이 묻어 나오는 것은 배달 순서에 있어서 선착순 원칙이다. 주문 배달에 대해서 먼저 주문한 사람에게 먼저 배달되어야 하며, 무상 급식에 있어서도 먼저 신청한 사람에게 먼저 배달되어야 한다. 단, 돈을 지불하는 주문 배달한 사람과 무상 급식을 신청한 사람의 순서는 무관하다. 예를 들어서, A, B, C의 순서로 배달 주문이 들어오고 X, Y, Z의 순서로 무상 급식 신청이 들어오게 되면 B는 반드시 A에게 배달된 다음에 배달되어야 하며 C 보다 먼저 배달을 받아야 하지만 X, Y, Z의 배달 순서와는 상관이 없다.
ICPC의 사회 서비스를 도와주기 위해, 한 명의 배달원이 배달 주문, 무상 급식 신청 두 가지 모두를 최단 거리로 배달할 수 있는 프로그램을 작성하시오. ICPC에서 출발하며 ICPC의 위치는 (0, 0)으로 가정한다.

입력

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트케이스의 첫 줄에는 배달 주문의 수와 무상 급식 신청의 수 N (1  N  20), M (1  M  20)이 공백 하나를 사이에 두고 주어진다. 그 다음 N 줄에 걸쳐 각 배달 주문의 위치가 순서대로 한 줄에 하나씩 좌표 (x, y)로 주어지고, 그 다음 M 줄에 걸쳐 각 무상 급식 신청 위치가 한 줄에 하나씩 좌표 (x, y)로 주어진다(0  x  100, 0  y  100, x, y 는 정수). x와 y는 하나의 공백을 사이에 두고 주어진다.

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대하여 한 명의 배달원이 두 종류의 배달을 마칠 수 있는 최단 거리를 출력하시오. 단, 소수점 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

Sample Input

3
2 3
1 1
2 1
1 0
2 0
3 0
4 5
35 53
19 15
43 59
21 37
35 77
81 26
23 65
95 52
76 45
4 1
74 41
80 65
74 99
93 99
82 89

Output for the Sample Input

5.0
407.8
165.2


 어렵다!! 단순하게 생각했다간 큰 코 다친다. 
현재 위치에서 가장 짧은곳 부터 가면 될 거 같지만,(탐욕적 알고리즘) 이 방법이 항상 최소의 값을 가진다고 단언 할 수 없다. 때문에 되추적(Back Tracking)같은 방법을 이용 해야 하는데,  되추적을 이용하려면 Tree 와 같은 자료구조를 형성해야 하는데 이게 만만치 않다. 포인터를 조작하는 일이다보니 엑세스 위반도 자주 일어난다.
실제 시험에 나왔다면 그냥 나중에 쉬운 문제들 풀고 시간남을때 한번 봐주는 문제.

필자는 OT시간땐 다 못풀고, 오기생겨서 집에서 알고리즘을 짜서 다음날 코딩을 해봤는데도 1~2시간 가량 디버그에 열중해야 했다. 역시 포인터,재귀는 편리하지만 어렵다 ㅠ

필자의 풀이의 과정을 말로 풀어보자면 이렇다.
1. 트리 클래스(구조체)형성
2. 루트 노드를 만들고
3. 재귀로 계속해서 노드를 생성한다.
4. 3에서 만약 weight(거리)가 지금까지의 최저값보다 크다면 해당 가지에서의 노드 생성을 중지한다
5. 트리가 완성되면 모든 과정을 중지한다.

ACM-ICPC 2010년도 O.T. 문제 1 - Ducci Sequence

Programming/Algorithm 2010. 10. 4. 14:18

A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers , the next n-tuple in the sequence is formed by taking the absolute differences of neighboring integers:
Ducci sequences either reach a tuple of zeros or fall into a periodic loop. For example, the 4-tuple sequence starting with takes 5 steps to reach the zeros tuple:

(8,11,2,7) -> (3,9,5,1) -> (6,4,4,2) -> (2,0,2,4) -> (2,2,2,2) -> (0,0,0,0).

The 5-tuple sequence starting with enters a loop after 2 steps:
Given an n-tuple of integers, write a program to decide if the sequence is reaching to a zeros tuple or a periodic loop.



Input

Your program is to read the input from standard input. The input consists of test cases. The number of test cases is given in the first line of the input. Each test case starts with a line containing an integer , which represents the size of a tuple in the Ducci sequences. In the following line, integers are given which represents the n-tuple of integers. The range of integers are from to . You may assume that the maximum number of steps of a Ducci sequence reaching zeros tuple or making a loop does not exceed 1,000.

Output

Your program is to write to standard output. Print exactly one line for each test case. Print LOOP if the Ducci sequence falls into a periodic loop, print ZERO if the Ducci sequence reaches to a zeros tuple.
The following shows sample input and output for four test cases.


Sample Input

4
4
8 11 2 7
5
4 2 0 2 0
7
0 0 0 0 0 0 0
6
1 2 3 1 2 3

Output for the Sample Input

ZERO
LOOP
ZERO
LOOP


비교적 간단한 문제.
그냥 설명 써진대로 수열 만들면 된다.