fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <queue>
  5. #include <stack>
  6. #include <utility>
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define saleh                         \
  11.     ios_base::sync_with_stdio(false); \
  12.     cin.tie(nullptr);
  13.  
  14. #define ll long long
  15.  
  16. void KMPalgo(const string &s)
  17. {
  18.     int n = s.size();
  19.     vector<int> pi(n, 0);
  20.  
  21.     for (int i = 1; i < n; i++)
  22.     {
  23.         int j = pi[i - 1];
  24.         while (j > 0 && s[j] != s[i])
  25.             j = pi[j - 1];
  26.         if (s[j] == s[i])
  27.             j++;
  28.         pi[i] = j;
  29.     }
  30.  
  31.     // for(auto it : pi)cout<<it<<" ";cout<<endl;
  32.  
  33.     int ans = 0;
  34.     for (int i = 0; i < n - 1; i++)
  35.     {
  36.         if (pi[i] == pi[n - 1] && pi[n - 1] != 0)
  37.         {
  38.             ans = pi[i];
  39.             break;
  40.         }
  41.     }
  42.  
  43.     int length = pi[n - 1];
  44.     if (length == 0)
  45.     {
  46.         cout << "Just a legend\n";
  47.         return;
  48.     }
  49.  
  50.     for (int i = 0; i < n - 1; i++)
  51.     {
  52.         if (pi[i] == length)
  53.         {
  54.             cout << s.substr(0, length) << "\n";
  55.             return;
  56.         }
  57.     }
  58.  
  59.     length = pi[length - 1];
  60.     if (length > 0)
  61.     {
  62.         cout << length << " " << endl;
  63.         cout << s.substr(0, length) << "\n";
  64.     }
  65.     else
  66.     {
  67.         cout << "Just a legend\n";
  68.     }
  69. }
  70. bool check(int one, int five, int ten, int twenty, int fifty, int n, vector<int> &arr)
  71. {
  72.     int rem = n - (one + 5 * five + 10 * ten + 20 * twenty + 50 * fifty);
  73.     if (rem != 0)
  74.         return false;
  75.  
  76.     for (int price : arr)
  77.     {
  78.         int temp = price;
  79.         int t50 = fifty, t20 = twenty, t10 = ten, t5 = five, t1 = one;
  80.  
  81.         while (temp >= 50 && t50 > 0)
  82.             temp -= 50, t50--;
  83.         while (temp >= 20 && t20 > 0)
  84.             temp -= 20, t20--;
  85.         while (temp >= 10 && t10 > 0)
  86.             temp -= 10, t10--;
  87.         while (temp >= 5 && t5 > 0)
  88.             temp -= 5, t5--;
  89.         while (temp >= 1 && t1 > 0)
  90.             temp -= 1, t1--;
  91.  
  92.         if (temp != 0)
  93.             return false;
  94.     }
  95.  
  96.     return true;
  97. }
  98.  
  99. int main()
  100. {
  101.     saleh;
  102.     int t;
  103.     cin >> t;
  104.     while (t--)
  105.     {
  106.         int n, m;
  107.         cin >> n >> m;
  108.         vector<int> prices(m);
  109.         for (auto &price : prices)
  110.             cin >> price;
  111.  
  112.         int mini = n;
  113.         vector<int> res(5, 0);
  114.         for (int one = 0; one <= 9; one++)
  115.         {
  116.             for (int five = 0; five <= 2; five++)
  117.             {
  118.                 for (int ten = 0; ten <= 2; ten++)
  119.                 {
  120.                     for (int twenty = 0; twenty <= 4; twenty++)
  121.                     {
  122.                         int rem = n - (one + 5 * five + 10 * ten + 20 * twenty);
  123.                         if (rem < 0 || rem % 50 != 0)
  124.                             continue;
  125.  
  126.                         int fifty = rem / 50;
  127.  
  128.                         if (check(one, five, ten, twenty, fifty, n, prices))
  129.                         {
  130.                             // cout<<"__"<<endl;
  131.                             int used = one + five + ten + twenty + fifty;
  132.                             if (used < mini)
  133.                             {
  134.                                 mini = used;
  135.                                 res = {one, five, ten, twenty, fifty};
  136.                             }
  137.                         }
  138.                     }
  139.                 }
  140.             }
  141.         }
  142.  
  143.         for (auto note : res)
  144.             cout << note << " ";
  145.         cout << endl;
  146.     }
  147.  
  148.     return 0;
  149. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/75KZsG
language:
C++ (gcc 8.3)
created:
8 days 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!