Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- #define int long long
- pair<int, int> gcd_ext(int a, int b, int c) {
- if (a == 0) {
- return { 0ll, c / b };
- }
- auto [x0, y0] = gcd_ext(b % a, a, c);
- int y1 = x0;
- int x1 = y0 - x0 * (b / a);
- return { x1, y1 };
- }
- int gcd(int a, int b) {
- if (a == 0 || b == 0) {
- return a + b;
- }
- return gcd(b % a, a);
- }
- int best = 0;
- int ans[3] = {};
- bool solve(int a, int b, int c, int mn, int n, int ban) {
- int g = gcd(a, b);
- bool sign = c < 0;
- c = abs(c);
- c = (c / g) * g;
- if (sign) {
- c *= -1;
- }
- if (c % g != 0) {
- return false;
- }
- auto [x0, y0] = gcd_ext(a, b, c);
- bool rs = false;
- auto try_update = [&](int x1, int y1) {
- if (mn + x1 > 0 && mn + y1 > 0) {
- if (best < mn * (mn + x1) * (mn + y1)) {
- best = mn * (mn + x1) * (mn + y1);
- int arr[2] = { mn + x1, mn + y1 };
- int it = 0;
- ans[ban] = mn;
- for (int i = 0; i < 3; i++) {
- if (i == ban) { continue; }
- ans[i] = arr[it++];
- }
- }
- rs = true;
- }
- };
- {
- int k = b / g;
- int xm = (x0 % k + k) % k;
- int ym = (c - xm * a) / b;
- assert(xm * a + ym * b == c);
- try_update(xm, ym);
- int tl = 0, tr = 1e9 + 1;
- while (tr - tl > 70) {
- int tm = (tr + tl) / 2;
- int x1 = (xm + k * tm);
- int y1 = (c - x1 * a) / b;
- if (y1 > 0) {
- tl = tm;
- }
- else {
- tr = tm;
- }
- }
- for (int i = tl; i <= tr; i++) {
- int x1 = (xm + k * i);
- int y1 = (c - x1 * a) / b;
- try_update(x1, y1);
- int j = i / 2;
- x1 = (xm + k * j);
- y1 = (c - x1 * a) / b;
- try_update(x1, y1);
- }
- }
- {
- int k = a / g;
- int ym = (y0 % k + k) % k;
- int xm = (c - ym * b) / a;
- try_update(xm, ym);
- assert(xm * a + ym * b == c);
- int tl = 0, tr = 1e9 + 1;
- while (tr - tl > 70) {
- int tm = (tr + tl) / 2;
- int y1 = (ym + k * tm);
- int x1 = (c - y1 * b) / a;
- if (x1 > 0) {
- tl = tm;
- }
- else {
- tr = tm;
- }
- }
- for (int i = tl; i <= tr; i++) {
- int y1 = (ym + k * i);
- int x1 = (c - y1 * b) / a;
- try_update(x1, y1);
- int j = i / 2;
- y1 = (ym + k * j);
- x1 = (c - y1 * b) / a;
- try_update(x1, y1);
- }
- }
- //cout << x0 << ' ' << (c - x0 * a) / b << '\n';
- return rs;
- }
- /*
- ax + by + cz = n
- ax + b(x + d1) + c(x + d2) = n
- b * d1 + c * d2 = (n - ax - bx - cx)
- ax + by = n
- (b%a)x + ay = n
- (b - b/a * a) x + ay = n
- bx + a(y - b/a x) = n
- */
- bool ok(int mn, int a, int b, int c, int n) {
- int l = n - a * mn - b * mn - c * mn;
- bool rs = false;
- if (solve(b, c, l, mn, n, 0)) {
- rs = true;
- }
- if (solve(a, b, l, mn, n, 2)) {
- rs = true;
- }
- if (solve(a, c, l, mn, n, 1)) {
- rs = true;
- }
- return rs;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int a, b, c, n; cin >> n >> a >> b >> c;
- vector<int> arr(3);
- int best = 0;
- for (int l1 = 1; l1 + 2 <= n; l1++) {
- auto upd = [&](int v2, int v3) {
- int _a = l1, _b = v2, _c = v3;
- if (best < (_a / a) * (_b / b) * (_c / c)) {
- best = (_a / a) * (_b / b) * (_c / c);
- vector<int> arr1 = { _a, _b, _c };
- arr = arr1;
- }
- };
- if (l1 == 11) {
- cout << "";
- }
- int sum = n - l1;
- int d = sum / 2;
- upd(d, n - l1 - d);
- vector<int> B, C;
- int x = d;
- //19 11 1 5
- if (x % b) {
- x += (b - d % b);
- }
- while (x < sum && (int)B.size() <= 2) {
- B.push_back(x);
- x += b;
- }
- x = d;
- if (x % b) {
- x -= d % b;
- }
- while (x > 0 && (int)B.size() <= 4) {
- B.push_back(x);
- x -= b;
- }
- x = n - l1 - d;
- if (x % c) {
- x -= (x % c);
- }
- while (x > 0 && (int)C.size() <= 2) {
- C.push_back(x);
- x -= c;
- }
- x = n - l1 - d;
- if (x % c) {
- x += (c - x % c);
- }
- while (x < sum && (int)C.size() <= 4) {
- C.push_back(x);
- x += c;
- }
- for (int& i : B) {
- upd(i, sum - i);
- }
- for (int& i : C) {
- upd(sum - i, i);
- }
- }
- // sum = a + b
- // z * (sum - x) * x = z * (-x*x + sum X) = -z*x*x + sum * z * x
- // sum/2
- ////
- ////
- for (int& i : arr) {
- cout << i << ' ';
- }
- //cout << best;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement