fork download 
  1. #include <assert.h>
  2. #include <ctype.h>
  3. #include <stdio.h>
  4. #include <string.h>
  5.  
  6. void print (int len, const int buf[]) {
  7.     int i = 0;
  8.     while (i < len && buf[i] == 0)
  9.         ++i;
  10.     if (i == len) {
  11.         putchar('0');
  12.     } else {
  13.         do {
  14.             putchar(buf[i++] + '0');
  15.         } while (i < len);
  16.     }
  17.     putchar('\n');
  18. }
  19.  
  20. int max_used_from (int from, const int used[]) {
  21.     int i;
  22.     for (i = from; i >= 0; --i)
  23.         if (used[i])
  24.             return i;
  25.     return -1;
  26. }
  27.  
  28. int max_used (const int used[]) {
  29.     int i;
  30.     for (i = 9; i >= 0; --i)
  31.         if (used[i])
  32.             return i;
  33.     assert (!"empty used bitmap");
  34. }
  35.  
  36. int min_used_from (int from, const int used[]) {
  37.     int i;
  38.     for (i = from; i <= 9; ++i)
  39.         if (used[i])
  40.             return i;
  41.     return -1;
  42. }
  43.  
  44. int min_used (const int used[]) {
  45.     int i;
  46.     for (i = 0; i <= 9; ++i)
  47.         if (used[i])
  48.             return i;
  49.     assert (!"empty used bitmap");
  50. }
  51.  
  52. void subtract(int len, const int over[], const int under[], int diff[]) {
  53.     int carry = 0;
  54.     for (int i = len - 1; i >= 0; --i) {
  55.         int d = over[i] - carry - under[i];
  56.         if (d >= 0) {
  57.             diff[i] = d;
  58.             carry = 0;
  59.         } else {
  60.             diff[i] = d + 10;
  61.             carry = 1;
  62.         }
  63.     }
  64. }
  65.  
  66. void update_output (int len, const int buf[], const int buf_diff[],
  67.                     int *out_len, int output[], int output_diff[]) {
  68.     // Test if buf_diff < output_diff
  69.     int i;
  70.     for (i = 0; i < len; ++i)
  71.         if (buf_diff[i] != output_diff[i])
  72.             break;
  73.  
  74.     if (i < len && buf_diff[i] < output_diff[i]) {
  75.         *out_len = len;
  76.         memmove(output, buf, len * sizeof(int));
  77.         memmove(output_diff, buf_diff, len * sizeof(int));
  78.     }
  79. }
  80.  
  81. void update_output_under (int len, const int goal[], const int buf[],
  82.                           int *out_len, int output[], int output_diff[]) {
  83.     int buf_diff[len];
  84.     subtract(len, goal, buf, buf_diff);
  85.     update_output(len, buf, buf_diff, out_len, output, output_diff);
  86. }
  87.  
  88. void update_output_over (int len, const int goal[], const int buf[],
  89.                          int *out_len, int output[], int output_diff[]) {
  90.     int buf_diff[len];
  91.     subtract(len, buf, goal, buf_diff);
  92.     update_output(len, buf, buf_diff, out_len, output, output_diff);
  93. }
  94.  
  95. /* Finds the number with at most [num] different digits such that the
  96.  * difference between [goal] and [output] is the minimum.
  97.  *
  98.  * num: number of different digits in output, 0 < num <= 10
  99.  * len: length of the goal number
  100.  * goal: array of size len, forall 0 <= i < len, 0 <= goal[i] < 10, and goal[0] > 0
  101.  * out_len: number of digits in the output
  102.  * output: array of size at least [len + 1]
  103.  */
  104. void NearestDigits (int num, int len, const int goal[],
  105.                     int *out_len, int output[]) {
  106.     assert(0 < num && num <= 10);
  107.     assert(0 < len);
  108.  
  109.     {
  110.         int used[10] = {0};
  111.         for (int i = 0; i < len; ++i)
  112.             used[goal[i]] = 1;
  113.         int n = 0;
  114.         for (int i = 0; i < 10; ++i)
  115.             n += used[i];
  116.         if (n <= num) {
  117.             *out_len = len;
  118.             memmove(output, goal, len * sizeof(int));
  119.             return;
  120.         }
  121.     }
  122.  
  123.     int buf[len];
  124.     int output_diff[len];
  125.  
  126.     if (goal[0] == 1 && num == 1) {
  127.         // Special case 1: 99999 may be the closest to goal 1xxxxx
  128.         *out_len = len /*- 1*/;
  129.         output[0] = 0;
  130.         for (int i = 1 /* - 1*/; i < len /*- 1*/; ++i)
  131.             output[i] = 9;
  132.         subtract(len, goal, output, output_diff);
  133.     } else if (goal[0] == 9) {
  134.         // Special case 2: 100000 or 111111 may be the closest to goal 9xxxxx
  135.         *out_len = len + 1;
  136.         if (num == 1) {
  137.             // Special case 2a: only one digit available: 111111
  138.             for (int i = 0; i <= len; ++i)
  139.                 output[i] = 1;
  140.  
  141.             int i, left = 1;
  142.             for (i = len - 1; i >= 0; --i) {
  143.                 if (left >= goal[i]) {
  144.                     output_diff[i] = left - goal[i];
  145.                     left = 1;
  146.                 } else {
  147.                     output_diff[i] = 10 + left - goal[i];
  148.                     left = 0;
  149.                 }
  150.             }
  151.         } else {  // num > 1
  152.             // Special case 2a: can use both 0 and 1: 100000
  153.             output[0] = 1;
  154.             for (int i = 1; i <= len; ++i)
  155.                 output[i] = 0;
  156.  
  157.             int i;
  158.             for (i = 0; i < len; ++i)
  159.                 output_diff[i] = 9 - goal[i];
  160.             for (i = len - 1; i >= 0 && output_diff[i] == 9; --i)
  161.                 output_diff[i] = 0;
  162.             ++output_diff[i];
  163.         }
  164.     } else {
  165.         // Generic initialization
  166.         *out_len = 0;
  167.         for (int i = 0; i < len; ++i)
  168.             output_diff[i] = 9;
  169.     }
  170.  
  171.     int used[10] = {0};
  172.     int i, n;
  173.     for (i = 0, n = num; i < len; ++i) {
  174.         buf[i] = goal[i];
  175.  
  176.         // Two most common cases can be done greedily
  177.         if (used[goal[i]])
  178.             continue;
  179.         if (n > 2) {
  180.             used[goal[i]] = 1;
  181.             --n;
  182.             continue;
  183.         }
  184.  
  185.         if (n == 2) {
  186.             if (goal[i] > 0 && !used[9]) {
  187.                 // Possibility 1: pick one under and a nine
  188.                 buf[i] = goal[i] - 1;
  189.                 for (int j = i + 1; j < len; ++j)
  190.                     buf[j] = 9;
  191.                 update_output_under(len, goal, buf, out_len, output, output_diff);
  192.             }
  193.  
  194.             if (goal[i] < 9 && !used[0]) {
  195.                 // Possibility 2: pick one over and a zero
  196.                 buf[i] = goal[i] + 1;
  197.                 for (int j = i + 1; j < len; ++j)
  198.                     buf[j] = 0;
  199.                 update_output_over(len, goal, buf, out_len, output, output_diff);
  200.             }
  201.  
  202.             // Possibility 3-5: match goal[i], go to n == 1
  203.             buf[i] = goal[i];
  204.             used[goal[i]] = 1;
  205.             --n;
  206.             continue;
  207.         } else {  // n == 1
  208.             {
  209.                 // Possibility 3: match goal[i]
  210.                 used[goal[i]] = 1;
  211.  
  212.                 // Find out how much longer we can get freely
  213.                 int j;
  214.                 for (j = i + 1; j < len && used[goal[j]]; ++j)
  215.                     buf[j] = goal[j];
  216.  
  217.                 if (j == len)
  218.                     // should not happen: num == number_of_different_digits(goal)
  219.                     return;
  220.  
  221.                 // Possibility 3a: maximal number that's smaller than goal.
  222.                 int k = max_used_from(goal[j], used);
  223.                 if (k >= 0) {
  224.                     buf[j] = k;
  225.  
  226.                     int m = max_used(used);
  227.                     for (k = j + 1; k < len; ++k)
  228.                         buf[k] = m;
  229.                     update_output_under(len, goal, buf, out_len, output, output_diff);
  230.                 }
  231.  
  232.                 // Possibility 3b: minimal number that's larger than goal.
  233.                 k = min_used_from (goal[j], used);
  234.                 if (k >= 0) {
  235.                     buf[j] = k;
  236.  
  237.                     int m = min_used(used);
  238.                     for (k = j + 1; k < len; ++k)
  239.                         buf[k] = m;
  240.                     update_output_over(len, goal, buf, out_len, output, output_diff);
  241.                 }
  242.                 used[goal[i]] = 0;
  243.             }  // End of possibility 3
  244.  
  245.             if (goal[i] > 0) {
  246.                 // Possibility 4: take 1 lower here, find maximal
  247.                 buf[i] = goal[i] - 1;
  248.                 if (used[goal[i] - 1]) {
  249.                     // Possibility 4a: number already covered, can use 9
  250.                     for (int j = i + 1; j < len; ++j)
  251.                         buf[j] = 9;
  252.                     update_output_under(len, goal, buf, out_len, output, output_diff);
  253.                 } else {
  254.                     // Possibility 4b: new number, choose filler from used
  255.                     used[goal[i] - 1] = 1;
  256.                     int k = max_used(used);
  257.                     for (int j = i + 1; j < len; ++j)
  258.                         buf[j] = k;
  259.                     update_output_under(len, goal, buf, out_len, output, output_diff);
  260.                     used[goal[i] - 1] = 0;
  261.                 }
  262.             }  // End of possibility 4
  263.  
  264.             if (goal[i] < 9) {
  265.                 // Possibility 5: take 1 over here, find minimal
  266.                 buf[i] = goal[i] + 1;
  267.                 if (used[goal[i] + 1]) {
  268.                     // Possibility 5a: number already covered, can use 0
  269.                     for (int j = i + 1; j < len; ++j)
  270.                         buf[j] = 0;
  271.                     update_output_over(len, goal, buf, out_len, output, output_diff);
  272.                 } else {
  273.                     // Possibility 5b: new number, choose filler from used
  274.                     used[goal[i] + 1] = 1;
  275.                     int k = min_used(used);
  276.                     for (int j = i + 1; j < len; ++j)
  277.                         buf[j] = k;
  278.                     update_output_over(len, goal, buf, out_len, output, output_diff);
  279.                     used[goal[i] + 1] = 0;
  280.                 }
  281.             }  // End of possibility 5
  282.             return;
  283.         }  // n == 1
  284.     }  // for i = 0 to len - 1
  285. }  // void NearestDigits
  286.  
  287. int goal[1024];
  288. int output[1024];
  289.  
  290. int main () {
  291.     int num;
  292.     while (scanf(" %d ", &num) == 1) {
  293.         int len = 0, c;
  294.         while (isdigit(c = getchar())) {
  295.             if (len < 1023)
  296.                 goal[len++] = c - '0';
  297.         }
  298.         int out_len;
  299.         NearestDigits (num, len, goal, &out_len, output);
  300.         print(out_len, output);
  301.     }
  302.     return 0;
  303. }
  304.  
Success #stdin #stdout 0s 3312KB
comments (?)
stdin 
10 3355798521
2 262004
1 8000
1 1000
2 2243
2 88449
1 123456789
2 7099
stdout 
3355798521
262222
7777
999
2242
88448
111111111
7111
https://ideone.com/bSBiJL
language:
C++ (gcc 8.3)
created:
10 years 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!