fork download
copy 
  1. #include <bits/stdc++.h>
  2. /*
  3.  * Payment method Problem
  4.  *
  5.  * Se considera n (n<=1000) tipuri de bancnote, de valori diferite,
  6.  * din fiecare existand un numar nelimitat de bucati.  Sa se determine
  7.  * o modalitate de plata, a valorii S, folosind un numar minim de bancnote.
  8.  
  9.  #
  10.  # We consider N (N<=1000) types of banknotes, of different values,
  11.  # of each there being an unlimited number of pieces. Determine a payment
  12.  # method of payment, of value S using a minimum numbers of banknotes.
  13.  #
  14.  # Input:
  15.  # N = 5
  16.  # S = 100
  17.  #         3,15,1,5,2
  18.  #
  19.  # Output: 6 * 15
  20.  #         2 * 5
  21.  */
  22. int B[ 1001 ],
  23.     N,
  24.     S;
  25.  
  26. void load() {
  27.    scanf("%d %d", &N,&S);
  28.    for(int i = 0; i < N; ++i) scanf("%d", &B[i]);
  29. }
  30.  
  31. void sort(int sign) {
  32.  
  33.      int aux,j;
  34.  
  35.      for(int i = 1; i < N; ++i) {
  36.  
  37.          j = i - 1;
  38.          aux = B[i];
  39.  
  40.          while(j>=0 && B[j]*sign>aux*sign) {
  41.            B[j+1] = B[j];
  42.            j--;
  43.          }
  44.          B[j+1] = aux;
  45.      }
  46. }
  47.  
  48. void solve() {
  49.  
  50.      sort(-1);
  51.      int sum;
  52.      for(int i = 0; i < N; ++i) {
  53.          if(S>=B[i]) printf("%d * %d\n", S/B[i],B[i]);
  54.          S -= (S / B[i]) * B[i];
  55.          if(!S) break;
  56.      }
  57.      if( S > 0 )printf("No Solution!");
  58. }
  59.  
  60. int main(int argc, char const *argv[]) {
  61.  
  62.   load();
  63.   solve();
  64.  
  65.   return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5440KB
comments (?)
stdin
copy 
5 100
3 15 1 5 2
stdout
copy 
6 * 15
2 * 5
https://ideone.com/P8qo5M
Payment Method
language:
C++ (gcc 8.3)
created:
1 year 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!