Cod sursa(job #1448001)

Utilizator cristina_borzaCristina Borza cristina_borza Data 5 iunie 2015 22:12:22
Problema Multiplu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>

using namespace std;

ifstream f("multiplu.in");
ofstream g("multiplu.out");

int a , b , MOD , p , r;
int coada[10000] , up[10000] , cif[10000] , freq[2000005] , sol[5000];

int main()
{
    int i , inc , sf , x;
    f >> a >> b ;
    p = a * b ;
    while(b){
        r = a % b;
        a = b ;
        b = r ;
    }
    MOD = p / a;
    coada[1] = 1;
    inc = sf = 1;
    up[1] = -1;
    while(inc <= sf){
        x = coada[inc];
        if(freq[(x * 10) % MOD] == 0){
            ++sf;
            up[sf] = inc;
            cif[sf] = 0;
            coada[sf] = (x * 10) % MOD;
            freq[(x * 10) % MOD] = 1;
            if((x * 10) % MOD == 0)
                break;
        }
        if(freq[(x * 10 + 1) % MOD] == 0){
            ++sf;
            up[sf] = inc;
            cif[sf] = 1;
            coada[sf] = (x * 10 + 1) % MOD;
            freq[(x * 10 + 1) % MOD] = 1;
            if((x * 10 + 1) % MOD == 0)
                break;
        }
        ++inc;
    }
    i = sf;
    int  nr = 0 ;
    while(up[i] != -1){
        sol[++nr] = cif[i] ;
        i = up[i];
    }
    sol[++nr] = 1;
    for(int i = nr ; i >= 1; --i){
        g << sol[i];
    }
    return 0;
}