USACO 2005 December Contest gold1- 그룹찾기(Cow Patterns) > 문제은행 : 정보올림피아드&알고리즘




1616 : 그룹찾기(Cow Patterns)

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

문제

농부 창호의 소들 중에서 K (1≤K≤25,000) 마리의 그룹은 말썽을 자주 피운다. 

일렬로 소들을 세울 때, 말썽쟁이들이 특정 순서로 서게 된다.

 

이 그룹을 찾아내기 위해서 농부 창호는 총 N (1≤N≤100,000)마리의 소들을 일렬로 세웠다. 

당신은 창호를 도와 K 마리의 연속된 소들이 말썽 그룹인지 확인해야한다.

 

창호는 그의 소들의 점의 수 1... S로 소들을 구분해 놓았다. (1≤S≤25). 

창호는 정확히 어느 소들이 말썽을 부리는 그룹인지는 기억하지 못하지만 소들의 점의 수는 기억한다. 

그는 말썽을 부리는 그룹 소들의 점의 수대로 순위를 매겼다.

 

1 4 4 3 2 1

 

이 예에서는, 연속된 6마리들 중에서 첫 번째와 여섯 번째가 가장 적은 점을 갖고 있고 

다음으로 다섯 번째, 다음으로 네 번째, 그리고 두 번째, 세 번째가 가장 적은 점을 갖고 있는 그룹을 찾고자 한다.


만약 소들의 점의 수가 다음과 같다면

 

5 6 2 10 10 7 3 2 9

 

2 10 10 7 3 2 부분은 위의 패턴을 만족한다. 

패턴을 만족하는 그룹들을 찾아야한다.


입력형식

입력은 다음의 형식으로 입력된다. 첫 번째 줄 : N, K, S가 입력된다. 두 번째 줄부터 N+1번째 줄 까지 : i+1줄은 i번 소의 점의 수를 의미한다. N+2번째 줄부터 N+K+1번째 줄 까지: i+N+1줄은 패턴에서 i번째의 순위를 의미한다.

출력형식

출력은 다음의 형식을 따른다. 첫 번째 줄: 패턴이 맞는 위치의 수를 출력한다. 두 번째 줄부터 B+1번째 줄까지: 패턴이 맞는 그룹의 시작 위치들을 출력한다.

입력 예

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

출력 예

1
3


KMP응용

경기도 안양시 동안구 평촌대로 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