2013
11-10

Arbitrage

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.

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.

For each test case, print one line telling whether arbitrage is possible or not in the format “Case case: Yes” respectively “Case case: No”.

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


Case 1: Yes
Case 2: No


import java.util.*;
public class Main {
static int c=0;
static String[] str;
static double[][] map;
static double[] v;
static int n,m;
static boolean[] visited;

public static void main(String[] args){
Main p=new Main();
Scanner cin=new Scanner(System.in);
while(true){
c++;
n=cin.nextInt();
if(n==0) return;
str=new String[n];
map=new double[n][n];
v=new double[n];
visited=new boolean[n];
for(int i=0;i< n;i++){
str[i]=cin.next();
map[i][i]=1;
}
m=cin.nextInt();
for(int i=0;i< m;i++){
String a=cin.next();
double r=cin.nextDouble();
String b=cin.next();
map[p.find(a)][p.find(b)]=r;

}
p.solve();
}
}
void solve(){
floyd(map);
for(int i=0;i< n;i++){
if(map[i][i]>1){
System.out.println("Case " + c +  ": Yes");
return;
}
}
System.out.println("Case " + c +  ": No");
}
void floyd(double[][] map){
for(int k=0;k < n;k++)
for(int i=0;i< n;i++)
for(int j=0;j< n;j++)
if(map[i][j]< map[i][k]*map[k][j])
map[i][j]=map[i][k]*map[k][j];
}
int find(String a){
for(int i=0;i< n;i++)
if(a.equals(str[i]))
return i;
return 0;
}
}

1. 最近一直在思考，为什么煎蛋的网友总体来说素质还算可以，却有这么多五毛？我猜是因为煎蛋的读者群体大多是工作时间有一定空闲的上班族，而上班时间最有闲的职业就是我们的公务猿了……

2. “总是和我说什么初中的朋友最好，我怎样都无法超越她初中的朋友”，看到这句话我还真是无语了，你碰到这个品种真是极品啊。你也跟她说，我初中的同学，我小学的同学，你连我幼儿园的同学都不如。老娘我来上学的还是来伺候你的，你爱跟谁交朋友就跟谁交朋友去，真娘的欠收拾

3. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？

4. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

5. bottes vernies blanches

I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!