USACO 2011 November Contest, Bronze Division Problem 3. Moo Sick (moosick)

Problem 3: Moo Sick [Rob Seay]

Everyone knows that cows love to listen to all forms of music. Almost all forms, that is -- the great cow composer Wolfgang Amadeus Moozart once discovered that a specific chord tends to make cows rather ill. This chord, known as the ruminant seventh chord, is therefore typically avoided in all cow musical compositions. 

Farmer John, not knowing the finer points of cow musical history, decides to play his favorite song over the loudspeakers in the barn. Your task is to identify all the ruminant seventh chords in this song, to estimate how sick it will make the cows. 

The song played by FJ is a series of N (1 <= N <= 20,000) notes, each an integer in the range 1..88. A ruminant seventh chord is specified by a sequence of C (1 <= C <= 10) distinct notes, also integers in the range 1..88. However, even if these notes are transposed (increased or decreased by a common amount), or re-ordered, the chord remains a ruminant seventh chord! For example, if "4 6 7" is a ruminant seventh chord, then "3 5 6" (transposed by -1), "6 8 9" (transposed by +2), "6 4 7" (re-ordered), and "5 3 6" (transposed and re-ordered) are also ruminant seventh chords.

A ruminant seventh chord is a sequence of C consecutive notes satisfying the above criteria. It is therefore uniquely determined by its starting location in the song. Please determine the indices of the starting locations of all of the ruminant seventh chords. 

PROBLEM NAME: moosick

INPUT FORMAT: 
* Line 1: A single integer: N.
* Lines 2..1+N: The N notes in FJ's song, one note per line. 
* Line 2+N: A single integer: C.
* Lines 3+N..2+N+C: The C notes in an example of a ruminant seventh chord. All transpositions and/or re-orderings of these notes are also ruminant seventh chords.

SAMPLE INPUT (file moosick.in): 
6 
1 
8 
5 
7 
9 
10 
3
4 
6 
7

INPUT 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 FORMAT:
* Line 1: A count, K, of the number of ruminant seventh chords that appear in FJ's song. Observe that different instances of ruminant seventh chords can overlap each-other.
* Lines 2..1+K: Each line specifies the starting index of a ruminant seventh chord (index 1 is the first note in FJ's song, index N is the last). Indices should be listed in increasing sorted order. 

SAMPLE OUTPUT (file moosick.out): 
2 
2 
4 

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.

【分析】
還是模擬題，先對那C個ruminant seventh chords進行排序，然後一次次的快速排序，判斷即可。

【我的代碼（成績出來了，滿分）】
/*
ID:zyfwork1
PROB:moosick
LANG:C++
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int N,C;
int Num[20001];
int Sev[11];
int res[20001];
int top=0;

int cmp(const void  *a,const void  *b)
{
    return *((int *)a)-*((int *)b);
}

void init()
{
    scanf("%d",&N);
    for (int i=1;i<=N;i++)
        scanf("%d\n",&Num[i]);
    scanf("%d",&C);
    for (int i=1;i<=C;i++)
        scanf("%d\n",&Sev[i]);
    qsort(Sev+1,C,sizeof(Sev[0]),cmp);
    return;
}

void work()
{
    for (int i=1;i<=N-C+1;i++)
    {
        int tmp[11];
        memset(tmp,0,sizeof(tmp));
        int tt=1;
        for (int j=i;tt<=C;j++)
            tmp[tt++]=Num[j];
        qsort(tmp+1,C,sizeof(tmp[0]),cmp);
        int delta=tmp[1]-Sev[1];
       
        bool flag=true;
        for(int k=2;k<=C;k++)
        {
            if(tmp[k]-delta!=Sev[k])
            {
                flag=false;
                break;
            }
        }
        if(flag)
        {
            res[++top]=i;
        }
    }
   
    printf("%d\n",top);
    for (int i=1;i<=top;i++)
        printf("%d\n",res[i]);
   
}

int main()
{
    freopen("moosick.in","r",stdin);
    freopen("moosick.out","w",stdout);
    init();
    work();
    return 0;
}