레이팅 미적용모든 소가 온갖 형태의 음악을 사랑한다는 것은 잘 알려져 있다. 정확히는 거의 모든 형태이다. 위대한 소 작곡가 볼프강 아마데우스 모차르트(Moozart)는 어떤 특정한 화음이 소들을 상당히 아프게 만드는 경향이 있다는 것을 발견했다. 반추동물 7화음이라고 알려진 이 화음은, 따라서 모든 소 음악 작품에서 일반적으로 금기시된다.
소 음악사의 세세한 부분까지는 알지 못하는 농부 존(Farmer John)은, 헛간의 확성기로 자신이 가장 좋아하는 노래를 틀기로 한다. 당신의 임무는 이 노래에 들어 있는 모든 반추동물 7화음을 찾아내어, 노래가 소들을 얼마나 아프게 할지 가늠하는 것이다.
FJ가 트는 노래는 N개 (1 <= N <= 20,000)의 음표로 이루어진 수열이며, 각 음표는 1..88 범위의 정수이다. 반추동물 7화음은 C개 (1 <= C <= 10)의 서로 다른 음표의 수열로 정의되며, 각 음표 역시 1..88 범위의 정수이다. 하지만 이 음표들을 조옮김하거나(모두 같은 양만큼 올리거나 내리거나), 순서를 바꾸어도 여전히 반추동물 7화음이다! 예를 들어 "4 6 7"이 반추동물 7화음이라면, "3 5 6"(-1만큼 조옮김), "6 8 9"(+2만큼 조옮김), "6 4 7"(순서 변경), "5 3 6"(조옮김과 순서 변경)도 모두 반추동물 7화음이다.
반추동물 7화음은 위 조건을 만족하는 연속한 C개의 음표로 이루어진 수열이다. 따라서 노래에서의 시작 위치로 유일하게 결정된다. 모든 반추동물 7화음의 시작 위치 인덱스를 구하시오.
첫째 줄: 정수 N.
둘째 줄부터 1+N번째 줄까지: FJ의 노래에 들어 있는 N개의 음표가 한 줄에 하나씩 주어진다.
2+N번째 줄: 정수 C.
3+N번째 줄부터 2+N+C번째 줄까지: 반추동물 7화음의 한 예를 이루는 C개의 음표. 이 음표들의 모든 조옮김 및/또는 순서 변경 역시 반추동물 7화음이다.
첫째 줄: FJ의 노래에 나타나는 반추동물 7화음의 개수 K. 서로 다른 반추동물 7화음들이 서로 겹칠 수 있음에 유의하라.
둘째 줄부터 1+K번째 줄까지: 각 줄에 반추동물 7화음의 시작 인덱스를 출력한다 (인덱스 1은 FJ의 노래의 첫 음표, 인덱스 N은 마지막 음표). 인덱스는 오름차순으로 출력해야 한다.
moosick.in · 출력을 쓸 파일 moosick.out6
1
8
5
7
9
10
3
4
6
72
2
4Input details: FJ's song is 1,8,5,7,9,10. A ruminant seventh chord is some transposition/re-ordering of 4,6,7.
Output details: Two ruminant seventh chords appear in FJ's song (and these occurrences actually overlap by one note). The first is 8,5,7 (transposed by +1 and reordered) starting at index 2, and the second is 7,9,10 (transposed by +3) starting at index 4.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > November > Bronze