제출 #13347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13347		baneling100	홀-짝 수열 (IZhO11_oddeven)	C++98	100 / 100	3 ms	1088 KiB

oddeven

#include <stdio.h>
#include <string.h>
#define LEN_MAX 300

int N[LEN_MAX], Nlen, MM[LEN_MAX], MMlen, T[LEN_MAX], Tlen;
int L[LEN_MAX], Llen, M[LEN_MAX], Mlen, R[LEN_MAX], Rlen;

int isBigger(void) {

    int i;

    if(Llen<Rlen) return 1;
    if(Llen>Rlen) return -1;
    for(i=Llen ; i>=1 ; i--) {
        if(L[i]<R[i]) return 1;
        if(L[i]>R[i]) return -1;
    }
    return 0;
}

void makeM(void) {

    int i;

    Mlen=Rlen;
    for(i=1 ; i<=Mlen ; i++) M[i]=R[i];
    for(i=1 ; i<=Llen ; i++) M[i]+=L[i];
    for(i=1 ; i<=Mlen ; i++) {
        if(M[i]%2) M[i-1]+=5;
        M[i]/=2;
    }
    for(i=1 ; i<=Mlen ; i++) {
        M[i+1]+=M[i]/10;
        M[i]%=10;
    }
    if(!M[Mlen]) Mlen--;
}

void makeMM(void) {

    int i, j;

    MMlen=(Mlen<<1)-1;
    for(i=1 ; i<=MMlen+1 ; i++) MM[i]=0;
    for(i=1 ; i<=Mlen ; i++) {
        for(j=1 ; j<=Mlen ; j++)
            MM[i+j-1]+=M[i]*M[j];
        MM[i]+=M[i];
    }
    for(i=1 ; i<=MMlen ; i++) {
        MM[i+1]+=MM[i]/10;
        MM[i]%=10;
    }
    if(MM[MMlen+1]) MMlen++;
}

int compare(void) {

    int i;

    if(MMlen<Nlen) return 1;
    if(MMlen>Nlen) return -1;
    for(i=MMlen ; i>=1 ; i--) {
        if(MM[i]<N[i]) return 1;
        if(MM[i]>N[i]) return -1;
    }
    return 0;
}

void makeT(void) {

    int i;

    Tlen=Mlen;
    T[Mlen+1]=0;
    for(i=1 ; i<=Mlen ; i++)
        T[i]=M[i];
    T[i=1]++;
    while(T[i]>9) {
        T[i+1]++;
        T[i]-=10;
        i++;
    }
    if(T[Tlen+1]) Tlen++;
}

void makeL(void) {

    int i;

    Llen=Mlen;
    L[Mlen+1]=0;
    for(i=1 ; i<=Mlen ; i++)
        L[i]=M[i];
    L[i=1]++;
    while(L[i]>9) {
        L[i+1]++;
        L[i]-=10;
        i++;
    }
    if(L[Llen+1]) Llen++;
}

void makeR(void) {

    int i;

    Rlen=Mlen;
    for(i=1 ; i<=Mlen ; i++)
        R[i]=M[i];
    R[i=1]--;
    while(R[i]<0) {
        R[i]+=10;
        R[i+1]--;
        i++;
    }
    if(!R[Rlen]) Rlen--;
}

int main(void) {

    int i;
    char S[LEN_MAX];

    scanf("%s",S+1);
    Nlen=strlen(S+1);
    for(i=1 ; i<=Nlen ; i++) {
        N[i]+=(S[Nlen-i+1]-'0')<<1;
        N[i+1]+=N[i]/10;
        N[i]%=10;
    }
    if(N[Nlen+1]) Nlen++;
    R[Rlen=100]=1;
    while(isBigger()>=0) {
        makeM();
        makeMM();
        if(compare()>0) {
            makeT();
            makeL();
        }
        else
            makeR();
    }
    for(i=1 ; i<=Tlen ; i++)
        N[i]-=T[i];
    for(i=1 ; i<=Nlen ; i++)
        if(N[i]<0) {
            N[i]+=10;
            N[i+1]--;
        }
    while(!N[Nlen]) Nlen--;
    for(i=Nlen ; i>=1 ; i--)
        printf("%d",N[i]);

    return 0;
}

• Subtask 1: 100 / 100