Cod sursa(job #3236638)

Utilizator tedicTheodor Ciobanu tedic Data 29 iunie 2024 21:27:55
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
int n,m,k;
pair<int,int>pre[2000005];
queue<pair<int,int>>q;
stack<int>st;
bool v[2000005];
int main()
{
    cin>>n>>m;
    k=n*m;
    int e=__gcd(n,m);
    k/=e;
    if(k==1){
        cout<<1;
        return 0;
    }
    q.push({1,1});
    int last=-1;
    //cout<<k;
    while(!q.empty())
    {
        int x=q.front().first,t=q.front().second;
        q.pop();
        int z=x*10,y=x*10+1;
        z%=k,y%=k;
        if(v[z]==0)
            q.push({z,0}),pre[z].first=x,pre[z].second=t,v[z]=1;
        if(z==0)
        {
            last=0;
            break;
        }

        if(v[y]==0)
            q.push({y,1}),pre[y].first=x,pre[y].second=t,v[y]=1;
        if(y==0)
        {
            last=1;
            break;
        }

    }
    st.push(last);
    int poz=0;
    while(pre[poz].first!=0)
        st.push(pre[poz].second),poz=pre[poz].first;
    cout<<1;
    st.pop();
    while(!st.empty())
        cout<<st.top(),st.pop();
        return 0;
}