Cod sursa(job #1719484)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 19 iunie 2016 14:20:58
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#define NMAX 2000005
#define MOD 10007
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

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

bool inQ[NMAX];
struct triplet {
	char cf;
	short lg;
	int sum,nr;
};
vector<triplet> multime;
int Prev[NMAX];
char res[NMAX];

int main() {
	int n,i,nr=1,p,ok=0,x,y;

	fin>>x>>y;
	n=x*y/__gcd(x,y);


	if(n<=1) {
		fout<<n;
		return 0;
	}

	queue<triplet> Q;
	Q.push({'1',1,1,1});

	multime.pb({0,0,0,0});
	multime.pb({'1',1,1,0});
	inQ[1]=1;
	triplet a;

	while(!Q.empty()) {
		a=Q.front();
		Q.pop();

		if(a.sum == 0) {
			ok=1;
			break;
		}

		//Prev[++nr]=a.nr;
		for(i=0;i<=1;++i)
			if(!inQ[(a.sum*10+i)%n]) {
				inQ[(a.sum*10+i)%n]=1;
				Prev[++nr]=a.nr;
				multime.pb({i+'0',a.lg+1,(a.sum*10+i)%n,nr});
				Q.push({i+'0',a.lg+1,(a.sum*10+i)%n,nr});
			}
	}

	p=a.nr;
	while(p) {
		res[multime[p].lg]=multime[p].cf;
		p=Prev[p];
	}

	fout<<res+1;


	return 0;
}