SHARE
TWEET

1

a guest Apr 23rd, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <assert.h>
  3. #define nMoneyMax 10000010
  4. using namespace std;
  5. ifstream in("sipet.in");
  6. ofstream out("sipet.out");
  7. struct pereche {
  8.     int a, b;
  9. };
  10. int nCases, nMoney, L, p[4];
  11. int A, B, C, R;
  12. pereche v[nMoneyMax];
  13. bool bb[nMoneyMax];
  14. bool isPrime(int x) {
  15.     for ( int d = 2; d * d <= x; ++ d ){
  16.         if ( x % d == 0 ){return false;}
  17.     }
  18.     return true;
  19. }
  20. int sqr(int x ) {
  21.     return x * x;
  22. }
  23. void read(){
  24.   in>>nCases;
  25.   for(int t = 1; t <= nCases; ++t) {
  26.       in>>nMoney>>p[1];
  27.       assert(isPrime(p[1]));
  28.       for (int i = 2; i <= 3; ++ i ){
  29.         for (p[i] = p[i - 1] + 1; !isPrime(p[i]); ++ p[i]);
  30.       }
  31.       for (int a = 0; a * p[1] <= nMoney; ++a){
  32.          for ( int b = 0; a * p[1] + b * p[2] <= nMoney && b < p[1]; ++b) {
  33.              int pos = a * p[1] + b * p[2];
  34.              v[pos].a = a;
  35.              v[pos].b = b;
  36.              bb[pos] = true;
  37.         }
  38.       }
  39.       bool found = false; R = -1;
  40.       for (int r = 0; r <= p[1] && R == -1; + r){
  41.           for (int c = 0; r + c * p[3] <= nMoney && c <= p[1]; ++c) {
  42.               int pos = c * p[3] + r;
  43.               if ( bb[nMoney - pos] && (R == -1 || R != -1 && A + B + C < v[nMoney - pos].a + v[nMoney - pos].b + c )) {
  44.                   found = true;
  45.                   A = v[nMoney - pos].a;
  46.                   B = v[nMoney - pos].b;
  47.                   C = c;
  48.                   R = r;
  49.               }
  50.           }
  51.       }
  52.       for (int a = 0; a * p[1] <= nMoney; ++ a ){
  53.         for (int b = 0; a * p[1] + b * p[2] <= nMoney && b < p[1]; ++ b ) {
  54.             int pos = a * p[1] + b * p[2];
  55.             bb[pos] = false;
  56.         }
  57.       }
  58.       out<<A + B + C<<" "<<A<<" "<<B<<" "<<C<<" "<<R<<'\n';
  59.   }
  60. }
  61. int main() {
  62.     read();
  63.     return 0;
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top