Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(l) cerr<<#l<<' '<<l<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef long double ld;
- ll gcd_ext(ll a, ll b, ll& x, ll& y) {
- if (a == 0) {
- x = 0; y = 1;
- return b;
- }
- ll x1, y1;
- ll 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);
- while (1) {
- ll c;
- cin >> c;
- if (c == 0) {
- return 0;
- }
- ll x, y, a, b, c1, c2;
- cin >> c1 >> a >> c2 >> b;
- ll g = gcd_ext(a, b, x, y);
- if (c % g != 0) {
- cout << "failed\n";
- continue;
- }
- ll subx = x, suby = y;
- x *= c / g;
- y *= c / g;
- ll d = b / g;
- ll d2 = a / g;
- ll ans = 1e18;
- pll anss = { -1,-1 };
- if (x >= 0 && y >= 0) {
- ans = x * c1 + c2 * y;
- anss = { x,y };
- }
- for (ll k = 1; k <= 1e4; k++) {
- ll x_1 = x + k * d, y_1 = y - k * d2;
- ll x_2 = x + k * d2, y_2 = y + k * d2;
- if (x_1 >= 0 && y_1 >= 0) {
- if (x_1 * c1 + c2 * y_1 < ans) {
- ans = x_1 * c1 + c2 * y_1;
- anss = { x_1,y_1 };
- }
- }
- if (x_2 >= 0 && y_2 >= 0) {
- if (x_2 * c1 + c2 * y_2 < ans) {
- ans = x_2 * c1 + c2 * y_2;
- anss = { x_2,y_2 };
- }
- }
- }
- if (anss.first == -1 && anss.second == -1) {
- cout << "failed\n";
- continue;
- }
- cout << anss.first << ' ' << anss.second << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement