Cod sursa(job #3242583)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 12 septembrie 2024 18:22:45
Problema Multiplu Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>

using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int cmmdc( int a, int b)
{
    int rest;
    while ( b != 0 )
    {
        rest  = a % b;
        a = b;
        b = rest;
    }
    return a;
}
int coada[2000000], st = 1, dr = 0, vizitat[2000000], tata[2000000], sol[2000000];
void push( int x)
{
    coada[++dr] = x;
}
void pop_front()
{
    ++st;
}
bool empty()
{
    return st > dr;
}
int front()
{
    return coada[st];
}
int main()
{

    int a, b;
    long long x, i;
    fin >> a >> b;
    x = a * b / cmmdc(a, b);

    push(1 % x );
    while ( empty() == false )
    {
        vizitat[front()] = 1;
        int rest = (front() * 10 ) % x;
        if ( vizitat[rest] == 0 )
        {
            push( rest );
            tata[rest] = front();
        }
        rest = (front() * 10 + 1) % x;
        if ( vizitat[rest] == 0 )
        {
            push( rest );
            tata[rest] = front();
        }
        if ( front() == 0 )
            break;
        pop_front();
    }
  /*  while ( empty() == false )
    {
        fout << front() << " ";
        pop_front();
    }
    fout << endl << "-----------------------------" << endl;
    for ( i = 0; i <= 90; ++i )
        if ( tata[i] != 0 )
            fout << i << " provine din restul " << tata[i] << endl;
    return 0;*/
    int k = 0;
    i = 0;
    while ( i != 1 )
    {
        if ( (tata[i] * 10 ) % x == i )
            sol[++k] = 0;
        if ( (tata[i] * 10 + 1) % x == i)
            sol[++k] = 1;
        i = tata[i];
    }
    sol[++k] = 1;
    for ( i = k; i >= 1; --i )
        fout << sol[i];
    return 0;
}