Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1031
I have some (say, n) marbles (small glass balls) and I am going to buy some boxes to store them. The boxes are of two types: T ype 1: each box costs c1 Taka and can hold exactly n1 marbles T ype 2: each box costs c2 Taka and can hold exactly n2 marbles I want each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since I find it difficult for me to figure out how to distribute my marbles among the boxes, I seek your help. I want your program to be efficient also. Input The input file may contain multiple test cases. Each test case begins with a line containing the integer n (1 ≤ n ≤ 2, 000, 000, 000). The second line contains c1 and n1, and the third line contains c2 and n2. Here, c1, c2, n1 and n2 are all positive integers having values smaller than 2,000,000,000. A test case containing a zero for n in the first line terminates the input. Output For each test case in the input print a line containing the minimum cost solution (two nonnegative integers m1 and m2, where mi = number of T ypei boxes required) if one exists, print ‘failed’ otherwise. If a solution exists, you may assume that it is unique.
Sample Input 43 1 3 2 4 40 5 9 5 12 0
Sample Output 13 1 failed
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll x, y, d;
void extendedEuclid(ll a, ll b) {
if(b==0) { x=1; y=0; d=a; return;}
extendedEuclid(b, a%b);
ll y1 = x-(a/b)*y;
x = y;
y = y1;
}
int main() {
ll v,n1,n2,c1,c2;
while(scanf("%lld",&v),v){
scanf("%lld %lld %lld %lld",&c1,&n1,&c2,&n2);
extendedEuclid(n1,n2);
if (v%d != 0) {
printf("failed\n");
} else {
// to get to ax + by = v
x *= v/d;
y *= v/d;
// two equations of Linear Diophantine
/* x = x0 + (b/d)n, y = y0 − (a/d)n, where n is an integer */
// derivation of n based on the fact that x and y has to be positive
// x0 + (b/d)n >= 0, solve for n: we get n >= -x0*d/b
// y0 - (a/d)n >= 0, solve for n: we get n <= y0*a/b
// putting together x0*d/b < = n <= y0*d/b
n2 /= d, n1 /= d; // divide first to prevent overflow
ll lowerbound=ceil(-(double)x/n2);
ll upperbound=floor((double)y/n1);
if(lowerbound < =upperbound) {
// compare cost
ll res1 = c1*(x+n2*lowerbound) + c2*(y-n1*lowerbound);
ll res2 = c1*(x+n2*upperbound) + c2*(y-n1*upperbound);
if (res1 < res2) {
printf("%lld %lld\n",(x+n2*lowerbound), (y-n1*lowerbound));
} else {
printf("%lld %lld\n",(x+n2*upperbound), (y-n1*upperbound));
}
} else
printf("failed\n">;
}
}
} Input
1 3
2 4
40
5 9
5 12
0
Output
failed
Demonstration
UVA Online Judge solution - 10090 - Marbles - UVA Online Judge solution in C,C++,Java