투 명 테 잎

두 자연수 N 과 P 를 가지고 다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자.

처음 출력하는 숫자는 N 이고, 두 번째 이후 출력하는 숫자들은 N 을 곱하고 P 로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N 에 을 N 을곱하고, 이 수를 P 로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N 을 곱하고 P 로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N 을 곱한 후 P 로 나눈 나머지를 출력한다. 이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다.

예를 들어서, N=67,P=31 인 경우를 생각해보자.

• 처음 출력되는 숫자는 67 이고,
• 두 번째로 출력되는 숫자는 67×67 =4489 를 31로 나눈 나머지 25 이다.
• 다음에는 25×67=1675 를 31 로 나눈 나머지 1 ,
• 다음에는 1×67=67 을 31 로 나눈 나머지 5 가 차례대로 출력된다.
• 다음에는 5×67=335를 31 로 나눈 나머지 25가 출력되는데, 이 수는 이미 이전에 출력된 수이다.

즉 이 과정을 반복하면, 처음 67을 제외하면 3개의 숫자 25, 1, 5가 계속 무한히 반복되게 된다.

또 다른 예로, N=9 , P=3 을 가지고 시작하면, 9×9=81 이고 3 으로 나눈 나머지는 0 이며, 0×3 =0 이고 3 으로 나눈 나머지도 0 이기 때문에 처음 9 를 제외하면 0 이 무한히 반복되게 된다.

N 과 P 를 입력받아 위와 같이 정의된 연산을 수행하였을 때, 반복되는 부분에 포함된 서로 다른 숫자의 개수를 구하는 프로그램을 작성하시오.

입력

출력

입출력 예

입력

67 31

출력 

3

입력

96 61

출력 

60

출처:2012 지역 본선 초등 2/5

KOI 전자에서는 건강에 좋고 맛있는 훈제오리구이 요리를 간편하게 만드는 인공지능 오븐을 개발하려고 한다. 인공지능 오븐을 사용하는 방법은 적당한 양의 오리 훈제 재료를 인공지능 오븐에 넣으면 된다. 그러면 인공지능 오븐은 오븐구이가 끝나는 시간을 분 단위로 자동적으로 계산한다.

또한, KOI 전자의 인공지능 오븐 앞면에는 사용자에게 훈제오리구이 요리가 끝나는 시각을 알려 주는 디지털 시계가 있다.

훈제오리구이를 시작하는 시각과 오븐구이를 하는 데 필요한 시간이 분단위로 주어졌을 때, 오븐구이가 끝나는 시각을 계산하는 프로그램을 작성하시오.

입력

• 첫 째 줄에는 현재 시각이 나온다. 현재 시각은 시 A (0 <= A <= 23) 와 분 B( 0 <= B <= 59) 가 정수로 빈칸을 사이에 두고 순서대로 주어진다.
• 두 번째 줄에는 요리하는 데 필요한 시간 C ( 0 <= C <= 1000) 가 분 단위로 주어진다.

출력

(단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.)

입출력 예

입력

14 30
20

출력 

14 50

입력 

17 40
80

출력 

19 0

입력 

23 48
25

출력 

0 13

출처:2012 지역 본선 초등 1/5

길이가 같은 두 개의 이진수 코드 과 가 있다고 하자.

이 두 코드 사이의 해밍 거리(Hamming distance)는 의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다.

예를 들어, , 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 해밍 거리는 2이다

KOI 연구소는 특정 암호문에서 사용되는 총 N개의 이진 코드를 가지고 있다. 각 코드의 길이는 K로 일정하다. 연구소는 이 코드들에 대해 여러 가지 특징을 분석하고 있다.

예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다고 하자.

두 코드 와  사이의 해밍 거리를 로 표현한다.

그러면, hd(w1,w2) = 3, hd(w1,w3) = 1, hd(w1,w4) = 2, hd(w1,w5) = 1

당신은 이진 코드들에 대해 해밍 경로를 찾고자 한다. 해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다. 위의 예에서  는 길이가 3인 해밍 경로이지만, 는 해밍 경로가 아니다. 두 코드 사이에 해밍 경로가 여러 개가 있을 경우 가장 짧은 경로를 찾고자 한다

이 문제는 1번 코드에서부터 질의로 주어진 여러 개의 코드까지의 해밍 경로를 각각 구하는 프로그램을 작성하는 것이다. 프로그램의 실행시간은 2초를 넘을 수 없다.

입력

• 첫째 줄에는 두 개의 정수 N(3≤N≤100,000)과 K(2≤K≤30)가 빈칸을 사이에 두고 주어진다.

• 둘째 줄부터 N개의 줄에는 각 줄마다 길이가 K인 이진 코드가 하나씩 주어진다.
  하나의 코드는 빈칸이 없이 주어지며, 코드들은 주어진 순서대로 1부터 N까지의 번호로 구분된다. 코드가 같은 경우는 없다.

• 그 다음 줄에는 해밍 경로를 찾고자하는 질의의 수인 하나의 정수 M(2≤M≤50)이 주어진다.

• 그 다음 M개의 줄에는 각 줄마다 한 개의 양의 정수 J(2≤J≤N)가 주어진다. J는 1번 코드와 J번 코드 사이의 해밍 경로를 구하라는 질의에 해당한다. J는 모두 다르다.

출력

출력은 M개의 줄로 구성된다.각 줄에는 입력으로 주어진 각 질의에 대한 답을 순서대로 출력한다.

만일 두 코드 사이에 해밍 경로가 존재하면 가장 짧은 경로에 있는 코드들의 번호를 1번 코드부터 차레로 하나의 빈칸을 사이에 두고 출력한다. 답이 여러 개 있으면 그 중에 하나만 출력하고, 경로가 존재하지 않으면 -1을 출력한다.

입출력 예

입력

5 3
000
111
010
110
001
2
4
2

출력

1 3 4
1 3 4 2

출처 : KOI 2010 지역본선 3번
special judge: Fate
참고 : http://211.228.163.31/pool/hamming_distance/hamming_distance.php?pname=hamming_distance