Cod sursa(job #2143652)

Utilizator mircearoataMircea Roata Palade mircearoata Data 26 februarie 2018 10:07:05
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

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

int a,b,m;

int cmmdc(int a, int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

struct nr
{
    char ch;
    int r;
    int parent;
};

vector<nr> v;

bool apare[2000001];

stringstream ss;

int main()
{
    in>>a>>b;
    m = a*b/cmmdc(a,b);
    nr num;
    num.ch='1';
    num.r=1%m;
    num.parent=-1;
    v.push_back(num);
    apare[v[0].r]=true;
    int i = 0;
    bool ok=false;
    while(!ok)
    {
        nr nou;
        nou.r=(v[i].r*10+0)%m;
        nou.ch='0';
        nou.parent = i;
        if(!apare[nou.r])
        {
            apare[nou.r]=true;
            v.push_back(nou);
        }
        if(nou.r==0)
        {
            ok=true;
            nr num = nou;
            while(num.parent != -1)
            {
                ss<<num.ch;
                num=v[num.parent];
            }
            ss<<v[0].ch;
        }
        nou.r=(v[i].r*10+1)%m;
        nou.ch='1';
        nou.parent = i;
        if(!apare[nou.r])
        {
            apare[nou.r]=true;
            v.push_back(nou);
        }
        if(nou.r==0)
        {
            ok=true;
            nr num = nou;
            while(num.parent != -1)
            {
                ss<<num.ch;
                num=v[num.parent];
            }
            ss<<v[0].ch;
        }
        i++;
    }
    string str;
    str=ss.str();
    reverse(str.begin(),str.end());
    out<<str;
    return 0;
}