Mehulcoder

SPOJMULTII

Oct 14th, 2020 (edited)
68
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Author: Mehul Chaturvedi
  3. Talent is overrated
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using pll = pair<ll, ll>;
  11. #define all(x) (x).begin(), (x).end()
  12. #define f first
  13. #define s second
  14. #define vll vector<long long>
  15. #define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
  16. #define trav(a, x) for(auto& a : x)
  17.  
  18. ll N, m;
  19. void solve() {
  20.     vector<bool> valid(10, 1);
  21.     rep(i, m) {
  22.         ll a; cin >> a;
  23.         valid[a] = 0;
  24.     }
  25.  
  26.     queue<pair<ll, string>> q;
  27.     vll v;
  28.     rep(i, 10) {
  29.         if (valid[i]) {
  30.             if (i != 0) q.push({i, to_string(i)});
  31.             v.push_back(i);
  32.         }
  33.     }
  34.     vector<bool> vis(N + 10, 0);
  35.     while (!q.empty()) {
  36.         auto temp = q.front();
  37.         q.pop();
  38.  
  39.         ll curr = temp.f % N;
  40.         string num = temp.s;
  41.         if (curr == 0) {
  42.             bool ok = 0;
  43.             cout << num << endl;
  44.             return;
  45.         }
  46.  
  47.         if (vis[curr]) continue;
  48.         vis[curr] = 1;
  49.  
  50.         trav(elem, v) {
  51.             if (!vis[(curr * 10 + elem + N) % N])
  52.                 q.push({(curr * 10 + elem + N) % N, num + to_string(elem)});
  53.         }
  54.     }
  55.  
  56.     cout << -1 << endl;
  57.     return;
  58.  
  59. }
  60.  
  61. int main(int argc , char ** argv) {
  62.     // ios_base::sync_with_stdio(false) ;
  63.     // cin.tie(NULL) ;
  64.  
  65.     ll curr = 1;
  66.     while (scanf("%lld%lld", &N, &m) == 2) {
  67.         cout << "Case " << curr << ": ";
  68.         solve();
  69.         curr++;
  70.     }
  71.  
  72.     return 0 ;
  73. }
RAW Paste Data