Submission #345484

#	Time	Username	Problem	Language	Result	Execution time	Memory
345484		nicolaalexandra	Odd-even (IZhO11_oddeven)	C++14	0 / 100	2085 ms	512 KiB

oddeven

#include <bits/stdc++.h>
#define DIM 1000000
using namespace std;

int a[DIM],aux[DIM],aux2[DIM],sol[DIM],ans[DIM],st[DIM],dr[DIM],mid[DIM],unu[3];
char s[DIM];
int i;

void adunare (int a[], int b[], int c[]){
    int m;
    if (a[0] > b[0]){
        m = a[0];
        for (int i=b[0]+1;i<=m;i++)
            b[i] = 0;
    } else {
        m = b[0];
        for (int i=a[0]+1;i<=m;i++)
            a[i] = 0;
    }

    int t = 0;
    for (int i=1;i<=m;i++){
        c[i] = a[i] + b[i] + t;
        t = c[i] / 10;
        c[i] %= 10;
    }

    c[0] = m;
    while (t){
        c[++c[0]] = t%10;
        t /= 10;
    }

}

void inmultire (int a[], int b[], int c[]){

    for (int i=1;i<=a[0] + b[0];i++)
        c[i] = 0;

    c[0] = a[0] + b[0] - 1;
    for (int i=1;i<=a[0];i++)
        for (int j=1;j<=b[0];j++)
            c[i+j-1] += a[i] * b[j];

    int t = 0;
    for (int i=1;i<=c[0];i++){
        c[i] += t;
        t = c[i] / 10;
        c[i] %= 10;
    }

    while (t){
        c[++c[0]] = t%10;
        t /= 10;
    }
}

void impartire (int a[], int b){

    int r = 0;
    for (int i=a[0];i;i--){
        r = r * 10 + a[i];
        a[i] = r / b;
        r %= b;
    }

    while (a[0] > 1 && !a[a[0]])
        a[0]--;

}

void scadere (int a[], int b[]){ /// a - b
    for (int i=b[0]+1;i<=a[0];i++)
        b[i] = 0;

    int t = 0;
    for (int i=1;i<=a[0];i++){
        a[i] = a[i] - (b[i] + t);
        if (a[i] < 0)
            t = 1;
        else t = 0;
        if (t)
            a[i] += 10;
    }

    while (a[0] > 1 && !a[a[0]])
        a[0]--;
}

int compare (int a[], int b[]){ /// a <= b
    if (a[0] < b[0])
        return 1;
    if (a[0] > b[0])
        return 0;

    for (int i=a[0];i;i--){
        if (a[i] < b[i])
            return 1;
        if (a[i] > b[i])
            return 0;
    }
    return 1;
}

void copiere (int a[], int b[]){
    for (int i=0;i<=b[0];i++)
        a[i] = b[i];
}

void scadere1 (int a[]){

    int i = 1;
    while (i <= a[0] && !a[i]){
        a[i] = 9;
        i++;
    }

    a[i]--;
    if (i == a[0] && !a[i])
        a[0]--;

}

int main (){

    /*1   2 4    5 7 9    10 12 14 16    17 19 21 23 25    26

    +1, +2*1+1, +2*2+1, +2*3+1, +2*4+1

    1+2+3+..+n <= val;
    n * (n+1) / 2 <= val;
    n * n + n*/

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>s+1;
    int n = strlen (s+1);
    for (i=1;i<=n;i++)
        a[n-i+1] = dr[n-i+1] = s[i] - '0';
    a[0] = dr[0] = n;

    if (n == 1 && a[1] == 1){
        cout<<1;
        return 0;
    }

    if (n == 1 && a[1] == 2){
        cout<<2;
        return 0;
    }

    if (n == 1 && a[1] == 3){
        cout<<4;
        return 0;
    }

    st[0] = st[1] = 1;
    unu[0] = unu[1] = 1;

    while (compare(st,dr)){

        adunare (st,dr,mid);
        impartire (mid,2);

        inmultire (mid,mid,aux);
        adunare (mid,aux,aux);
        impartire (aux,2);

        if (compare(aux,a)){
            copiere (sol,mid);
            adunare (mid,unu,st);
            /// st = mid+1;
        } else { /// dr = mid-1;
            copiere (dr,mid);
            scadere1 (dr);
        }

    }

    copiere (aux,sol);
    scadere1 (aux);

    /*copiere (aux2,sol);
    scadere1 (aux2); scadere1 (aux2);
*/

    inmultire (aux,sol,ans);
    adunare (ans,sol,ans);
    adunare (ans,unu,ans);


    /// mai adun ce a mai ramas din ultima grupa

    inmultire (sol,sol,aux);
    adunare (aux,sol,aux);
    impartire (aux,2);

    scadere (a,aux);

    scadere1 (a);

    adunare (ans,a,ans);
    adunare (ans,a,ans);

    for (i=ans[0];i;i--)
        cout<<ans[i];



    return 0;
}

Compilation message (stderr)

oddeven.cpp: In function 'int main()':
oddeven.cpp:138:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |     cin>>s+1;
      |          ~^~

• Subtask 1: 0 / 100