UVA 10090 Marbles(扩展欧几里得)
Marbles
Input: standard input
Output: standard output
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:
Type 1: each box costs c1 Taka and can hold exactly
n1 marbles
Type 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
c1and n1, and the third line contains
c2 and n2. Here, c1,
c2, n1and n2 are all positive integers having values smaller than 2,000,000,000.
A test case containing a zero forn 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
Type i 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
题意:一个人有n个弹球。如今要把这些弹球所有装进盒子里。第一种盒子每一个盒子c1美元,能够恰好装n1个弹球。另外一种盒子每一个盒子c2元。能够恰好装n2个弹球。找出一种方法把这n个弹球装进盒子,每一个盒子都装满,而且花费最少的钱。
分析:如果第一种盒子买m1个,另外一种盒子买m2个,则n1*m1 + n2*m2 = n。由扩展欧几里得 ax+by=gcd(a,b)= g,如果n%g!=0。则方程无解。
联立两个方程。能够解出m1=nx/g, m2=ny/g,所以通解为m1=nx/g + bk/g, m2=ny/g - ak/g,
又由于m1和m2不能是负数,所以m1>=0, m2>=0,所以k的范围是 -nx/b <= k <= ny/a。且k必须是整数。
如果
k1=ceil(-nx/b)
k2=floor(ny/b)
假设k1>k2的话则k就没有一个可行的解。于是也是无解的情况。
设花费为cost,则cost = c1*m1 + c2*m2,
把m1和m2的表达式代入得
cost=c1*(-xn/g+bk/g)+c2*(yn/g-ak/g) = ((b*c1-a*c2)/g)*k+(c1*x*n+c2*y*n)/g
这是关于k的一次函数。单调性由b*c1-a*c2决定。
若b*c1-a*c2 >= 0,k取最小值(k1)时花费最少;否则,k取最大值(k2)时花费最少。
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL; LL extend_gcd(LL a, LL b, LL *x, LL *y)
{
LL xx, yy, g;
if(a < b) return extend_gcd(b, a, y, x);
if(b == 0) {
*x = 1;
*y = 0;
return a;
}
else {
g = extend_gcd(b, a%b, &xx, &yy);
*x = yy;
*y = (xx - a/b*yy);
return g;
}
} int main()
{
LL n, c1, n1, c2, n2, x, y;
while(cin >> n && n) {
cin >> c1 >> n1 >> c2 >> n2;
LL g = extend_gcd(n1, n2, &x, &y);
if(n % g != 0) {
cout << "failed" << endl;
continue;
}
LL mink = ceil(-n * x / (double)n2);
LL maxk = floor(n*y / (double)n1); // mink <= k <= maxk
if(mink > maxk) {
cout << "failed" << endl;
continue;
}
if(c1 * n2 <= c2 * n1) {
x = n2 / g * maxk + n / g * x;
y = n / g * y - n1 / g * maxk;
}
else {
x = n2 / g * mink + n / g * x;
y = n / g * y - n1 / g * mink;
}
cout << x << " " << y << endl;
}
return 0;
}
最新文章
- PHP 的面向方面编程
- AspNet WebApi : MessageHandler(消息处理器 )
- 《CSS那些事儿》读书笔记
- AngularJS中如何使用trigger报错$digest already in progress
- 关于 HSSF 和 XSSF 功能的开发者入门指南 (Apache POI 操作 Excel)
- 对于Netty的十一个疑问
- js判断是否安装某个android app,没有安装下载该应用(websocket通信,监听窗口失去焦点事件)
- mongodb ---->; 从入门到。。。
- js判断数组中是不是有某个元素
- [转帖]VMware Vsphere 6.0安装部署 (三) vCenter Server安装
- asp.net cookie的操作
- 15 +免费及收费的jQuery滚动插件
- 文本框改变之onpropertychange事件
- Linux相关网络命令
- Python全栈day9(Python基础)
- Portal系统中当切换学生时仍旧停留在当前页面的实现方法
- [BZOJ3669]魔法森林
- python-nmap模块常用方法说明
- 李洪强iOS开发OC[001]-NSLog函数的使用方法
- iOS调试技巧(debug)
热门文章
- ST-PUZZLE-2.0(一个益智游戏)
- ngx_lua配置及应用
- bzoj 3672 利用点分治将CDQ分治推广到树型结构上
- Codeforces Round #357 (Div. 2) B. Economy Game 水题
- HDU 5683 zxa and xor 暴力模拟
- Codeforces Round #234 (Div. 2) B. Inna and New Matrix of Candies SET的妙用
- OPENCV----在APP性能测试中的应用(一)
- 解决IE11下载文件 文件名乱码问题
- Word文档中的语法高亮显示代码
- oracle 取整的几种方法