UVa 10090

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

Summary[edit]

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[edit]

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)

And about the cost

 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[edit]

  • Overflow with 32 bits integer.

Implementations[edit]

#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;
}

Optimizations[edit]

Not needed.

Input[edit]

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[edit]

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