Advertisement
ivnikkk

Untitled

May 28th, 2022
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(mask) mask.begin(), mask.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef pair<int, int> pii;
  9. typedef long double ld;
  10. int gcd_ext(int a, int b, int& x, int& y) {
  11.     if (a == 0) {
  12.         x = 0; y = 1;
  13.         return b;
  14.     }
  15.     int x1, y1;
  16.     int d = gcd_ext(b % a, a, x1, y1);
  17.     x = y1 - (b / a) * x1;
  18.     y = x1;
  19.     return d;
  20. }
  21. signed main() {
  22. #ifdef _DEBUG
  23.     freopen("input.txt", "r", stdin);
  24.     freopen("output.txt", "w", stdout);
  25. #endif
  26.     ios_base::sync_with_stdio(false);
  27.     cin.tie(nullptr);
  28.     cout.tie(nullptr);
  29.     int n;
  30.     while (cin >> n) {
  31.         if (!n)return 0;
  32.         int c1, n1, c2, n2;
  33.         cin >> c1 >> n1 >> c2 >> n2;
  34.         int x, y;
  35.         int g = gcd_ext(n1, n2, x, y);
  36.         if (n % g) {
  37.             cout << "failed\n";
  38.             continue;
  39.         }
  40.         x *= n / g;
  41.         y *= n / g;
  42.         // x + k * n2/g >= 0
  43.         // y - k * n1/g >= 0
  44.  
  45.         // k >= - x * g  /  n2
  46.  
  47.         // k <= y * g / n1
  48.         int k1 = -(x * g - ((x*g)%n2) )/ n2;
  49.         //if ((x * g )% n2)k1++;
  50.         int k2 = (y * g - ((y * g) %n1)) / n1;
  51.         //if ((y * g) % n1) k2++;
  52.         auto func = [&](int& lo) {
  53.             return c1 * (x + lo * n2 / g) + c2 * (y - lo * n1 / g);
  54.         };
  55.         int ansk = k1;
  56.         if (func(k2) < func(k1)) {
  57.             ansk = k2;
  58.         }
  59.         x += ((ansk * n2) / g);
  60.         y -= ((ansk * n1) / g);
  61.         assert(x >= 0);
  62.         assert(y >= 0);
  63.         cout << x << ' ' << y << '\n';
  64.     }
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement