Codeforces Round #279 (Div. 2) Problem solving report_html/css_WEB-ITnose

A - Team Olympiad

Greedy question. . Just start from the first one.

The code is as follows:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64int a[6000], b[6000];int main(){    int n, x, y, z, ans, i, j;    while(scanf("%d",&n)!=EOF)    {        x=y=z=0;        for(i=0;i<n;i++)        {            scanf("%d",&a[i]);        }        memset(b,0,sizeof(b));        for(i=0;i<n;i++)        {            if(a[i]==1)            {                x++;                b[i]=x;            }            else if(a[i]==2)            {                y++;                b[i]=y;            }            else if(a[i]==3)            {                z++;                b[i]=z;            }        }        ans=min(x,min(y,z));        printf("%d\n",ans);        for(i=1;i<=ans;i++)        {            for(j=0;j<n;j++)            {                if(b[j]==i)                {                    printf("%d ",j+1);                }            }            puts("");        }    }    return 0;}

B - Queue

By recording the next position in an array, the even numbers are positions and filling in odd positions.

Even-numbered positions must start from 0, and odd-numbered positions must start from a number with no out-degree and only in-degree.

The code is as follows:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64int next[1100000], a[1100000], out[1100000];struct node{    int u, v;}fei[1100000];int main(){    int n, i, j, u, v, cnt, pos;    while(scanf("%d",&n)!=EOF)    {        memset(next,-1,sizeof(next));        memset(out,0,sizeof(out));        for(i=0;i<n;i++)        {            scanf("%d%d",&fei[i].u, &fei[i].v);            next[fei[i].u]=fei[i].v;            out[fei[i].v]++;        }        cnt=1;        for(i=0;i!=-1;i=next[i])        {            if(cnt!=1&&!i) break;            a[cnt]=next[i];            cnt+=2;        }        cnt=0;        for(i=0;i<n;i++)        {            if(!out[fei[i].u])            {                pos=fei[i].u;                break;            }        }        a[0]=pos;        cnt=2;        for(i=pos;i!=-1;i=next[i])        {            a[cnt]=next[i];            cnt+=2;        }        for(i=0;i<n;i++)        {            printf("%d ",a[i]);        }    }    return 0;}

C - Hacking Cypher

Scan the record from the front and back respectively to be divisible location. Very good handling from front to back.

As for the k-th digit, you can first preprocess the sum of the remainders of 10^k to b and the remainder of the first k digits to b, and then, the last few digits = total number - the previous The number represented by k bits*10^k. So as long as the total number %b==(the number represented by the first k digits %b)*(10^k%b)%b is satisfied, it means that the number represented by the last few digits can be divided by b.

This can be completed within O(n) complexity.

It means that I am really weak. . I’ve seen other people make it in a short time. . But it took me half an hour to figure it out. . .

The code is as follows:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64int a[1100000], b[1100000], c[1100000], d[1100000];char s[1100000];int main(){    int aa, bb, i, x, len, pos, flag=0, y;    gets(s);    scanf("%d%d",&aa,&bb);    memset(a,0,sizeof(a));    memset(d,0,sizeof(d));    x=1;    c[1]=1%bb;    for(i=2;i<=1000000;i++)    {        x=x*10%bb;        c[i]=x;    }    len=strlen(s);    x=0;    y=0;    for(i=0;i<len;i++)    {        x=x*10+s[i]-'0';        x%=aa;        //printf("%d\n",x);        if(x==0)            a[i]=1;        y=y*10+s[i]-'0';        y%=bb;        b[i]=y;    }    //printf("%d\n",y);    for(i=0;i<len;i++)    {        if((LL)b[i]*c[len-i]%bb==(LL)y)        {            d[i]=1;        }    }    for(i=0;i<len-1;i++)    {        if(a[i]&&d[i]&&s[i+1]!='0')        {            pos=i;            flag=1;            break;        }    }    if(!flag)        puts("NO");    else    {        puts("YES");        for(i=0;i<=pos;i++)        {            printf("%c",s[i]);        }        puts("");        for(i=pos+1;i<len;i++)        {            printf("%c",s[i]);        }    }    return 0;}

D - Chocolate

If the final areas are equal, then the factor of 2 The number must be equal to the number of factors of 3. So we can first find the number of factors of 2 and the number of factors of 3. Then at this time we can have two operations: eliminating a 2 or turning a 3 into a 2. So at this time, first change the larger of 3 into 2 to make the remaining 3 equal, and then eliminate the larger factor of 2. The larger side makes equal. Then it is judged that the areas of both sides are equal at this time.

The code is as follows:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64int main(){    int a1, b1, a2, b2, x2, x3, y2, y3, ans, m1, m2, n1, n2;    while(scanf("%d%d%d%d",&a1,&b1,&a2,&b2)!=EOF)    {        m1=a1;        m2=a2;        n1=b1;        n2=b2;        x2=x3=y2=y3=0;        while(!(a1%2)||!(a1%3))        {            if(a1%2==0)            {                x2++;                a1/=2;            }            if(a1%3==0)            {                x3++;                a1/=3;            }        }        while(!(b1%2)||!(b1%3))        {            if(b1%2==0)            {                x2++;                b1/=2;            }            if(b1%3==0)            {                x3++;                b1/=3;            }        }        while(!(a2%2)||!(a2%3))        {            if(a2%2==0)            {                y2++;                a2/=2;            }            if(a2%3==0)            {                y3++;                a2/=3;            }        }        while(!(b2%2)||!(b2%3))        {            if(b2%2==0)            {                y2++;                b2/=2;            }            if(b2%3==0)            {                y3++;                b2/=3;            }        }        if(x3>=y3)        {            x2+=x3-y3;            ans=x3-y3;            for(int i=0; i<x3-y3; i++)            {                if(m1%3==0)  m1=m1/3*2;                else  n1=n1/3*2;            }        }        else        {            y2+=y3-x3;            ans=y3-x3;            for(int i=0; i<y3-x3; i++)            {                if(m2%3==0) m2=m2/3*2;                else n2=n2/3*2;            }        }        ans+=abs(x2-y2);        if(x2>=y2)        {            for(int i=0; i<x2-y2; i++)            {                if(m1%2==0) m1/=2;                else n1/=2;            }        }        else        {            for(int i=0; i<y2-x2; i++)            {                if(m2%2==0) m2/=2;                else n2/=2;            }        }        if((LL)m1*n1!=(LL)m2*n2)            puts("-1");        else        {            printf("%d\n",ans);            printf("%d %d\n%d %d\n",m1,n1,m2,n2);        }    }    return 0;}