mickypinata

CUBE-T120: COI Coin Change

Jul 26th, 2021
1,107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int C = 10;
  5. const int M = 1e6;
  6.  
  7. int dp[M + 1], par[M + 1], coin[C + 1], cnt[C + 1];
  8.  
  9. int main(){
  10.  
  11.     int price, mxPaid, nCoin;
  12.     scanf("%d%d%d", &price, &mxPaid, &nCoin);
  13.     for(int i = 1; i <= nCoin; ++i){
  14.         scanf("%d", &coin[i]);
  15.     }
  16.  
  17.     dp[0] = 0;
  18.     for(int p = 1; p <= mxPaid; ++p){
  19.         int mn = 1e9;
  20.         for(int i = 1; i <= nCoin; ++i){
  21.             if(p >= coin[i] && dp[p - coin[i]] < mn){
  22.                 mn = dp[p - coin[i]];
  23.                 par[p] = i;
  24.             }
  25.         }
  26.         dp[p] = mn + 1;
  27.     }
  28.  
  29.     int mnCoin = 1e9;
  30.     int pCustomer = price;
  31.     for(int p = price; p <= mxPaid; ++p){
  32.         int coinCnt = dp[p] + dp[p - price];
  33.         if(coinCnt < mnCoin){
  34.             mnCoin = coinCnt;
  35.             pCustomer = p;
  36.         }
  37.     }
  38.     cout << dp[pCustomer] << ' ' << dp[pCustomer - price] << '\n';
  39.  
  40.     // Customer Coin Types
  41.     int curr = pCustomer;
  42.     while(curr != 0){
  43.         ++cnt[par[curr]];
  44.         curr -= coin[par[curr]];
  45.     }
  46.     for(int i = 1; i <= nCoin; ++i){
  47.         cout << cnt[i] << ' ';
  48.         cnt[i] = 0;
  49.     }
  50.     cout << '\n';
  51.  
  52.     // Seller Coin Types
  53.     curr = pCustomer - price;
  54.     while(curr != 0){
  55.         ++cnt[par[curr]];
  56.         curr -= coin[par[curr]];
  57.     }
  58.     for(int i = 1; i <= nCoin; ++i){
  59.         cout << cnt[i] << ' ';
  60.     }
  61.  
  62.     return 0;
  63. }
  64.  
RAW Paste Data