Cod sursa(job #1021206)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 3 noiembrie 2013 14:51:16
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int MAX_M = 2000002;

int A, B;
pair < int, int > prev[MAX_M][2];
queue < pair < int, int > > Q;
vector < char > ans1, ans2;
bool m[MAX_M][2];

inline int gcd(int a, int b) {
    int r;
    while(b) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

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

    f >> A >> B;

    int M = (A*B)/gcd(A, B);
    Q.push(make_pair(1%M, 1));
    m[1%M][1] = 1;
    while(!Q.empty()) {
        int x = Q.front().first, c = Q.front().second;
        Q.pop();

        int y = (x*10)%M, c1 = 0;
        if(m[y][c1] == 0) {
            m[y][c1] = 1;
            prev[y][c1] = make_pair(x, c);
            Q.push(make_pair(y, c1));
        }

        y = (x*10 + 1)%M, c1 = 1;
        if(m[y][c1] == 0) {
            m[y][c1] = 1;
            prev[y][c1] = make_pair(x, c);
            Q.push(make_pair(y, c1));
        }
    }

    int x = 0, c = 0;
    while(x != 1 || c != 1) {
        ans1.push_back(c + '0');
        int x1 = prev[x][c].first, c1 = prev[x][c].second;
        x = x1, c = c1;
    }
    ans1.push_back('1');

    x = 0, c = 1;
    while(x != 1 || c != 1) {
        ans2.push_back(c + '0');
        int x1 = prev[x][c].first, c1 = prev[x][c].second;
        x = x1, c = c1;
    }
    ans2.push_back('1');

    if(ans1.size() < ans2.size())
        for(int i = ans1.size() - 1; i >= 0; --i)
            g << ans1[i];
    else if(ans2.size() < ans1.size())
        for(int i = ans2.size() - 1; i >= 0; --i)
            g << ans2[i];
    else {
        bool ok = 1;
        for(int i = ans1.size() - 1; i >= 0; --i)
            if(ans2[i] < ans1[i]) {
                ok = 0;
                break;
            }
        if(ok)
            for(int i = ans1.size() - 1; i >= 0; --i)
                g << ans1[i];
        else for(int i = ans2.size() - 1; i >= 0; --i)
            g << ans2[i];
    }
    g << "\n";

    f.close();
    g.close();

    return 0;
}