Cod sursa(job #1436068)

Utilizator OpportunityVlad Negura Opportunity Data 14 mai 2015 23:12:14
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#define LIM 2000001

using namespace std;

vector <int> s;

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

queue <int> q;

int a,b,xa,xb, r[LIM], pre[LIM], val[LIM];

int cmmdc(int a, int b) {
	if (!b) return a; 
	return cmmdc(b, a % b);
}


int main() {
	fi >> a >> b;

	int cmmmc = (a*b)/cmmdc(a,b);
	int lastRest = 0;

	q.push(1);
	r[1] = 1;
	pre[1] = 0;
	val[1] = 1;

	
	while (!q.empty()) {
		int auxRest = q.front();

		q.pop();

		int x1 = (auxRest * 10) % cmmmc;
		int x2 = (auxRest * 10 + 1) % cmmmc;

		if (!r[x1]) {
			r[x1] = 1;
			pre[x1] = auxRest;
			val[x1] = 0;
			q.push(x1);
		}
		
		if (!r[x2]) {
			r[x2] = 1;
			pre[x2] = auxRest;
			val[x2] = 1;
			q.push(x2);
		}

		if (!x1) {
			s.push_back(0);
			lastRest = auxRest;
			break;
		}
		if (!x2) {
			s.push_back(1);
			lastRest = auxRest;
			break;
		}
	}

	while (lastRest) {
		s.push_back(val[lastRest]);
		lastRest = pre[lastRest];
	}

	reverse(s.begin(), s.end());

	for (vector <int>::iterator it = s.begin(); it != s.end();  it++) {
		fo << *it;
	}


	return 0;
}