Arbitrage
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 14163 | Accepted: 5957 |
Description
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.
Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
Input
The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".
Sample Input
3 USDollar BritishPound FrenchFranc 3 USDollar 0.5 BritishPound BritishPound 10.0 FrenchFranc FrenchFranc 0.21 USDollar 3 USDollar BritishPound FrenchFranc 6 USDollar 0.5 BritishPound USDollar 4.9 FrenchFranc BritishPound 10.0 FrenchFranc BritishPound 1.99 USDollar FrenchFranc 0.09 BritishPound FrenchFranc 0.19 USDollar 0
Sample Output
Case 1: Yes Case 2: No
题意:
给出 N(1 ~ 30),代表有 N 种钱币,后给出这 N 种钱币。后给出 M 条单向关系,代表前者兑换为后者的利率。问是否能使某种钱币升值。
思路:
最短路。同样也是Bellman ford,判断正环,利率可以不断相乘来累加,找到正环就能不断累加钱币,每种钱币都用字符串表示,转化为map对应匹配即可。
AC:
#include <map> #include <string.h> #include <string> #include <cstdio> using namespace std; typedef struct { int u,v; double w; }node; node edg[1000]; int ind,n; double d[35]; int Bellman_ford() { memset(d,0,sizeof(d)); d[1] = 1; for(int i = 1;i < n;i++) for(int j = 0;j < ind;j++) { int x = edg[j].u,y = edg[j].v; double r = edg[j].w; if(d[y] < d[x] * r) d[y] = d[x] * r; } for(int i = 0;i < ind;i++) { int x = edg[i].u,y = edg[i].v; double r = edg[i].w; if(d[y] < d[x] * r) return 1; } return 0; } int main() { //freopen("test.in","r",stdin); int time = 0; map<string,int> m; while(~scanf("%d",&n) && n) { int k; ind = 0; time++; for(int i = 1;i <= n;i++) { char str[100]; scanf("%s",str); m[str] = i; } scanf("%d",&k); while(k--) { char st[100],en[100]; double val; scanf("%s%lf%s",st,&val,en); edg[ind].u = m[st]; edg[ind].v = m[en]; edg[ind].w = val; ind++; } printf("Case %d: ",time); if(Bellman_ford()) puts("Yes"); else puts("No"); } return 0; }
相关推荐
The Arbitrage Pricing Theory.pdf
statistical Arbitrage book
统计套利,Statistical Arbitrage
Arbitrage Theory in Continuous Time
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 ...
Statistical Arbitrage Algorithmic Trading Insights and Techniques.pdf
北大POJ2240-Arbitrage【Floyd】 解题报告+AC代码
Empirical tests are reported for Ross'[48] arbitrage theory of asset pricing. Using data for individual equities during the 1962–72 period, at least three and probably four priced factors are found ...
套利定价理论假设Arbitrage.pptx
arbitrage
Arbitrage is server for slow broker
2020-Statistical-Arbitrage1.组员的代码文件,在/code/组员姓名/下2.参考文献、报告,在/reference下3.会议记录,在/demo/meeting下,以日期为文件4.工作时间统计,外链腾讯在线文档,
Free theme for wordpress web
arbitrage(国际金融香港大学,WONGKaFu).pptx
arbitrage(国际金融-香港大学,WONGKaFu).pptx
SC_量化策略_价差_arbitrage_协整_原油.zip
Arbitrage_Theory_in_Continuous_Time_3rd__Bjork
三角套利 该库用于阻止链三角套利 现在与Python 2.7和Python 3.6兼容 使用pip安装: pip install triangular-arbitrage
此软件可以帮助您计算在暗黑破坏神3中拍卖行的套利利润。换句话说,它可以帮助您计算从其中一个拍卖行购买的商品(黄金或真实货币)所能赚取的收入),然后在其他拍卖行上出售。