首页 > 专题系列 > Java解POJ > POJ 2240 Arbitrage [解题报告] Java
2013
11-10

POJ 2240 Arbitrage [解题报告] Java

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. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. #!/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

  3. 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!