fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5.   Given n, we want the minimum number of operations (adding 9, 99, 999, ...)
  6.   to reach a number that has at least one digit '7'.  Each operation
  7.   adds an integer whose decimal digits are all '9'.
  8.  
  9.   Algorithm:
  10.     1) If n already has '7', answer = 0.
  11.     2) Otherwise, scan y = n+1, n+2, ... until we find y that contains '7'.
  12.        Let m = y - n.
  13.     3) We look for the smallest k >= 1 such that
  14.          digit_sum(m + k) == k.
  15.        As soon as we find that, we output k.
  16.  
  17.   Complexity:  In the worst case, we’ll check maybe ~10–20 values of y
  18.   (since ~1/10 of integers contain '7'), and for each candidate m we
  19.   try k up to ~100, computing a digit‐sum in O( log_{10}(m) ) time.
  20.   That’s easily < O(10^6) total work over 10^4 test cases.
  21. */
  22.  
  23. static long long digit_sum(long long x) {
  24.     long long s = 0;
  25.     while (x > 0) {
  26.         s += (x % 10);
  27.         x /= 10;
  28.     }
  29.     return s;
  30. }
  31.  
  32. int main() {
  33.     ios::sync_with_stdio(false);
  34.     cin.tie(nullptr);
  35.  
  36.     int t;
  37.     cin >> t;
  38.     while (t--) {
  39.         long long n;
  40.         cin >> n;
  41.  
  42.         // 1) If n already contains '7', answer = 0
  43.         {
  44.             bool has7 = false;
  45.             for (long long tmp = n; tmp > 0; tmp /= 10) {
  46.                 if ((tmp % 10) == 7) {
  47.                     has7 = true;
  48.                     break;
  49.                 }
  50.             }
  51.             if (has7) {
  52.                 cout << 0 << "\n";
  53.                 continue;
  54.             }
  55.         }
  56.  
  57.         // 2) Otherwise, increment y until we see a '7' in y
  58.         long long y = n + 1;
  59.         for (;;) {
  60.             long long tmp = y;
  61.             bool has7 = false;
  62.             while (tmp > 0) {
  63.                 if ((tmp % 10) == 7) {
  64.                     has7 = true;
  65.                     break;
  66.                 }
  67.                 tmp /= 10;
  68.             }
  69.             if (has7) break;
  70.             ++y;
  71.         }
  72.  
  73.         long long m = y - n;  // total increment we want to realize
  74.  
  75.         // 3) Find the smallest k >= 1 so that digit_sum(m + k) == k
  76.         int answer = -1;
  77.         for (int k = 1; k <= 100; ++k) {
  78.             long long D = m + k;
  79.             if (digit_sum(D) == k) {
  80.                 answer = k;
  81.                 break;
  82.             }
  83.         }
  84.  
  85.         // (We are guaranteed to find some k ≤ 100 in all reasonable inputs.)
  86.         cout << answer << "\n";
  87.     }
  88.  
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
16
51
60
61
777
12345689
1000000000
2002
3001
977
989898986
80
800001
96
70
15
90
stdout
copy 
-1
-1
-1
0
-1
-1
-1
-1
0
-1
-1
-1
-1
0
-1
-1
https://ideone.com/Gj044B
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!