Advertisement
ivnikkk

Untitled

Jan 11th, 2023
657
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.18 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. #define int long long
  6. pair<int, int> gcd_ext(int a, int b, int c) {
  7.     if (a == 0) {
  8.         return { 0ll, c / b };
  9.     }
  10.     auto [x0, y0] = gcd_ext(b % a, a, c);
  11.     int y1 = x0;
  12.     int x1 = y0 - x0 * (b / a);
  13.     return { x1, y1 };
  14. }
  15. int gcd(int a, int b) {
  16.     if (a == 0 || b == 0) {
  17.         return a + b;
  18.     }
  19.     return gcd(b % a, a);
  20. }
  21. int best = 0;
  22. int ans[3] = {};
  23. bool solve(int a, int b, int c, int mn, int n, int ban) {
  24.     int g = gcd(a, b);
  25.     bool sign = c < 0;
  26.     c = abs(c);
  27.     c = (c / g) * g;
  28.     if (sign) {
  29.         c *= -1;
  30.     }
  31.     if (c % g != 0) {
  32.         return false;
  33.     }
  34.     auto [x0, y0] = gcd_ext(a, b, c);
  35.     bool rs = false;
  36.     auto try_update = [&](int x1, int y1) {
  37.         if (mn + x1 > 0 && mn + y1 > 0) {
  38.             if (best < mn * (mn + x1) * (mn + y1)) {
  39.                 best = mn * (mn + x1) * (mn + y1);
  40.                 int arr[2] = { mn + x1, mn + y1 };
  41.                 int it = 0;
  42.                 ans[ban] = mn;
  43.                 for (int i = 0; i < 3; i++) {
  44.                     if (i == ban) { continue; }
  45.                     ans[i] = arr[it++];
  46.                 }
  47.             }
  48.             rs = true;
  49.         }
  50.     };
  51.     {
  52.         int k = b / g;
  53.         int xm = (x0 % k + k) % k;
  54.         int ym = (c - xm * a) / b;
  55.         assert(xm * a + ym * b == c);
  56.         try_update(xm, ym);
  57.         int tl = 0, tr = 1e9 + 1;
  58.         while (tr - tl > 70) {
  59.             int tm = (tr + tl) / 2;
  60.             int x1 = (xm + k * tm);
  61.             int y1 = (c - x1 * a) / b;
  62.             if (y1 > 0) {
  63.                 tl = tm;
  64.             }
  65.             else {
  66.                 tr = tm;
  67.             }
  68.         }
  69.         for (int i = tl; i <= tr; i++) {
  70.             int x1 = (xm + k * i);
  71.             int y1 = (c - x1 * a) / b;
  72.             try_update(x1, y1);
  73.             int j = i / 2;
  74.             x1 = (xm + k * j);
  75.             y1 = (c - x1 * a) / b;
  76.             try_update(x1, y1);
  77.         }
  78.     }
  79.     {
  80.         int k = a / g;
  81.  
  82.         int ym = (y0 % k + k) % k;
  83.         int xm = (c - ym * b) / a;
  84.         try_update(xm, ym);
  85.         assert(xm * a + ym * b == c);
  86.         int tl = 0, tr = 1e9 + 1;
  87.         while (tr - tl > 70) {
  88.             int tm = (tr + tl) / 2;
  89.             int y1 = (ym + k * tm);
  90.             int x1 = (c - y1 * b) / a;
  91.             if (x1 > 0) {
  92.                 tl = tm;
  93.             }
  94.             else {
  95.                 tr = tm;
  96.             }
  97.         }
  98.         for (int i = tl; i <= tr; i++) {
  99.             int y1 = (ym + k * i);
  100.             int x1 = (c - y1 * b) / a;
  101.             try_update(x1, y1);
  102.             int j = i / 2;
  103.             y1 = (ym + k * j);
  104.             x1 = (c - y1 * b) / a;
  105.             try_update(x1, y1);
  106.         }
  107.     }
  108.     //cout << x0 << ' ' << (c - x0 * a) / b << '\n';
  109.     return rs;
  110. }
  111. /*
  112. ax + by + cz = n
  113.  
  114. ax + b(x + d1) + c(x + d2) = n
  115.  
  116. b * d1 + c * d2 = (n - ax - bx - cx)
  117.  
  118.  
  119. ax + by = n
  120. (b%a)x + ay = n
  121.  
  122. (b - b/a * a) x + ay = n
  123.  bx + a(y - b/a x) = n
  124.  
  125. */
  126. bool ok(int mn, int a, int b, int c, int n) {
  127.     int l = n - a * mn - b * mn - c * mn;
  128.     bool rs = false;
  129.     if (solve(b, c, l, mn, n, 0)) {
  130.         rs = true;
  131.     }
  132.     if (solve(a, b, l, mn, n, 2)) {
  133.         rs = true;
  134.     }
  135.     if (solve(a, c, l, mn, n, 1)) {
  136.         rs = true;
  137.     }
  138.     return rs;
  139. }
  140. signed main() {
  141. #ifdef _DEBUG
  142.     freopen("input.txt", "r", stdin);
  143.     freopen("output.txt", "w", stdout);
  144. #endif
  145.     ios_base::sync_with_stdio(false);
  146.     cin.tie(nullptr);
  147.     int a, b, c, n; cin >> n >> a >> b >> c;
  148.     vector<int> arr(3);
  149.     int best = 0;
  150.     for (int l1 = 1; l1 + 2 <= n; l1++) {
  151.         auto upd = [&](int v2, int v3) {
  152.             int _a = l1, _b = v2, _c = v3;
  153.             if (best < (_a / a) * (_b / b) * (_c / c)) {
  154.                 best = (_a / a) * (_b / b) * (_c / c);
  155.                 vector<int> arr1 = { _a, _b, _c };
  156.                 arr = arr1;
  157.             }
  158.         };
  159.         if (l1 == 11) {
  160.             cout << "";
  161.         }
  162.         int sum = n - l1;
  163.         int d = sum / 2;
  164.         upd(d, n - l1 - d);
  165.         vector<int> B, C;
  166.         int x = d;
  167.         //19 11 1 5
  168.         if (x % b) {
  169.             x += (b - d % b);
  170.         }
  171.         while (x < sum && (int)B.size() <= 2) {
  172.             B.push_back(x);
  173.             x += b;
  174.         }
  175.         x = d;
  176.         if (x % b) {
  177.             x -= d % b;
  178.         }
  179.         while (x > 0 && (int)B.size() <= 4) {
  180.             B.push_back(x);
  181.             x -= b;
  182.         }
  183.  
  184.         x = n - l1 - d;
  185.         if (x % c) {
  186.             x -= (x % c);
  187.         }
  188.         while (x > 0 && (int)C.size() <= 2) {
  189.             C.push_back(x);
  190.             x -= c;
  191.         }
  192.  
  193.         x = n - l1 - d;
  194.         if (x % c) {
  195.             x += (c - x % c);
  196.         }
  197.         while (x < sum && (int)C.size() <= 4) {
  198.             C.push_back(x);
  199.             x += c;
  200.         }
  201.         for (int& i : B) {
  202.             upd(i, sum - i);
  203.         }
  204.         for (int& i : C) {
  205.             upd(sum - i, i);
  206.         }
  207.     }
  208.     // sum = a + b
  209.     // z * (sum - x) * x = z * (-x*x  + sum X) = -z*x*x + sum * z * x
  210.     // sum/2
  211.     ////
  212.     ////
  213.     for (int& i : arr) {
  214.         cout << i << ' ';
  215.     }
  216.     //cout << best;
  217. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement