Advertisement
Guest User

Untitled

a guest
Jun 28th, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.79 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main implements Runnable {
  5. static class Mapper {
  6. Map<String, Integer> mapper = new HashMap<String, Integer>();
  7.  
  8. public int get(String s) {
  9. if (mapper.containsKey(s)) {
  10. return mapper.get(s);
  11. } else {
  12. mapper.put(s, mapper.size());
  13. return mapper.size() - 1;
  14. }
  15. }
  16. }
  17. private void solution() throws IOException {
  18. while (in.hasNext()) {
  19. int n = in.nextInt();
  20. if (n == 0) {
  21. break;
  22. }
  23. Mapper mapper = new Mapper();
  24. for (int i = 0; i < n; ++i) {
  25. in.next();
  26. }
  27. double[][] path = new double[n][n];
  28. for (double[] a : path) {
  29. Arrays.fill(a, Double.NaN);
  30. }
  31. int q = in.nextInt();
  32. for (int i = 0; i < q; ++i) {
  33. int x = mapper.get(in.next());
  34. int y = mapper.get(in.next());
  35. String t = in.next();
  36. String[] lex = t.split(":");
  37. // if (Double.isNaN(path[x][y])) {
  38. path[x][y] = Math.log((double) Integer.parseInt(lex[1]) / Integer.parseInt(lex[0]));
  39. // } else {
  40. // path[x][y] = Math.max(path[x][y], Math.log((double) Integer.parseInt(lex[1]) / Integer.parseInt(lex[0])));
  41. // }
  42. }
  43. for (int k = 0; k < n; ++k) {
  44. for (int i = 0; i < n; ++i) {
  45. if (!Double.isNaN(path[i][k])) {
  46. for (int j = 0; j < n; ++j) {
  47. if (!Double.isNaN(path[k][j])) {
  48. if (Double.isNaN(path[i][j]) || path[i][j] < path[i][k] + path[k][j]) {
  49. path[i][j] = path[i][k] + path[k][j];
  50. }
  51. }
  52. }
  53. }
  54. }
  55. }
  56. boolean ok = true;
  57. for (int i = 0; i < n; ++i) {
  58. if (!Double.isNaN(path[i][i])) {
  59. if (path[i][i] - 1e-9 > 0) {
  60. ok = false;
  61. }
  62. }
  63. }
  64. out.println(ok ? "Ok" : "Arbitrage");
  65. }
  66. }
  67.  
  68. public void run() {
  69. try {
  70. solution();
  71. in.reader.close();
  72. out.close();
  73. } catch (IOException e) {
  74. e.printStackTrace();
  75. System.exit(1);
  76. }
  77. }
  78.  
  79. public static void main(String[] args) {
  80. new Thread(null, new Main(), "", 1 << 28).start();
  81. }
  82.  
  83. private class Scanner {
  84. BufferedReader reader;
  85. StringTokenizer tokenizer;
  86.  
  87. public Scanner(Reader reader) {
  88. this.reader = new BufferedReader(reader);
  89. this.tokenizer = new StringTokenizer("");
  90. }
  91.  
  92. public boolean hasNext() throws IOException {
  93. while (!tokenizer.hasMoreTokens()) {
  94. String line = reader.readLine();
  95. if (line == null) {
  96. return false;
  97. }
  98. tokenizer = new StringTokenizer(line);
  99. }
  100. return true;
  101. }
  102.  
  103. public String next() throws IOException {
  104. hasNext();
  105. return tokenizer.nextToken();
  106. }
  107.  
  108. public int nextInt() throws IOException {
  109. return Integer.parseInt(next());
  110. }
  111. }
  112.  
  113. Scanner in = new Scanner(new InputStreamReader(System.in));
  114. PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement