結果
問題 | No.2727 Tetrahedron Game |
ユーザー | 👑 rin204 |
提出日時 | 2024-04-12 23:27:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 576 ms / 2,000 ms |
コード長 | 1,557 bytes |
コンパイル時間 | 272 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 172,800 KB |
最終ジャッジ日時 | 2024-10-02 23:50:52 |
合計ジャッジ時間 | 5,016 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 53 ms
61,824 KB |
testcase_01 | AC | 479 ms
78,464 KB |
testcase_02 | AC | 403 ms
78,332 KB |
testcase_03 | AC | 427 ms
172,800 KB |
testcase_04 | AC | 369 ms
153,472 KB |
testcase_05 | AC | 576 ms
147,116 KB |
testcase_06 | AC | 510 ms
154,956 KB |
testcase_07 | AC | 408 ms
122,212 KB |
testcase_08 | AC | 532 ms
147,928 KB |
testcase_09 | AC | 504 ms
134,688 KB |
ソースコード
def det(A): return ( A[0][0] * A[1][1] * A[2][2] + A[0][1] * A[1][2] * A[2][0] + A[0][2] * A[1][0] * A[2][1] - A[0][2] * A[1][1] * A[2][0] - A[0][1] * A[1][0] * A[2][2] - A[0][0] * A[1][2] * A[2][1] ) def solve(): n, k = map(int, input().split()) P = [list(map(int, input().split())) for _ in range(3)] A = list(map(int, input().split())) S = input() x = det(P) if x == 0: return None x = abs(x) x %= 606 dp = [[False] * 606 for _ in range(n + 1)] dp[0][x] = True for i, a in enumerate(A): for j in range(606): dp[i + 1][j] |= dp[i][j] dp[i + 1][j * (a + 1) % 606] |= dp[i][j] dp2 = [[0] * 606 for _ in range(n + 1)] for i in range(606): if i % 6 != 0: dp2[-1][i] = 1 elif i >= 6 * k: dp2[-1][i] = 2 else: dp2[-1][i] = 0 for i in range(n - 1, -1, -1): a = A[i] s = S[i] for j in range(606): if not dp[i][j]: continue if s == "K": dp2[i][j] = max(dp2[i + 1][j], dp2[i + 1][j * (a + 1) % 606]) else: dp2[i][j] = min(dp2[i + 1][j], dp2[i + 1][j * (a + 1) % 606]) if dp2[0][x] == 2: return True elif dp2[0][x] == 1: return None else: return False for _ in range(int(input())): res = solve() if res is None: print("D") elif res: print("K") else: print("P")