fork download
copy 
  1. #include <algorithm>
  2. #include <array>
  3. #include <bitset>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <climits>
  7. #include <deque>
  8. #include <fstream>
  9. #include <functional>
  10. #include <iomanip>
  11. #include <iostream>
  12. #include <limits>
  13. #include <list>
  14. #include <map>
  15. #include <numeric>
  16. #include <queue>
  17. #include <random>
  18. #include <set>
  19. #include <stack>
  20. #include <string>
  21. #include <tuple>
  22. #include <numeric>
  23. #include <unordered_map>
  24. #include <unordered_set>
  25. #include <utility>
  26. #include <vector>
  27.  
  28. using namespace std;
  29.  
  30. void solve() {
  31.     string a;
  32.     int n;
  33.     cin >> a >> n;
  34.  
  35.     vector<int> d(n);
  36.     for (int i = 0; i < n; ++i) {
  37.         cin >> d[i];
  38.     }
  39.  
  40.     int L = a.length();
  41.     int d_min = d.front();
  42.     int d_max = d.back();
  43.  
  44.     vector<unsigned long long> candidates;
  45.  
  46.     if (L > 1) {
  47.         unsigned long long val = 0;
  48.         for (int i = 0; i < L - 1; ++i) {
  49.             val = val * 10 + d_max;
  50.         }
  51.         candidates.push_back(val);
  52.     }
  53.  
  54.     int min_non_zero = -1;
  55.     for (int x : d) {
  56.         if (x > 0) {
  57.             min_non_zero = x;
  58.             break;
  59.         }
  60.     }
  61.     if (min_non_zero != -1) {
  62.         unsigned long long val = min_non_zero;
  63.         for (int i = 0; i < L; ++i) {
  64.             val = val * 10 + d_min;
  65.         }
  66.         candidates.push_back(val);
  67.     }
  68.  
  69.     unsigned long long cur = 0;
  70.     for (int i = 0; i < L; ++i) {
  71.         int digit = a[i] - '0';
  72.  
  73.         int smaller = -1;
  74.         for (int x : d) {
  75.             if (x < digit) smaller = x;
  76.         }
  77.         if (smaller != -1) {
  78.             unsigned long long val = cur * 10 + smaller;
  79.             for (int j = i + 1; j < L; ++j) {
  80.                 val = val * 10 + d_max;
  81.             }
  82.             candidates.push_back(val);
  83.         }
  84.  
  85.         int larger = -1;
  86.         for (int x : d) {
  87.             if (x > digit) {
  88.                 larger = x;
  89.                 break;
  90.             }
  91.         }
  92.         if (larger != -1) {
  93.             unsigned long long val = cur * 10 + larger;
  94.             for (int j = i + 1; j < L; ++j) {
  95.                 val = val * 10 + d_min;
  96.             }
  97.             candidates.push_back(val);
  98.         }
  99.  
  100.         bool found = false;
  101.         for (int x : d) {
  102.             if (x == digit) {
  103.                 found = true;
  104.                 break;
  105.             }
  106.         }
  107.  
  108.         if (found) {
  109.             cur = cur * 10 + digit;
  110.             if (i == L - 1) {
  111.                 candidates.push_back(cur);
  112.             }
  113.         } else {
  114.             break; 
  115.         }
  116.     }
  117.  
  118.     unsigned long long target = stoull(a);
  119.     unsigned long long min_diff = -1; 
  120.  
  121.     for (unsigned long long c : candidates) {
  122.         unsigned long long diff = (target > c) ? (target - c) : (c - target);
  123.         if (diff < min_diff) {
  124.             min_diff = diff;
  125.         }
  126.     }
  127.  
  128.     cout << min_diff << "\n";
  129. }
  130.  
  131. int main() {
  132.     ios_base::sync_with_stdio(false);
  133.     cin.tie(NULL);
  134.  
  135.     int t;
  136.     if (cin >> t) {
  137.         while (t--) {
  138.             solve();
  139.         }
  140.     }
  141.     return 0;
  142. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dYZvCX
language:
C++ (gcc 8.3)
created:
5 hours 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!