Cod sursa(job #2330391)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 28 ianuarie 2019 12:20:21
Problema Multiplu Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

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

const int Dim = 2000001;
long long a,b,sum;
 long long P10[17],mi = 0x3f3f3f3f;
int save,st,dr;
int Viz[Dim],T[Dim],A[Dim];
queue < int > Q;
int sol[Dim],k = 0;
int Solve() ;
int idk;
int main() {

	
	fin >> a >> b;
	idk = (a * b) / __gcd(a,b);
	Viz[1] = 1;
		Q.push(1);
	int finish= Solve();
	fout << 1;
	
	sol[++k]=A[finish];
    while(T[finish] != 0){
        finish = T[finish];
        sol[++k]=A[finish];
    }
   for ( int i = k; i >= 1; --i)
	fout << sol[i];

}

int Solve() {
	
	
 int   st = dr = 0;
    while(true){
        int x = Q.front();
        if(Viz[x*10 % idk] == 0){
            ++dr;
            Q.push(x*10 % idk);
            A[dr] = 0;
            T[dr] = st;
            Viz[x * 10% idk]=1;
        }
        if(Viz[0] == 1)
            return dr;
        if(Viz[(x * 10 + 1 )%idk] == 0){
            Q.push((x*10+1)%idk);
            ++dr;
            A[dr]=1;
            T[dr]=st;
            Viz[(x * 10 +1) % idk]=1;
        }
        if(Viz[0]==1)
            return dr;
        Q.pop();
        ++st;
    }
}