同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2052_套汇问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 40| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504279884800-Problem List-采集的数据-后羿采集器.html

Pro.ID

2052

Title

套汇问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2052

AC

Submit

Ratio

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

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

给定n种货币c₁, c₂, ..., c_n的有关兑换率，试设计一个有效算法，用以确定是否存在套汇获利的可能性。

输入

输入含多个测试数据项。每个测试数据项的第一行中只有一个整数n ( 1 ≤ n ≤ 30 )，表示货币总数。其后n行给出n种货币的名称。接下来的一行中有一个整数m，表示有m种不同的货币兑换率。其后m行给出m种不同的货币兑换率，每行有三个数据项c_i ，r_ij 和c_j ，表示货币c_i 和c_j的兑换率为 r_ij。

最后以数字0结束。