Cod sursa(job #3140165)

Utilizator Horia_haivasHaivas Horia Horia_haivas Data 4 iulie 2023 16:22:16
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cout << #x << " " << x << "\n"
#define debugs(x) cout << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;


struct choice
{
    int mod;
    int lastdigit;
    int lastmod;
};

int last[2000001];
int shortestpath[2000001];
bool visited[2000001];
queue<choice> q;
vector<int> ans;

signed main()
{
    ifstream fin("multiplu.in");
    ofstream fout("multiplu.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a,b,lcm,curr,i;
    choice number;
    fin >> a >> b;
    lcm=(a*b)/__gcd(a,b);
    q.push({1,-1,-1});
    while (!q.empty())
    {
        number=q.front();
        if (!visited[number.mod])
        {
            shortestpath[number.mod]=number.lastmod;
            last[number.mod]=number.lastdigit;
            visited[number.mod]=1;
            if (!visited[(number.mod*10)%lcm])
                q.push({(number.mod*10)%lcm,0,number.mod});
            if (!visited[(number.mod*10+1)%lcm])
                q.push({(number.mod*10+1)%lcm,1,number.mod});
        }
        q.pop();
    }
    curr=0;
    while (shortestpath[curr]!=-1)
    {
        ans.push_back(last[curr]);
        curr=shortestpath[curr];
    }
    ans.push_back(1);
    reverse(ans.begin(),ans.end());
    for (i=0; i<ans.size(); i++)
        fout << ans[i];
}