题目链接:uva 10090 - Marbles
题目大意:给出n,表示有n个珠子,现在要用若干个盒子来装。有两种盒子,一种价钱c1,可以装t1个珠子,另一种价钱c2,可以装t2个珠子。要求所卖的盒子刚好装n个珠子,并且价钱最小的方案。
解题思路:用拓展欧几里得算法求出xt1+yt2=n的一对解x′和y′,这样就有通解:
x=x′ngcd(t1,t2)+t2gcd(t1,t2)k
y=y′ngcd(t1,t2)−t1gcd(t1,t2)k
然后根据性价比选择一种盒子的个数尽量多。
#include <cstdio>
#include <cstring>
#include <cmath>
typedef long long ll;
ll n, c1, t1, c2, t2;
void gcd (ll a, ll b, ll& d, ll& x, ll& y) {
if (!b) {
d = a;
x = 1;
y = 0;
} else {
gcd(b, a%b, d, y, x);
y -= (a/b)*x;
}
}
int main () {
while (scanf("%lld", &n) == 1 && n) {
scanf("%lld%lld%lld%lld", &c1, &t1, &c2, &t2);
ll d, xi, yi, x, y;
gcd(t1, t2, d, xi, yi);
ll lower = ceil(-1.0 * n * xi / t2);
ll up = floor(1.0 * n * yi / t1);
if (lower > up || n % d) {
printf("failed\n");
continue;
}
if (c1 * t2 > c2 * t1) {
x = xi * n / d + t2 / d * lower;
y = yi * n / d - t1 / d * lower;
} else {
x = xi * n / d + t2 / d * up;
y = yi * n / d - t1 / d * up;
}
printf("%lld %lld\n", x, y);
}
return 0;
}
分享到:
相关推荐
茉莉花大理石 RxJS和Jasmine的大理石测试助手 有用的网址 支持的RxJS版本 0.2.0支持RxJS 5 。 => 0.3。*支持RxJS 6 。
产品特点打字稿错误消息先决条件笑话接收器熟悉用法对于RxJ 5: npm i jest-marbles@1 -D 对于RxJs 6: npm i jest-marbles@latest -D 在测试文件中: import { cold , hot , time } from 'jest-marbles' ;...
rxjs-marbles是一个RxJS 库,应该与任何测试框架兼容。 它包装了RxJS 并提供了与TestScheduler API所使用的相似的。 它可以在浏览器或Node中与 , , Jest , Mocha或Tape一起使用,并且支持CommonJS和ES模块捆绑...
Rxmarblesdemo 该项目是使用版本11.2.1生成的。 开发服务器 为开发服务器运行ng serve 。... 如果您更改任何源文件,该应用程序将自动重新加载。 代码脚手架 运行ng generate component component-name生成一个新的...
rxmarbles, Rx观测图交互图 RxMarbles用于实验 Rx 观察图的webapp,用于学习目的。 插件功能:可视化Rx中每个操作符的示例图表在可见对象上拖动项("") 以查看运算符的反应方式直接链接到任何范例图,比如, ...
docker build -t cescoffier/rx-marbles . 或仅使用: docker pull cescoffier/rx-marbles 跑步 docker run -i -v $PWD :/data cescoffier/rx-marbles 它搜索位于(容器) data目录中的所有.txt文件并进行解析。 ...
虹膜数据集3D大理石 如果在物理模拟中将每一行/每朵花都表示为大理石,该怎么办? 使用带有在3d中渲染虹膜数据集,并创建大理石机器的物理模拟以对数据集进行分类。 在Blender中安装Scikit-Learn(或任何其他python...
通过一个 Marbles 示例项目分析基于 fabric-sdk-node 的比较复杂的web项目的实现过程。演示如何利用 Hyperledger Fabric 在许多Marble所有者之间创建、转移或删除资产。应用程序在 Node.js 中调用在Hyperledger ...
Mythic_Marbles_CH.exe Mythic_Marbles_CH.exe
该源码为IBM Marbles项目,笔者亲测可用,其配置运行流程参考笔者博文:Hyperledger Fabric笔记4--运行IBM Marbles项目
反射大理石建筑日志: :
ObjectType string `json:"objectType"` // CouchDBfmt.Println("Marbles Init Succes
python库。 资源全名:marbles-0.11.0.tar.gz
marbles
资源分类:Python库 所属语言:Python 资源全名:marbles.core-0.9.2-py2.py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
UVA 10474
对于Sega Genesis,“ Marbles”是一款与“ Columns”类似的简单益智游戏。
yarn add -D jasmine-marbles 运行原理图 ng add @briebug/ngrx-entity-schematic 这将把原理图添加为项目依赖项(如果尚未添加),并提供配置提示。 实体名称 提供的ENTITY名称应为驼峰式或反斜线( customerOrder...
Wordpress Marbles模板