Marbles

分析：n1 * m1 + n2 * m2 = n (a)

以上不定方程的“非负整数”解可以用7.4节提到的解线性同余式的方法求得。再根据

C = m1 * c1 + m2 * c2 (b)

由(a)(b)两式得： <!--more-->

C = (m1 * (c1 * n2 - c2 * n1) + n * c2) / n2 (c)

从(c)式可见总成本C是m1的一次函数，在m1的取值区间内不难得到最小值。

另外，有两个特别需要注意的地方：

其一是注意计算中间结果不要溢出——虽然20亿用int就可以表示，但乘积就需要long long类型了；另外在必须要用浮点运算的地方也要注意精度。

其二是即使(a)式有整数解，但m1,m2未必同时有非负整数解，所以还需要进一步判断。

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned int uint;
typedef long long llt;
typedef long double ldt;

uint gcd(uint n1, uint n2, llt & i1, llt & i2) {
  uint d;
  if (n1 < n2) {
    d = gcd(n2, n1, i2, i1);
  }
  else if (!n2) {
    i2 = 0;
    i1 = 1;
    d = n1;
  }
  else {
    llt ii1, ii2;
    d = gcd(n2, n1 % n2, ii1, ii2);
    i1 = ii2;
    i2 = ii1 - (n1 / n2) * ii2;
  }
  return d;
}

bool marbles(uint n, uint c1, uint n1, uint c2, uint n2, uint & m1, uint & m2) {
  llt i1, i2;
  uint d = gcd(n1, n2, i1, i2);
  if (n % d)
    return false;
  if (d != 1) {
    n /= d;
    n1 /= d;
    n2 /= d;
  }
  llt low = ceil((ldt)(-1.0) * i1 * n / n2);
  llt high = floor((ldt)n / ((llt)n1 * n2) - (ldt)i1 * n / n2);
  if (low > high)
    return false;
  llt k = (llt)c1 * n2 >= (llt)c2 * n1 ? low : high;
  m1 = k * n2 + i1 * n;
  m2 = (n - n1 * m1) / n2;
  return true;
}

int main() {
  uint n;
  while (cin >> n && n) {
    uint c1, n1, c2, n2;
    cin >> c1 >> n1 >> c2 >> n2;
    uint m1, m2;
    if (marbles(n, c1, n1, c2, n2, m1, m2))
      cout << m1 << ' ' << m2 << endl;
    else
      cout << "failed" << endl;
  }
  return 0;
}