fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. ostream &operator<<(ostream &os, vector<int> &v)
  9. {
  10.     for (int &x : v) os << (&x == &v[0] ? "[" : ", ") << x;
  11.     return os << "]";
  12. }
  13.  
  14. void solve(vector<int> &v, int S)
  15. {
  16.     cout << "入力" << endl;
  17.     cout << "硬貨: " << v << endl;
  18.     cout << "金額: " << S << endl << endl;
  19.  
  20.     int m = *max_element(v.begin(), v.end());
  21.     vector<int> N(4 * m, INT_MAX);
  22.     N[0] = 0;
  23.  
  24.     int c = 0, q = 0;
  25.  
  26.     for (int i = 0; i < S; i++) {
  27.         if (i > m) {
  28.             N[i] == N[i - m] + 1 ? c++ : c = 0;
  29.             if (c == m) {
  30.                 q = (S - i) / m + 1;
  31.                 break;
  32.             }
  33.         }
  34.  
  35.         if (i + m >= N.size()) N.resize(N.size() + 4 * m, INT_MAX);
  36.  
  37.         if (N[i] != INT_MAX) for (int j : v) N[i + j] = min(N[i + j], N[i] + 1);
  38.     }
  39.  
  40.     int n = N[S - q * m];
  41.     cout << "出力" << endl;
  42.     cout << "使用枚数: " << (n == INT_MAX ? -1 : n + q) << endl << endl << endl;
  43. }
  44.  
  45. vector<int> V[] = {{1, 7, 10}, {3, 7, 10}, {10, 19, 23, 47, 101}};
  46.  
  47. int main(void)
  48. {
  49.     for (auto &v : V) solve(v, 123456789);
  50.     return 0;
  51. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
入力
硬貨: [1, 7, 10]
金額: 123456789

出力
使用枚数: 12345681


入力
硬貨: [3, 7, 10]
金額: 123456789

出力
使用枚数: 12345681


入力
硬貨: [10, 19, 23, 47, 101]
金額: 123456789

出力
使用枚数: 1222348
https://ideone.com/52TbeF
language:
C++14 (gcc 8.3)
created:
23 days 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!