Cod sursa(job #1878364)

Utilizator leraValeria lera Data 14 februarie 2017 06:46:55
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
int c,ok,dp[2000005],viz[2000005];
vector<int>v;
queue<int>q;
int p;
int cmmdc(int a,int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void rec(int r)
{
    viz[r]=1;
    if(r==0)
    {
        ok=1;
        while(r!=1)
        {
            if(r==(dp[r]*10)%c)v.push_back(0);
            else v.push_back(1);
            r=dp[r];
        }
        v.push_back(1);
        for(int i=v.size()-1;i>=0;i--)fout<<v[i];
        return;
    }
    if(!viz[(r*10)%c])
    {
        dp[(r*10)%c]=r;
        q.push((r*10)%c);
    }
    if(!viz[(r*10+1)%c])
    {
        dp[(r*10+1)%c]=r;
        q.push((r*10+1)%c);
    }
}
int main()
{
    int a,b;
    fin>>a>>b;
    c=(a*b)/(cmmdc(a,b));
    for(int i=0;i<=c;i++)dp[i]=-1;
    q.push(1);
    dp[1]=1;
    while(!q.empty() && ok==0)
    {
        p=q.front();
        rec(p);
        q.pop();
    }
    return 0;
}