Advertisement
ivnikkk

Untitled

Apr 29th, 2022
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(l) cerr<<#l<<' '<<l<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(a) a.begin(), a.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef long double ld;
  9. ll gcd_ext(ll a, ll b, ll& x, ll& y) {
  10.     if (a == 0) {
  11.         x = 0; y = 1;
  12.         return b;
  13.     }
  14.     ll x1, y1;
  15.     ll d = gcd_ext(b % a, a, x1, y1);
  16.     x = y1 - (b / a) * x1;
  17.     y = x1;
  18.     return d;
  19. }
  20. signed main() {
  21. #ifdef _DEBUG
  22.     freopen("input.txt", "r", stdin);
  23.     freopen("output.txt", "w", stdout);
  24. #endif
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(nullptr);
  27.     cout.tie(nullptr);
  28.     while (1) {
  29.         ll c;
  30.         cin >> c;
  31.         if (c == 0) {
  32.             return 0;
  33.         }
  34.         ll x, y, a, b, c1, c2;
  35.         cin >> c1 >> a >> c2 >> b;
  36.         ll g = gcd_ext(a, b, x, y);
  37.         if (c % g != 0) {
  38.             cout << "failed\n";
  39.             continue;
  40.         }
  41.         ll subx = x, suby = y;
  42.         x *= c / g;
  43.         y *= c / g;
  44.         ll d = b / g;
  45.         ll d2 = a / g;
  46.         ll ans = 1e18;
  47.         pll anss = { -1,-1 };
  48.         if (x >= 0 && y >= 0) {
  49.             ans = x * c1 + c2 * y;
  50.             anss = { x,y };
  51.         }
  52.  
  53.         for (ll k = 1; k <= 1e4; k++) {
  54.             ll x_1 = x + k * d, y_1 = y - k * d2;
  55.             ll x_2 = x + k * d2, y_2 = y + k * d2;
  56.             if (x_1 >= 0 && y_1 >= 0) {
  57.                 if (x_1 * c1 + c2 * y_1 < ans) {
  58.                     ans = x_1 * c1 + c2 * y_1;
  59.                     anss = { x_1,y_1 };
  60.                 }
  61.             }
  62.             if (x_2 >= 0 && y_2 >= 0) {
  63.                 if (x_2 * c1 + c2 * y_2 < ans) {
  64.                     ans = x_2 * c1 + c2 * y_2;
  65.                     anss = { x_2,y_2 };
  66.                 }
  67.             }
  68.         }
  69.         if (anss.first == -1 && anss.second == -1) {
  70.             cout << "failed\n";
  71.             continue;
  72.         }
  73.         cout << anss.first << ' ' << anss.second << '\n';
  74.     }
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement