UVa 10090

Summary

Find k_1 and k_2 such that n_1 m_1 + n_2 m_2 = n minimizing c_1 m_1 + c_2 m_2.

Explanation

Use Extended Euclidean Algorithm[1][2] to find a solution (probably not optimal). Analyse the cost function to find the optimal.

By definition

``` n_1*x_0 + n_2*y_0 = gcd(n_1, n_2) = g
```

If n/g is not integer, then n is not a linear combination of n_1 and n_2. Failed

``` n_1*x_0*(n/g) + n_2*y_0*(n/g) = n
n_1*[x_0*(n/g) + n_2*t/g] + n_2*[y_0*(n/g) - n_1*t/g] = n

```

Therefore

``` m_1(t) = x_0*(n/g) + n_2*t/g >= 0 // Amount of type1 boxes
m_2(t) = y_0*(n/g) - n_1*t/g >= 0 // Amount of type2 boxes
```
``` m_1(t) >= 0 -> -x_0*n/n_2 <= t
m_2(t) >= 0 -> t <= t_0*n/n_1
```
``` -> LOWER_BOUND = -x_0*n/n_2 <= t <= t_0*n/n_1 = UPPER_BOUND... (1)
```

``` cost(m_1, m_2) = cost(t) = (x_0*c_1+y_0*c_2)*(n/g) + (n_2*c_1-n_1*c_2)*(t/g) = C + M*t -> cost(t) is monotonic[3].

```

Finally, if exists a t that satisfy (1), then the minimum cost will be at

``` t = ceil( LOWER_BOUND ) or t = floor( UPPER_BOUND )
```

Gotchas

• Overflow with 32 bits integer.

Implementations

```#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;

ll gcde(ll a, ll b, ll& x, ll& y){
if( b == 0 ){
x = 1;
y = 0;
return a;
}
ll x1, y1;
ll gcd = gcde(b, a%b, x1, y1);
x = y1;
y = x1 - (a/b)*y1;
return gcd;
}

int main(){
ll n, n1, n2, c1, c2;
while( cin >> n >> c1 >> n1 >> c2 >> n2 ){
ll x, y;
ll gcd = gcde(n1, n2, x, y);
if( n % gcd != 0 ){
cout << "failed\n";
}else{
ll t1 = (ll)ceil(-(double)x*n/n2);
ll t2 = (ll)floor((double)y*n/n1);
if( t2 < t1 )
cout << "failed\n";
else{
ll cost1 = (n/gcd)*(c1*x+c2*y)+t1*(c1*n2-c2*n1)/gcd;
ll cost2 = (n/gcd)*(c1*x+c2*y)+t2*(c1*n2-c2*n1)/gcd;
ll t;
if( cost1 < cost2 ) t = t1;
else t = t2;
ll k1 = (x*n + n2*t)/gcd;
ll k2 = (y*n - n1*t)/gcd;
cout << k1 << " " << k2 << "\n";
}
}
}
return 0;
}
```

Not needed.

```9990
3 3
88 89
9991
3 3
88 89
9992
3 3
88 89
9993
3 3
88 89
9994
3 3
88 89
9997
3 3
88 89
10000
3 3
88 89
0
```

Output

```37 111
67 110
8 112
38 111
68 110
69 110
70 110
```

Categories here, use the form [[Category: Category Name]], see Categories for a list