fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define MOD 1000000007
  7. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  8. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  9. #define ALL(x) (x).begin(),(x).end()
  10. #define ii pair<int,int>
  11. #define iii pair<int,pair<int,int>>
  12. //const int MOD = 998244353;
  13. const int MAXN = 1e5 + 7;
  14. int f[MAXN],b[MAXN];
  15. int main(){
  16.     ios_base::sync_with_stdio(false);
  17.     cin.tie(0); cout.tie(0);
  18.     //freopen("cardscore.inp","r",stdin);
  19.     //freopen("cardscore.out","w",stdout);
  20.     ll k;cin >> k;
  21.     int ans = 1e9;
  22.     memset(f,0x3f,sizeof(f));
  23.     memset(b,0x3f,sizeof(b));
  24.     FOR(i,1,9)f[i % k] = min(f[i % k],i);
  25.     FOR(i,1,100){
  26.         FOR(id,0,k - 1)
  27.             FOR(j,0,9){
  28.             int x = (id * 10 + j) % k;
  29.             b[x] = min(b[x],f[id] + j);
  30.         }
  31.         FOR(id,0,k - 1){
  32.             f[id] = min(f[id],b[id]);
  33.             b[id] = 1e9;
  34.         }
  35.     }
  36.     cout << f[0];
  37.     return 0^0;
  38.  
  39. }
Success #stdin #stdout 1.01s 5288KB
comments (?)
stdin
copy 
100000
stdout
copy 
1
https://ideone.com/BjPfuv
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!