Cod sursa(job #3211602)

Utilizator alexandraiacobelAlexandra Iacob alexandraiacobel Data 9 martie 2024 17:16:25
Problema Multiplu Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int Nmax=  200005;
queue<int> q;
int ant[Nmax],D,A,B,i,j;
vector<int> sol;
//Vom pastra resturilein queue ptc numarul poate sa depaseasca chiar si long long
//Vom face un anterior[] pt reconstituire
int cmmdc(int a,int b)
{
    if(b==0) return a;
    return cmmdc(b, a%b);
}
void reconst(int val)
{

    int prv = ant[val]; //9 - 0


    if(prv * 10 % D == val) sol.push_back(0);
    else sol.push_back(1);

    if(prv == -2) return;

    reconst(prv);       //1 9 0

}

int main()
{
    fin>>A>>B;
    D = A*B / cmmdc(A,B);
    q.push(1);
    int val = 1;

    for(i=0; i<=D; i++)
        ant[i] = -1; // merge si ca un vector de visited[]

    ant[1] = -2; //conditie stop reconst()
    while(!q.empty()) //merg pana am primul rest de 0
    {
        val = q.front();
        q.pop();
        int rest1 = (val * 10)%D;
        int rest2 = (val*10 +1) %D;

        if(ant[rest1]== -1) //daca nu am mai intalnit restul
            q.push(rest1),   ant[rest1] = val;

        if(ant[rest2] == -1)
            q.push(rest2),  ant[rest2] = val;
    }

    reconst(0);

    for(i=sol.size()-1; i>=0; i--) //trb sa o luam invers
    {
        fout<<sol[i];
    }
    return 0;
}