Cod sursa(job #2171320)

Utilizator cella.florescuCella Florescu cella.florescu Data 15 martie 2018 11:55:10
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXP = 2e6;

int prv[MAXP], dig[MAXP];
queue <int> q;

int main()
{
    int a, b;
    ifstream fin("multiplu.in");
    fin >> a >> b;
    fin.close();
    int p = a * b / __gcd(a, b);
    dig[1] = 1; prv[1] = -1;
    q.push(1);
    while (q.empty() == false && prv[0] == 0) {
      int rest = q.front();
      q.pop();
      for (int app : {0, 1}) {
        int newr = (rest * 10 + app) % p;
        if (prv[newr] == 0) {
          q.push(newr);
          prv[newr] = rest;
          dig[newr] = app;
        }
      }
    }
    vector <int> sol;
    for (int aux = 0; aux != -1; aux = prv[aux])
      sol.push_back(dig[aux]);
    reverse(sol.begin(), sol.end());
    ofstream fout("multiplu.out");
    for (auto it : sol)
      fout << it;
    fout.close();
    return 0;
}