fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1000; inline void valid( int v, int v_min = 0 ) { assert( v >= v_min and v < N ); }
  6.  
  7. struct coins_change_t: set< int >
  8. {
  9.     struct memo_t: array< int, N >
  10.     {
  11.         memo_t()
  12.         {
  13.             fill( -1 );
  14.         }
  15.  
  16.     } memo;
  17.  
  18.     coins_change_t( int n )
  19.     {
  20.         for( int v, i = 0; i < n; i++ )
  21.             cin >> v, valid( v, 1 ), insert( v );
  22.     }
  23.  
  24.     int min_count( int rs )
  25.     {
  26.         if ( rs == 0 )
  27.             return 0;
  28.  
  29.         if ( rs < 0 )
  30.             return INT_MAX;
  31.  
  32.         auto &a = memo[ rs ];
  33.  
  34.         if ( a != -1 )
  35.             return a;
  36.  
  37.         a = INT_MAX;
  38.  
  39.         for( auto v: *this )
  40.             a = min( a, min_count( rs - v ) );
  41.  
  42. 		if ( a != INT_MAX )
  43.             a++;
  44.  
  45.         return a;
  46.     }
  47. };
  48.  
  49. int main()
  50. {
  51.     int n, val; cin >> n >> val, valid( val );
  52.  
  53.     coins_change_t coins_change( n );
  54.  
  55.     int min_count = coins_change.min_count( val );
  56.  
  57.     if ( min_count == INT_MAX )
  58.         cout << -1;
  59.     else
  60.         cout << min_count;
  61. }
  62.  
Success #stdin #stdout 0s 4248KB
comments (?)
stdin
copy 
5 34 
1 2 5 10 25
stdout
copy 
4
https://ideone.com/OPltAU
Coins Change
language:
C++14 (gcc 8.3)
created:
6 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!