Cod sursa(job #3286892)

Utilizator maxtraAlex Deonise maxtra Data 14 martie 2025 19:42:11
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

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

/*
strategie de rezolvare:
cmmmc(a, b) = a * b / cmmdc(a, b)

cmmdc - euclid

construim cel mai mic multiplu comun format doar din 0 si 1
folosesc BFS pentru a explora toate numerele posibile care sa fie formate din 0 si 1
ma bazez pe resturile mod cmmdc(a, b) pentru a verifica daca am gasit un multiplu corect
*/

int a, b, n, p, rest, x, k;
int prec[2000005];
char str[2000005];
bitset<2000005> cf, dist;
queue<int> q;

int main()
{
    f >> a >> b;
    
    p = a * b;
    
    while (a != b) {
        if (a > b) a -=b;
        else b-=a;
    }
    
    n = p / a; // cmmmc(a, b);
    
    // bfs pentru a gasi multiplu format doar din cifre de 0 si 1
    // folosim bfs pentru a genera multiplii de n folosind doar 0 si 1
    // pastram predecesorii pentru a reconstrui numarul final
    dist[1] = 1; // marchez restul 1 ca vizitat
    q.push(1);
    cf[1] = 1; // cifra care a dus la acest rest
    prec[1] = -1; // nu are predecesor
    
    while (dist[0] == 0) { // cautam primul multiplu de n
        rest = q.front();
        q.pop();
        
        for (int i = 0; i <= 1; i++) { // adaugam 0 si 1
            x = (rest * 10 + i) % n;
            
            if (dist[x] == 0) {
                dist[x] = 1;
                cf[x] = i; // stochez cifra folosita
                prec[x] = rest; // stocam predecesorul
                q.push(x);
            }
        }
    }
    
    // reconstruim solutia invers
    x = 0;
    while (x != -1) {
        k++;
        str[k] = cf[x] + '0'; // adaug cifra
        x = prec[x]; // ne deplasam inapoi
    }
    
    for (k; k > 0; k--) { // scriem in fisier in ordinea corecta
        g << str[k];
    }
    

    return 0;
}