Problem 1367 --算法实现题 4-15 套汇问题（习题 4-32）

1367: 算法实现题 4-15 套汇问题（习题 4-32）

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $3$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心

Description

套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定 1 美元可以买 0.7 英镑，1 英镑可以买 9.5 法郎，且 1 法郎可以买到 0.16 美元。通过货币兑换，一个商人可以从 1 美元开始买入，得到 0.7×9.5×0.16=1.064 美元，从而获得 6.4%的利润。

算法设计：

给定 n 种货币c1,c2 ,  ,cn 的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。

Input

输入包含多个测试数据项。每个测试数据项的第一行中只有 1 个整数 n (1<=n<=30)，表示货币总数。其后 n 行给出 n 种货币的名称。接下来的一行中有 1 个整数 m，表示有 m 种不同的货币兑换率。其后 m 行给出 m 种不同的货币兑换率，每行有 3 个数据项 ci ， rij 和 cj ，表示货币 ci 和 cj 的兑换率为 rij。文件最后以数字 0 结束。

Output

对每个测试数据项 j，如果存在套汇的可能性则输出“case j yes”， 否则输出“case j no”。

Sample Input复制

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
0

Sample Output复制

case 1 yes
case 2 no

推荐代码 查看1367 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 陈陆瑶 290752 2018-10-17 15:20:06

赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛
AOJ