fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  5.  
  6. #define int long long
  7. #define pb push_back
  8. #define endl '\n'
  9.  
  10. const int INF = 1e18;
  11.  
  12. void solve() {
  13.  
  14.     int a, n;
  15.     cin >> a >> n;
  16.  
  17.     vector<int> b(n);
  18.  
  19.     for (int i = 0; i < n; i++)
  20.         cin >> b[i];
  21.  
  22.     sort(b.begin(), b.end());
  23.  
  24.     string s = to_string(a);
  25.  
  26.     int len = s.size();
  27.  
  28.     int ans = INF;
  29.  
  30.     auto check = [&](string t) {
  31.  
  32.         if (t.size() > 1 && t[0] == '0')
  33.             return;
  34.  
  35.         int num = stoll(t);
  36.  
  37.         ans = min(ans, abs(a - num));
  38.     };
  39.  
  40.     string mxsmaller = "";
  41.     bool smaller = false;
  42.  
  43.     for (int i = 0; i < len; i++) {
  44.  
  45.         int cur = s[i] - '0';
  46.  
  47.         int best = -1;
  48.  
  49.         for (int d : b) {
  50.             if (d < cur)
  51.                 best = d;
  52.         }
  53.  
  54.         if (smaller) {
  55.             mxsmaller += char(b.back() + '0');
  56.         }
  57.  
  58.         else if (best != -1) {
  59.  
  60.             mxsmaller += char(best + '0');
  61.  
  62.             for (int j = i + 1; j < len; j++)
  63.                 mxsmaller += char(b.back() + '0');
  64.  
  65.             smaller = true;
  66.  
  67.             break;
  68.         }
  69.  
  70.         else {
  71.  
  72.             bool equal = false;
  73.  
  74.             for (int d : b) {
  75.                 if (d == cur)
  76.                     equal = true;
  77.             }
  78.  
  79.             if (equal)
  80.                 mxsmaller += s[i];
  81.  
  82.             else {
  83.                 mxsmaller = "";
  84.                 break;
  85.             }
  86.         }
  87.     }
  88.  
  89.     if (!mxsmaller.empty())
  90.         check(mxsmaller);
  91.  
  92.     string mingreater = "";
  93.     bool greater = false;
  94.  
  95.     for (int i = 0; i < len; i++) {
  96.  
  97.         int cur = s[i] - '0';
  98.  
  99.         int best = 10;
  100.  
  101.         for (int d : b) {
  102.             if (d > cur) {
  103.                 best = d;
  104.                 break;
  105.             }
  106.         }
  107.  
  108.         if (greater) {
  109.             mingreater += char(b[0] + '0');
  110.         }
  111.  
  112.         else if (best != 10) {
  113.  
  114.             mingreater += char(best + '0');
  115.  
  116.             for (int j = i + 1; j < len; j++)
  117.                 mingreater += char(b[0] + '0');
  118.  
  119.             greater = true;
  120.  
  121.             break;
  122.         }
  123.  
  124.         else {
  125.  
  126.             bool equal = false;
  127.  
  128.             for (int d : b) {
  129.                 if (d == cur)
  130.                     equal = true;
  131.             }
  132.  
  133.             if (equal)
  134.                 mingreater += s[i];
  135.  
  136.             else {
  137.                 mingreater = "";
  138.                 break;
  139.             }
  140.         }
  141.     }
  142.  
  143.     if (!mingreater.empty())
  144.         check(mingreater);
  145.  
  146.     string smalllen = "";
  147.  
  148.     if (len > 1) {
  149.  
  150.         int d = -1;
  151.  
  152.         for (int x : b) {
  153.             if (x != 0) {
  154.                 d = x;
  155.                 break;
  156.             }
  157.         }
  158.  
  159.         if (d != -1) {
  160.  
  161.             smalllen += char(d + '0');
  162.  
  163.             for (int i = 1; i < len - 1; i++)
  164.                 smalllen += char(b.back() + '0');
  165.  
  166.             check(smalllen);
  167.         }
  168.     }
  169.  
  170.     string biglen = "";
  171.  
  172.     int d = -1;
  173.  
  174.     for (int x : b) {
  175.         if (x != 0) {
  176.             d = x;
  177.             break;
  178.         }
  179.     }
  180.  
  181.     if (d != -1) {
  182.  
  183.         biglen += char(d + '0');
  184.  
  185.         for (int i = 1; i <= len; i++)
  186.             biglen += char(b[0] + '0');
  187.  
  188.         check(biglen);
  189.     }
  190.  
  191.     cout << ans << endl;
  192. }
  193.  
  194. int32_t main() {
  195.  
  196.     fast_io;
  197.  
  198.     int t;
  199.     cin >> t;
  200.  
  201.     while (t--) {
  202.         solve();
  203.     }
  204.  
  205.     return 0;
  206. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
0 2
0 1
11 2
1 2
222 2
3 4
3333 2
6 7
stdout
copy 
0
0
111
2656
https://ideone.com/A1O8yp
language:
C++ (gcc 8.3)
created:
9 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!