fork(1) download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. static const int values[] = { 1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000 };
  5. #define values_num (sizeof(values) / sizeof(*values))
  6. int main_part11_281(int argc, char *argv[]) {
  7.     int ary[values_num] = {0};
  8.     int i, j;
  9.     int total, remain, value, value2, cnt, max_cnt, change, check_total;
  10.     total = atoi(argv[1]);
  11.     remain = total;
  12.     max_cnt = 0;
  13.     change = 0;
  14.     for (i = values_num - 1; i > -1; i--) {
  15.         value = values[i];
  16.         cnt = remain / value;
  17.         remain -= value * cnt;
  18.         ary[i] = cnt;
  19.         if (max_cnt < cnt) max_cnt = cnt;
  20.         if (cnt > 0) change++;
  21.     }
  22.     while (change > 0) {
  23.         change = 0;
  24.         for (i = values_num - 1; i > -1; i--) {
  25.             value = values[i];
  26.             if (ary[i] > 0 && max_cnt == ary[i]) {
  27.                 for (j = values_num - 1; j > -1; j--) {
  28.                     value2 = values[j];
  29.                     if (i < j) {
  30.                         if (((value2 % value) == 0) && ((ary[i] - (value2 / value)) >= (ary[j] + 1))) {
  31.                             ary[i] -= value2 / value;
  32.                             ary[j] += 1;
  33.                             change++;
  34.                         }
  35.                     } else if (i > j) {
  36.                         if (((value % value2) == 0) && ((ary[i] - 1) >= (ary[j] + (value / value2)))) {
  37.                             ary[i] -= 1;
  38.                             ary[j] += value / value2;
  39.                             change++;
  40.                         }
  41.                     }
  42.                 }
  43.             }
  44.         }
  45.         if (change > 0) {
  46.             max_cnt = 0;
  47.             check_total = 0;
  48.             for (i = 0; i < values_num; i++) {
  49.         	    value = values[i];
  50.                 cnt = ary[i];
  51.                 check_total += value * cnt;
  52.                 if (max_cnt < cnt) max_cnt = cnt;
  53.             }
  54.             if (check_total != total) {
  55.                 printf("ERROR: total=%d but check_total=%d\n", total, check_total);
  56.             }
  57.         }
  58.     }
  59.     printf("Y=%d\n=>%d\n", total, max_cnt);
  60. }
  61. int main(int argc, char *argv[]) {
  62.     char *argv1[] = {"", "500"};
  63.     char *argv2[] = {"", "300"};
  64.     char *argv3[] = {"", "40"};
  65.     char *argv4[] = {"", "60"};
  66.     if (argc <= 1) {
  67.         main_part11_281(sizeof(argv1) / sizeof(char*), argv1);
  68.         main_part11_281(sizeof(argv2) / sizeof(char*), argv2);
  69.         main_part11_281(sizeof(argv3) / sizeof(char*), argv3);
  70.         main_part11_281(sizeof(argv4) / sizeof(char*), argv4);
  71.     } else {
  72.         main_part11_281(argc, argv);
  73.     }
  74.     return 0;
  75. }
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Y=500
=>1
Y=300
=>2
Y=40
=>3
Y=60
=>1
https://ideone.com/RVA3Mk
language:
C (gcc 8.3)
created:
7 years ago
visibility:
secret

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!