IOI 1998 day1 1- 미지의 별과의 교신(Contact) > 문제은행 : 정보올림피아드&알고리즘




1456 : 미지의 별과의 교신(Contact)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
21 회   
시도횟수
116 회   

문제

창호 박사는 전파 망원경 센터에서 근무한다. 

최근 창호는 은하수 중앙에서 곧바로 빛줄기를 뿜으며 흘러가는 아주 묘하게 생긴 극초단파를 주목하고 있다. 

그 빛줄기는 외계의 다른 고등 생물이 보낸 신호인가, 아니면 그저 보통 별에서 뿜어져 나오는 빛일 뿐일까?



당신은 창호 박사가 기록한 비트열 데이터 파일을 분석하는 도구를 만들어, 박사가 진위 여부를 밝혀내는 것을 도와야 한다. 

창호 박사는 관측 기계에서 매일 나오는 데이터 파일 가운데, 길이가 A와 B사이에서 자주 반복되어 나오는 비트열을 여러 개 찾아내고 싶어한다.



서로 다른 빈도수의 개수를 N이라고 한다. 비트열은 겹쳐도 상관없으며, (00000라는 비트열 안에는 000이 세 개 있다.)

적어도 한 번만 나타나면 그것은 빈도수의 개수로 쳐준다.


입력형식

첫 번째 줄은 정수 A(1 ≤ A ≤ 12)의 값으로, 가장 짧은 패턴의 길이이다. 두 번째 줄은 정수 B(A ≤ B ≤ 12)의 값으로, 가장 긴 패턴의 길이이다. 세 번째 줄은 정수 N(0 < N ≤ 20)의 값으로, 서로 다른 빈도수의 개수 (아래 설명을 보면 이해가 될 것이다)를 뜻한다. 네 번째 줄은 0과 1로만 이루어졌고, 2로 끝나는 수열이며 수열의 최대 길이는 10,000이다. 예를 들면, 2 4 10 010100100100010001111011000010100110011110000100100111100100000002 이는 01010010010001000111101100001010011001111000010010011110010000000이라는 패턴 중에서 길이가 2에서 4 사이인 가장 자주 나오는 비트열을 뽑아서 출력하되, 빈도수의 순위를 가장 긴 것부터 10개까지만 고르라는 뜻이다. 예를 들면, 1000은 다섯 번 나오고, 100은 12번 나왔다. 가장 빈도수가 높은 것은 00으로, 23번 나온다.

출력형식

최대 N줄에 가장 자주 나오는 빈도의 순서대로 빈도수를 기록하고 다음에 반복되어 나오는 패턴(길이가 짧은 것을 길이가 같은 경우 2진수를 10진수로 표현했을 때 숫자가 작은 것을 먼저 출력)들을 모두 기록한다. 패턴과 패턴 그리고 숫자 사이는 공백으로 구분한다. 앞의 입력 자료가 들어가면 그에 대응하는 출력 자료는 다음과 같아야 한다. 23 00 15 10 01 12 100 11 001 000 11 10 010 8 0100 7 1001 0010 6 0000 111 5 1000 110 011 4 1100 0011 0001 00이 가장 자주 나왔고(23번), 10과 01은 15번, 100은 12번 나왔다. 그렇게 서로 다른 빈도수 순위를 10개까지 뽑아서 위와 같은 결과를 만드는 것이다.

입력 예

2
4
10
010100100100010001111011000010100110011110000100100111100100000002

출력 예

23 00
15 01 10
12 100
11 11 000 001
10 010
8 0100
7 0010 1001
6 111 0000
5 011 110 1000
4 0001 0011 1100


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP