結果
問題 | No.425 ジャンケンの必勝法 |
ユーザー | 37zigen |
提出日時 | 2016-09-23 02:00:02 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,159 bytes |
コンパイル時間 | 4,307 ms |
コンパイル使用メモリ | 80,668 KB |
実行使用メモリ | 54,364 KB |
最終ジャッジ日時 | 2024-04-28 20:25:30 |
合計ジャッジ時間 | 8,969 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 149 ms
54,364 KB |
testcase_01 | AC | 155 ms
42,040 KB |
testcase_02 | AC | 156 ms
41,460 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 128 ms
42,112 KB |
testcase_11 | AC | 191 ms
42,344 KB |
testcase_12 | AC | 183 ms
42,160 KB |
testcase_13 | AC | 173 ms
47,148 KB |
testcase_14 | AC | 185 ms
42,704 KB |
testcase_15 | AC | 142 ms
41,340 KB |
testcase_16 | AC | 144 ms
41,780 KB |
testcase_17 | AC | 189 ms
42,932 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 183 ms
42,924 KB |
testcase_21 | AC | 143 ms
41,408 KB |
testcase_22 | AC | 143 ms
41,180 KB |
ソースコード
package No400番台; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class C { public static void main(String[] args) { new C().run(); } void run() { solver(); } void solver() { Scanner sc = new Scanner(System.in); double p = sc.nextDouble() / 100.0; double q = sc.nextDouble() / 100.0; ArrayList<Double> list = new ArrayList<>(); double tmp = p; int lower = 0; if (q != 0) { while (tmp != 1) { tmp = Math.min(1, tmp + q); list.add(tmp); } tmp = p; while (tmp != 0) { tmp = Math.max(0, tmp - q); list.add(tmp); lower++; } } list.add(p); list.sort(null); int n = list.size(); double[][] vec = new double[n][1]; double[][] m = new double[n][n]; for (int i = 0; i < n; i++) { m[i][i] = 1; } for (int i = 0; i < n; i++) { vec[i][0] += list.get(i) * 0.5 + (1 - list.get(i)) * 1.0 / 3.0; if (i == 0) m[i][i] -= list.get(i) * 0.5; else m[i][i - 1] -= list.get(i) * 0.5; if (i == n - 1) m[i][i] -= (1 - list.get(i)) * 1.0 / 3.0; else m[i][i + 1] -= (1 - list.get(i)) * 1.0 / 3.0; } m = Rev(m); vec = MtPrd(m, vec); System.out.println(1.0 / 3.0 + 1.0 / 3.0 * vec[lower][0]); } public static double[][] Rev(double[][] OM) { int n = OM.length, m = OM[0].length; if (n != m) return null; double[][] M = new double[n][2 * n]; m = 2 * n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { M[i][j] = OM[i][j]; } M[i][n + i] = 1; } double[][] res = operateElementarily(M); if (res == null) return null; // resotration double[][] ret = new double[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ret[i][j] = res[i][j + n]; } } return ret; } public static double[][] operateElementarily(double[][] M) { int n = M.length, m = M[0].length; int rank = n - 1; // Forward Elimination for (int i = 0; i < n; i++) { // select pivot double max = 1E-9; int maxj = -1; for (int j = i; j < n; j++) { double v = Math.abs(M[j][i]); if (v > max) { max = v; maxj = j; } } if (maxj == -1) { rank = i - 1; break; } if (maxj != i) { double[] dum = M[i]; M[i] = M[maxj]; M[maxj] = dum; } double D = M[i][i]; M[i][i] = 1; for (int j = i + 1; j < m; j++) { M[i][j] /= D; } for (int j = i + 1; j < n; j++) { double B = -M[j][i]; M[j][i] = 0; for (int k = i + 1; k < m; k++) { M[j][k] += M[i][k] * B; } } } // Back Substitution for (int i = rank; i >= 0; i--) { for (int j = rank; j >= i + 1; j--) { double B = -M[i][j]; M[i][j] = 0; for (int k = rank + 1; k < m; k++) { M[i][k] += B * M[j][k]; } } } return M; } double[][] MtPrd(double[][] A, double[][] B) { double[][] C = new double[A.length][B[0].length]; for (int i = 0; i < A.length; i++) { for (int j = 0; j < B[0].length; j++) { for (int k = 0; k < A[0].length; k++) { C[i][j] += A[i][k] * B[k][j]; } } } return C; } void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }