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


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


 

ACM-ICPC 2009년도 기출 _ Candy War

Programming/Algorithm 2010. 10. 1. 17:06

알고리즘 유치원 선생님인 영희는 간식시간이 되자 아이들에게 사탕을 나누어 주려고 하였다. 하지만 욕심 많고 제멋대로인 유치원 아이들은 차례대로 받으라는 선생님의 말을 무시한 채 마구잡이로 사탕을 집어 갔고 많은 사탕을 집어 간 아이가 있는가 하면 사탕을 거의 차지하지 못하고 우는 아이도 있었다.
말로 타일러도 아이들이 말을 듣지 않자 영희는 한 가지 놀이를 제안했다. 일단 모든 아이들이 원으로 둘러 앉는다. 그리고 모든 아이들은 동시에 자기가 가지고 있는 사탕의 절반을 오른쪽 아이에게 준다. 만약 이 결과 홀수개의 사탕을 가지게 된 아이가 있을 경우 선생님이 한 개를 보충해 짝수로 만들어 주기로 했다. 흥미로워 보이는 이 놀이에 아이 들은 참여 했고 이 과정을 몇 번 거치자 자연스럽게 모든 아이들이 같은 수의 사탕을 가지게 되어 소란은 종료되었다.
자기가 가진 사탕의 반을 옆에 오른쪽에 앉은 아이에게 주는 과정과 선생님이 사탕을 보충해 주는 과정을 묶어서 1순환이라고 할 때 몇 번의 순환을 거치면 모든 아이들이 같은 수의 사탕을 가지게 되는지 계산 해 보자. 단, 처음부터 홀수개의 사탕을 가지고 있으면 선생님이 짝수로 보충을 먼저 해주며 이 경우 순환수에 들어가지 않는다. 선생님은 충분한 수의 사탕을 갖고 있다고 가정하자.

입력

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각각의 테스트 케이스의 첫 줄에는 아이의 인원 N (1 ≤N ≤ 10)이 주어지고 그 다음 줄에는 각 아이들이 초기에 가지고 있는 사탕의 개수 Ci ( 1 ≤ i ≤ N  ,  1 ≤ Ci≤ 30)가 주어진다. 분배 시 C1의 오른쪽에는 C 2가, C 2의 오른쪽에는 C 3가…… 같은 식으로 앉게 되며 C N의 오른쪽에는 C 1이 앉게 된다.

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대하여 모든 아이가 같은 개수의 사탕을 가질 때까지 몇 순환이 걸리는지 출력하시오.

Sample Input

4
5
2 4 7 8 9
1
9
6
10 5 13 2 7 8
4
3 4 4 3

Output for the Sample Input

6
0
4
0

"동시에" 라는 키워드에 주목 해야 한다.
예컨데, 2번 아이가 3번 아이에게 사탕을 줄 때는 1 번 아이에게 사탕을 받기 전이다. 
필자는 바보 같이 절반주고 나서 그 절반을 감하는 것을 깜박해서 뻘짓햇다는 후문이...;;

 

'Programming > Algorithm' 카테고리의 다른 글

ACM-ICPC 2010년도 O.T. 문제 2 - Delivery  (2) 2010.10.04
ACM-ICPC 2010년도 O.T. 문제 1 - Ducci Sequence  (0) 2010.10.04
암호 깨기 (Crypt Kicker)  (0) 2010.09.30
동맹 휴업 (Hartal)  (0) 2010.09.03
포커 패(Poker Hands)  (0) 2010.09.01

암호 깨기 (Crypt Kicker)

Programming/Algorithm 2010. 9. 30. 19:07

텍스트를 암호화하는 방법 중에 보안상 취약하긴 하지만 흔하게 쓰이는 방법으로 알파벳 글자를 다른 글자로 돌리는 방법이 있다. 즉 알파벳의 각 글자를 다른 글자로 치환한다. 암호화된 것을 다시 원래대로 되돌릴 수 있으려면 두 개의 서로 다른 글자가 같은 글자로 치환되지 않아야 한다.

암호화된 텍스트가 한 줄 이상 입력되는데, 각 줄마다 서로 다른 치환 방법이 적용된다고 가정하자.
암호화 이전의 텍스트에 있는 단어는 모두 주어진 사전에 들어있는 단어라고 가정하고, 암호화된 텍스트를 해독하여 원래 텍스트를 알아내자.

입력

입력은 한 개의 정수 n이 들어있는 행으로 시작되며 그 다음 줄부터는 한 줄에 하나씩 n개의 소문자로 쓰인 단어들이 알파벳 순으로 입력된다. 이 n개의 단어들은 복호화된 텍스트에 들어갈 수 있는 단어로 구성된 사전이다. 사전 뒤에는 몇 줄의 텍스트가 입력된다. 각 줄은 앞에서 설명했던 방법에 따라 암호화된다.

사전에 들어갈 수 있는 단어의 개수는 1,000개를 넘지 않는다. 단어의 길이는 16글자를 넘지 않는다. 암호화된 텍스트에는 소문자와 스페이스만 들어가며 한 줄의 길이는 80글자를 넘어가지 않는다.

출력

각 줄을 복호화하여 표준 출력으로 출력한다. 여러 문장으로 복호화될 수 있다면 그 중 아무 결과나 출력하면 된다. 가능한 풀이가 없다면 알파벳 모든 문자를 *로 바꾼다.

입력 예
6
and
dick
jane
puff
spot
yertle
bjvg xsb hxsn  xsb   qymm   xsb rqat     xsb   pnetfn
xxxx yyy zzzz www  yyyy    aaa bbbb   ccc   dddddd

출력 예
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

문자열을 저장할때 error C2106 : '=' : 왼쪽 피연산자는 l-value이어야 합니다. 오류가 뜰경우
> strcpy를 이용하라.

1.글자수가 사전 단어, 암호화된 텍스트 양쪽 다 유일할때는 반드시 그 단어로 치환 되어야 합니다
2.암호화된 텍스트에 있는 글자수가 사전에 없다면 복호화가 불가능 합니다.(* 표시해야함)
3.2개 이상 존재하는 단어들은 1번 과정에서 복호화된 문자들부터 하나씩 처리해나가도록 합시다...

 



'Programming > Algorithm' 카테고리의 다른 글

ACM-ICPC 2010년도 O.T. 문제 1 - Ducci Sequence  (0) 2010.10.04
ACM-ICPC 2009년도 기출 _ Candy War  (0) 2010.10.01
동맹 휴업 (Hartal)  (0) 2010.09.03
포커 패(Poker Hands)  (0) 2010.09.01
유쾌한 점퍼(Jolly Jumpers)  (0) 2010.08.31