Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(mask) mask.begin(), mask.end()
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef pair<int, int> pii;
- typedef long double ld;
- int gcd_ext(int a, int b, int& x, int& y) {
- if (a == 0) {
- x = 0; y = 1;
- return b;
- }
- int x1, y1;
- int d = gcd_ext(b % a, a, x1, y1);
- x = y1 - (b / a) * x1;
- y = x1;
- return d;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n;
- while (cin >> n) {
- if (!n)return 0;
- int c1, n1, c2, n2;
- cin >> c1 >> n1 >> c2 >> n2;
- int x, y;
- int g = gcd_ext(n1, n2, x, y);
- if (n % g) {
- cout << "failed\n";
- continue;
- }
- x *= n / g;
- y *= n / g;
- // x + k * n2/g >= 0
- // y - k * n1/g >= 0
- // k >= - x * g / n2
- // k <= y * g / n1
- int k1 = -(x * g - ((x*g)%n2) )/ n2;
- //if ((x * g )% n2)k1++;
- int k2 = (y * g - ((y * g) %n1)) / n1;
- //if ((y * g) % n1) k2++;
- auto func = [&](int& lo) {
- return c1 * (x + lo * n2 / g) + c2 * (y - lo * n1 / g);
- };
- int ansk = k1;
- if (func(k2) < func(k1)) {
- ansk = k2;
- }
- x += ((ansk * n2) / g);
- y -= ((ansk * n1) / g);
- assert(x >= 0);
- assert(y >= 0);
- cout << x << ' ' << y << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement