Cod sursa(job #1001217)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 24 septembrie 2013 18:53:21
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#include <cstring>
#include <queue>
#define N 2000001
using namespace std;
 
int cif[N], nxt[N], sol[100];
 
int cmmdc(int r, int t)
{
    int c;
    while (t) {
        c = r % t;
        r = t;
        t = c;
    }
    return r;
}
 
int main()
{
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    int n, i, poz;
    int Q[N], st=1, dr=0;
    long long x;
    scanf("%d %d ", &n, &i);
    n=n*i/cmmdc(n, i);
    Q[++dr]=1;
    nxt[1]=-1;
    cif[1]=1;
    while(1)
    {
        x=Q[st];
        st++;
        if(x*10%n==0)
        {
            poz=x;
            sol[++sol[0]]=0;
            break;
        }
        if((x*10+1)%n==0)
        {
            poz=x;
            sol[++sol[0]]=1;
            break;
        }
        if(!nxt[x*10%n])
        {
            Q[++dr]=(x*10%n);
            nxt[x*10%n]=x;
        }
        if(!nxt[(x*10+1)%n])
        {
            Q[++dr]=((x*10+1)%n);
            nxt[(x*10+1)%n]=x;
            cif[(x*10+1)%n]=1;
        }
    }
    for(i=poz;i!=-1;i=nxt[i])
    {
        //printf("%d", cif[i]);
        sol[++sol[0]]=cif[i];
    }
    for(i=sol[0];i;i--) printf("%d", sol[i]);
}