| Problem | Verdict | Lang | Time | Best | Rank | Submit Time |
|---|---|---|---|---|---|---|
 | discuss10090 - | Accepted | C++11 | 0.010 | 0.000 | 1352 | 1 mins ago |
Suggest: (from codeantenna.com/a/WO2VpJHAQP)
/****************************************************************************
*
* let d = gcd (n1, n2)
* n1 * x + n2 * y = n <==> n1 / d * x + n2 / d * y = n / d ... (1)
* let n1 / d * x0 + n2 / d * y0 = 1 ... (2)
* x0 and y0 can be get by 'Extended Euclid Algorithm'.
* multiply (2) by 'n / d' and compare to (1), we get:
* x = x0 * n / d
* y = y0 * n / d
* if we have x, y such that:
* n1 * x + n2 * y = n
* then we have:
* n1 * (x + i * n2 / d) + n2 * (y - i * n1 / d) = n (i = 1, 2, ...) ... (3)
* because 'n1 * (x + i * n2 / d)' increase n1 * n2 / d while 'n2 * (y - i * n1 / d)' decrease n1 * n2 / d.
* and here 'x' and 'y' are fixed values.
*
* according to the statement of the problem, x >= 0 and y >= 0.
* so we get:
* x + i * n2 / d >= 0 and y - i * n1 / d >= 0
* solve these two inequations we get the range of 'i', let's note the range [l, u]
*
* the problem asks us to minimize 'c1 * x + c2 * y',
* let z = c1 * (x + i * n2 / d) + c2 * (y - i * n1 / d) ... (4)
* so (4) is what we want to minimize.
* since it's monotonically either increasing or decreasing, what we need to do is examine two cases when i == l and i == u.
*
****************************************************************************/
I was able to solve this problem thanks to the hint provided, although it took some time dealing with the equation
n1 * (x + i * n2 / d) + n2 * (y - i * n1 / d) = n (i = 1, 2, ...)
<=> n1*x + n2*y + n1*n2/d - n2*n1/d = n
<=> n1*x + n2*y + 0 = n
#include<bits/stdc++.h>
#define int long long
#define X first
#define Y second
using namespace std;
typedef pair<int, int> ii;
int euclid(int a, int b){
if (b==0) return a;
return euclid(b, a%b);
}
ii extended_euclid(int a, int b, ii aa, ii bb){
if (b==0) return aa;
int div= a/b;
ii cc(aa.X - div * bb.X, aa.Y - div * bb.Y);
return extended_euclid(b, a%b, bb, cc);
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int a, b, c, ca, cb;
while(cin >> c && c){
cin >> ca >> a >> cb >> b;
int d= euclid(a, b);
if (c%d) cout<<"failed\n";
else{
ii p= extended_euclid(a, b, ii(1, 0), ii(0, 1));
int q= c/d;
int x= p.X*q;
int y= p.Y*q;
//x + i * b / d >= 0 and y - i * a / d >= 0
int l= ceil(-x * d * 1.0/b);
int r= floor(y * d * 1.0/a);
int x1= x + l * b/d;
int y1= y - l * a/d;
int x2= x + r * b/d;
int y2= y - r * a/d;
if (x1*ca + y1*cb < x2*ca + y2*cb){
if (x1<0 || y1<0) cout<<"failed\n";
else cout<<x1<<" "<<y1<<"\n";
}
else
if (x2<0 || y2<0) cout<<"failed\n";
else cout<<x2<<" "<<y2<<"\n";
}
}
}
No comments:
Post a Comment