import java.io.IOException; import java.util.Scanner; public class haz { public static void main(String args[]) throws IOException { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 1000000 int cash[] = new int[n]; for (int i = 0; i < n; i++) { cash[i] = scanner.nextInt(); // 1000000 } int m = scanner.nextInt(); // 1000000 boolean winning[] = new boolean[m]; String pattern = scanner.next("[WP]+"); for (int i = 0; i < pattern.length(); i++) { winning[i] = (pattern.charAt(i) == 'W'); // true|false } scanner.close(); long oneCycleGainLoss[] = new long[n]; long zeroedin[] = new long[n]; long fullCycle = nww(m, n); long cycle = fullCycle / n; for (int i = 0; i < n; i++) { int count = 0; for (int j = i % m; count < cycle; j = (j + n) % m) { oneCycleGainLoss[i] += (winning[j]) ? 1 : -1; if (cash[i] + oneCycleGainLoss[i] == 0 && zeroedin[i] == 0) { zeroedin[i] = (count * n + i) + 1; } count++; } } long min = -1; for (long x : zeroedin) { if (x != 0) { if (min == -1 || x < min) { min = x; } } } if (min != -1) { System.out.println(min); return; } boolean negativeExists = false; for (long x : oneCycleGainLoss) { if (x < 0) { negativeExists = true; } } if (!negativeExists) { System.out.println(-1); return; } // negatives exist // somebody will get zeroed // lets first calculate in/after which cycle for (int i = 0; i < n; i++) { if (oneCycleGainLoss[i] < 0) { zeroedin[i] = (int) Math.ceil(-cash[i] / oneCycleGainLoss[i]); } } min = -1; for (int i = 0; i < n; i++) { long x = zeroedin[i]; if (x != 0) { if (min == -1 || x < min) { min = x; } } } // find out game number for this i to be zeroed in long games = (min - 1) * fullCycle; long[] finalValues = new long[n]; for (int i = 0; i < n; i++) { if (zeroedin[i] == min) { finalValues[i] = cash[i] + (min - 1) * oneCycleGainLoss[i]; } } int j = 0; for (int i = 0; i < n; i++) { if (zeroedin[i] == min) { finalValues[i] += (winning[j]) ? 1 : -1; } games++; j = (j + 1) % m; if (finalValues[i] == 0) { System.out.println(games); return; } } } private static long nww(long a, long b) { return a * b / nwd(a, b); } private static long nwd(long a, long b) { long c; while (b != 0) { c = a % b; a = b; b = c; } return a; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | import java.io.IOException; import java.util.Scanner; public class haz { public static void main(String args[]) throws IOException { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 1000000 int cash[] = new int[n]; for (int i = 0; i < n; i++) { cash[i] = scanner.nextInt(); // 1000000 } int m = scanner.nextInt(); // 1000000 boolean winning[] = new boolean[m]; String pattern = scanner.next("[WP]+"); for (int i = 0; i < pattern.length(); i++) { winning[i] = (pattern.charAt(i) == 'W'); // true|false } scanner.close(); long oneCycleGainLoss[] = new long[n]; long zeroedin[] = new long[n]; long fullCycle = nww(m, n); long cycle = fullCycle / n; for (int i = 0; i < n; i++) { int count = 0; for (int j = i % m; count < cycle; j = (j + n) % m) { oneCycleGainLoss[i] += (winning[j]) ? 1 : -1; if (cash[i] + oneCycleGainLoss[i] == 0 && zeroedin[i] == 0) { zeroedin[i] = (count * n + i) + 1; } count++; } } long min = -1; for (long x : zeroedin) { if (x != 0) { if (min == -1 || x < min) { min = x; } } } if (min != -1) { System.out.println(min); return; } boolean negativeExists = false; for (long x : oneCycleGainLoss) { if (x < 0) { negativeExists = true; } } if (!negativeExists) { System.out.println(-1); return; } // negatives exist // somebody will get zeroed // lets first calculate in/after which cycle for (int i = 0; i < n; i++) { if (oneCycleGainLoss[i] < 0) { zeroedin[i] = (int) Math.ceil(-cash[i] / oneCycleGainLoss[i]); } } min = -1; for (int i = 0; i < n; i++) { long x = zeroedin[i]; if (x != 0) { if (min == -1 || x < min) { min = x; } } } // find out game number for this i to be zeroed in long games = (min - 1) * fullCycle; long[] finalValues = new long[n]; for (int i = 0; i < n; i++) { if (zeroedin[i] == min) { finalValues[i] = cash[i] + (min - 1) * oneCycleGainLoss[i]; } } int j = 0; for (int i = 0; i < n; i++) { if (zeroedin[i] == min) { finalValues[i] += (winning[j]) ? 1 : -1; } games++; j = (j + 1) % m; if (finalValues[i] == 0) { System.out.println(games); return; } } } private static long nww(long a, long b) { return a * b / nwd(a, b); } private static long nwd(long a, long b) { long c; while (b != 0) { c = a % b; a = b; b = c; } return a; } } |