//Queue 나 Stack 은 잊지 않았지만.

//잔실수에 괜한 시간을 빼앗기는 것은 서두르기 때문;

#include <stdio.h>

#include <Windows.h>

#define MAX_K 5000000

short queue[5000000]; //2 * 5,000,000 = 10,000,000 bytes

int head =0;

int tail =0;

unsigned int sum =0;

short pop(){

    head ++;

    if(head<=tail){

        sum -= (unsigned int)queue[head];

        return queue[head];

    }else{

        head =tail;

        return -1;

    }

}

void push(short val){

    tail ++;

    if(tail < 5000000){

        queue[tail] = val;

        sum += (unsigned int)val;

    }else{

        tail --;

    }

}

//K : 합이 되는 수

//N : 20 개 중에

int getPartialSeq(unsigned int k,int n){

    head = 0;

    tail = 0;

    sum = 0u;

    int count=0;

    int i=0,j=0;

    unsigned int val=0;

    unsigned int cur = 0;

    cur = 1983u;

    for(i=1;i<n;i++){

        val = cur;

        cur = (cur * 214013u + 2531011u);

        val = val%(10000u)+1;

        push(val);

        //숫자 합이 k 보다 크면 point 를 하나 크게 한다. => pop

        while(sum > k){

            pop();

        }

        if(sum == k){

            count ++;

        }

    }

    return count;

}

int main(){

    long start = GetTickCount();

    printf("%d

",getPartialSeq(8791u,20));

    printf("%d

",getPartialSeq(5265u,5000));

    for(int i=0;i<20;i++){

    printf("%d

",getPartialSeq(3578452u,5000000));

    }

    printf("%.2lf sec

",(GetTickCount() - start)/1000.0);

}

//stack 기본 문제였던듯?

//그래도 마무리는 깔끔하게 모두 pop 되었는지, 전역변수는 제대로 초기화가 되었는지 확인!

#include <stdio.h>

#include <string.h>

inline int mystrlen(char* str){int n =0 ;for(n=0;str[n]!='\0';n++); return n;}

char bracket[10000];

char stack[10000];

int point=0;

char pop(){

    if(point<=0){return -1;}

    point--;

    return stack[point];

}

void push(char c){

    stack[point]=c;

    point++;

}

char well_formed(){

    int n = mystrlen(bracket);

    for(int i=0;i<n;i++){

        //열면 push

        //닫으면 pop

        if(bracket[i] == '['|| bracket[i] == '{'||bracket[i] == '('){

            push(bracket[i]);

        }else{

            char c = pop();

            if(bracket[i]==']'&& c != '[' ){

                return (char)0;

            }

            else if(bracket[i]=='}'&& c != '{'){

                    return (char)0;

            }else if(bracket[i]==')'&& c != '('){

                    return (char)0;

            }

        }

    }

    if(pop()==-1){

        return (char)1;

    }else{

        return (char)0;

    }

}

int main(){

    strcpy(bracket,"()()");

    point =0;

    if(well_formed()==(char)1){

        printf("YES

");

    }else{

        printf("NO

");

    }

    strcpy(bracket,"({[}])");

    point =0;

    if(well_formed()==(char)1){

        printf("YES

");

    }else{

        printf("NO

");

    }

    strcpy(bracket,"({}[(){}])");

    point =0;

    if(well_formed()==(char)1){

        printf("YES

");

    }else{

        printf("NO

");

    }

}

//최적화 없이 O(NK) 였음..

#include <stdio.h>

#define N 1000 //min 3

#define K 1000 //min 3

//1,4,2,6

int main(){

    //2명이 될때 까지 K 번 건너뛰면서 본다.

    int n =40;

    int k =3;

    int soldier[N];

    for(int i=0;i<n;i++){

        soldier[i] = 1;

    }

    int check =n;

    int no=0;

    while ( check >2){

        if(soldier[no]==1){

            check--;

            soldier[no] = 0;

        }else{

            int j=no+1;

            j=j%n;

            for(;soldier[j]==0;){

                j++;

                j=j%n;

            }

            no=j;

            check--;

            soldier[no] = 0;

        }

        for(int next = no+1,count =0;count <k;next++){

            next = next%n;

            if(soldier[next]==1){

                no = next;

                count++;

            }

        }

    }

    int j=0;

    for(int i=0;i<n;i++){

        if(soldier[i]){

        printf("%d ",i+1);

        j++;

        if(j==2){

            break;

        }

        }

    }

    printf("

");

}

//-1 번째를 계산해야 하므로 H[-1] 과 같은 효과를 주어 다른 것을 1칸씩 뒤로 미루고 0 에 0 을 넣는다.

//(A-B)%M 은 A%M - B%M 과 같다..?

#include <stdio.h>

#define N 4 //인형 상자의 수

#define K 1 //어린이 수

int present[100000]; //인형 상자

int partialSum[100000];

int cache[100000];

int count[100000];

//Max(0~n 까지의 선물배열의 연속 부분 집합 중 K 로 나눠지는 것의 개수)

int multipleMemoizationDP(int T){

    if(T<=0){

//        if(partialSum[T]==0){return 1;}

        return 0;

    }

    //포함하지 않는 경우.

    int & ret = cache[100000];

    if(ret!=-1){return ret;}

    int max1 = multipleMemoizationDP(T-1);

    int h=T-1;

    //포함하는 경우.

    for(;h>=0;h--){

        if(partialSum[h] == partialSum[T]){

            break;

        }

    }

    int max2=multipleMemoizationDP(h)+1;

    ret = max1>max2 ? max1:max2;

    return ret;

}

int multipleRepeatDP(int T){

    int ret[100000];

    int returnValue = 0;

    int prev[K];

    for(int i=0;i<100000;i++){

        ret[i] = 0;

        if(i<K){

            prev[i]=-1;

        }

    }

    //이번 것을 넣지 않거나, 같은 psum을 가진 것 중 가장 큰 것을 넣는다.

    //ret[i]=max(ret[i-1], ret[prev[psum[i]]);

    for(int i=0;i<T;i++){

        if(i>0){

            ret[i]=ret[i-1];

        }

        //처음 본 나머지가 아니라면 max 를 정하는 것에 둔다.

        if(prev[partialSum[i]]!=-1){

            ret[i] = (ret[prev[partialSum[i]]]+1)>ret[i]?(ret[prev[partialSum[i]]]+1):ret[i];

            returnValue=ret[i];

        }

        prev[partialSum[i]] = i;

    }

    return returnValue;

}

//psum 의 나머지가 같으면 K로 반드시 나눠진다.

int main(){

    for(int i=0;i<100000;i++){

        cache[i]=-1;

    }

    int Answer1=0;

    int i=0,Answer2=0;

    int T=0,H=T;

    present[0]=0;//1 //0

    present[1]=1;//1 //1

    present[2]=2;//3 //3

    present[3]=3;//6 // 2

  &nbs\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0p; present[4]=4;//10 // 2

    present[5]=5;//15 // 3

    present[6]=6;//21 // 1

    present[0]=0;

    present[1]=1;

    present[2]=2;

    present[3]=3;

    present[4]=4;

    partialSum[0] = 0;

    for(i=1;i<=N+1;i++){

        int psum=0;

        for(int j=0;j<i;j++){

            psum += present[j];

        }

        partialSum[i-1] = psum %K;

    }

    //문제 1 O(N^2)

    //조합의 수를 구한다.

    for(i=1;i<=N+1;i++){

        count[partialSum[i-1]] ++;

    }

    //btt = Bigger than two (count 배열 중 2를 넘는 것)

    //btt C 2

    for(i=0;i<K;i++){

        if(count[i]>=2){

            Answer1 = (Answer1 + (count[i]*(count[i]-1)) /2)%20091101 ;

        }

    }

    //문제 2 Max(0~n 까지의 선물배열의 연속 부분 집합 중 K 로 나눠지는 것의 개수)

    Answer2 = multipleRepeatDP(N+1);

    printf("%d %d

",Answer1,Answer2);

}