結果
問題 | No.5006 Hidden Maze |
ユーザー | kys |
提出日時 | 2022-06-12 15:14:53 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 626 ms / 2,000 ms |
コード長 | 2,304 bytes |
コンパイル時間 | 232 ms |
実行使用メモリ | 102,424 KB |
スコア | 0 |
平均クエリ数 | 1000.00 |
最終ジャッジ日時 | 2022-06-12 15:16:01 |
合計ジャッジ時間 | 61,977 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
純コード判定しない問題か言語 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 567 ms
100,672 KB |
testcase_01 | AC | 511 ms
99,924 KB |
testcase_02 | AC | 578 ms
101,408 KB |
testcase_03 | AC | 541 ms
100,980 KB |
testcase_04 | AC | 567 ms
101,196 KB |
testcase_05 | AC | 580 ms
100,432 KB |
testcase_06 | AC | 526 ms
100,420 KB |
testcase_07 | AC | 551 ms
100,460 KB |
testcase_08 | AC | 519 ms
100,640 KB |
testcase_09 | AC | 541 ms
100,404 KB |
testcase_10 | AC | 553 ms
101,212 KB |
testcase_11 | AC | 550 ms
100,424 KB |
testcase_12 | AC | 548 ms
100,672 KB |
testcase_13 | AC | 573 ms
101,232 KB |
testcase_14 | AC | 508 ms
100,056 KB |
testcase_15 | AC | 547 ms
100,512 KB |
testcase_16 | AC | 580 ms
101,924 KB |
testcase_17 | AC | 556 ms
100,828 KB |
testcase_18 | AC | 533 ms
99,876 KB |
testcase_19 | AC | 543 ms
99,980 KB |
testcase_20 | AC | 556 ms
101,856 KB |
testcase_21 | AC | 535 ms
100,812 KB |
testcase_22 | AC | 582 ms
100,432 KB |
testcase_23 | AC | 578 ms
100,992 KB |
testcase_24 | AC | 565 ms
101,152 KB |
testcase_25 | AC | 585 ms
101,624 KB |
testcase_26 | AC | 524 ms
100,704 KB |
testcase_27 | AC | 587 ms
101,332 KB |
testcase_28 | AC | 599 ms
100,960 KB |
testcase_29 | AC | 534 ms
100,272 KB |
testcase_30 | AC | 618 ms
101,112 KB |
testcase_31 | AC | 553 ms
101,428 KB |
testcase_32 | AC | 535 ms
100,888 KB |
testcase_33 | AC | 551 ms
100,996 KB |
testcase_34 | AC | 529 ms
100,752 KB |
testcase_35 | AC | 570 ms
101,012 KB |
testcase_36 | AC | 539 ms
100,128 KB |
testcase_37 | AC | 527 ms
100,556 KB |
testcase_38 | AC | 534 ms
100,728 KB |
testcase_39 | AC | 563 ms
101,376 KB |
testcase_40 | AC | 569 ms
100,952 KB |
testcase_41 | AC | 599 ms
102,408 KB |
testcase_42 | AC | 542 ms
100,652 KB |
testcase_43 | AC | 501 ms
101,088 KB |
testcase_44 | AC | 532 ms
100,468 KB |
testcase_45 | AC | 547 ms
100,564 KB |
testcase_46 | AC | 552 ms
100,232 KB |
testcase_47 | AC | 523 ms
99,412 KB |
testcase_48 | AC | 551 ms
100,788 KB |
testcase_49 | AC | 551 ms
100,960 KB |
testcase_50 | AC | 530 ms
100,624 KB |
testcase_51 | AC | 531 ms
100,412 KB |
testcase_52 | AC | 626 ms
102,360 KB |
testcase_53 | AC | 598 ms
101,164 KB |
testcase_54 | AC | 535 ms
100,920 KB |
testcase_55 | AC | 607 ms
101,172 KB |
testcase_56 | AC | 590 ms
101,396 KB |
testcase_57 | AC | 598 ms
101,508 KB |
testcase_58 | AC | 527 ms
99,836 KB |
testcase_59 | AC | 624 ms
102,424 KB |
testcase_60 | AC | 521 ms
100,624 KB |
testcase_61 | AC | 554 ms
100,896 KB |
testcase_62 | AC | 576 ms
100,780 KB |
testcase_63 | AC | 577 ms
101,724 KB |
testcase_64 | AC | 588 ms
101,136 KB |
testcase_65 | AC | 576 ms
101,100 KB |
testcase_66 | AC | 542 ms
100,188 KB |
testcase_67 | AC | 581 ms
101,548 KB |
testcase_68 | AC | 573 ms
100,632 KB |
testcase_69 | AC | 585 ms
101,148 KB |
testcase_70 | AC | 522 ms
100,196 KB |
testcase_71 | AC | 555 ms
100,560 KB |
testcase_72 | AC | 570 ms
101,132 KB |
testcase_73 | AC | 599 ms
101,032 KB |
testcase_74 | AC | 542 ms
100,512 KB |
testcase_75 | AC | 530 ms
100,132 KB |
testcase_76 | AC | 544 ms
100,756 KB |
testcase_77 | AC | 514 ms
100,756 KB |
testcase_78 | AC | 525 ms
100,380 KB |
testcase_79 | AC | 511 ms
100,176 KB |
testcase_80 | AC | 548 ms
100,856 KB |
testcase_81 | AC | 572 ms
101,212 KB |
testcase_82 | AC | 596 ms
101,244 KB |
testcase_83 | AC | 548 ms
100,260 KB |
testcase_84 | AC | 532 ms
100,664 KB |
testcase_85 | AC | 582 ms
100,660 KB |
testcase_86 | AC | 587 ms
101,788 KB |
testcase_87 | AC | 573 ms
101,600 KB |
testcase_88 | AC | 556 ms
101,148 KB |
testcase_89 | AC | 544 ms
101,204 KB |
testcase_90 | AC | 564 ms
100,304 KB |
testcase_91 | AC | 543 ms
101,196 KB |
testcase_92 | AC | 529 ms
100,376 KB |
testcase_93 | AC | 561 ms
100,364 KB |
testcase_94 | AC | 525 ms
100,188 KB |
testcase_95 | AC | 599 ms
100,868 KB |
testcase_96 | AC | 541 ms
99,856 KB |
testcase_97 | AC | 561 ms
100,932 KB |
testcase_98 | AC | 559 ms
100,836 KB |
testcase_99 | AC | 549 ms
101,264 KB |
ソースコード
import sys input = sys.stdin.readline def iinput(): return int(input()) def sinput(): return input().rstrip() def i0input(): return int(input()) - 1 def linput(): return list(input().split()) def liinput(): return list(map(int, input().split())) def miinput(): return map(int, input().split()) def li0input(): return list(map(lambda x: int(x) - 1, input().split())) def mi0input(): return map(lambda x: int(x) - 1, input().split()) INF = 10**20 MOD = 1000000007 from random import random, seed seed(101010) def random_direction(p): for i in range(3): p[i+1] += p[i] r = random() for i in range(4): if p[i] > r: return i H, W, p = liinput() # URDL probability = [[[0.75] * W for _ in [0] * H] for _ in [0] * 4] p /= 100 direction_inv = {'U': 0, 'R': 1, 'D': 2, 'L': 3} direction = 'URDL' direction_coord = [(-1, 0), (0, 1), (1, 0), (0, -1)] for i in range(W): probability[0][0][i] = 0 probability[2][-1][i] = 0 for i in range(H): probability[1][i][-1] = 0 probability[3][i][0] = 0 for _ in [0] * 1000: place = [0, 0] res = [] for _ in [0] * 400: prob_tmp = [] for i in range(4): try: prob_tmp.append(probability[i][place[0]][place[1]]) except IndexError: print('IndexError', place) sum_prob = sum(prob_tmp) for i in range(4): prob_tmp[i] /= sum_prob d = random_direction(prob_tmp) dr, dc = direction_coord[d] place[0] += dr place[1] += dc res.append(direction[d]) print(''.join(res), flush=True) thr = iinput() if thr == -1: exit() place = [0, 0] for i in range(thr): d = direction_inv[res[i]] probability[d][place[0]][place[1]] = 1 dr, dc = direction_coord[d] place[0] += dr place[1] += dc probability[(d+2)%4][place[0]][place[1]] = 1 if len(res) > thr: d = direction_inv[res[thr]] q = probability[d][place[0]][place[1]] if q < 1: new_p = (p * q) / (p * q + 1 - q) probability[d][place[0]][place[1]] = new_p dr, dc = direction_coord[d] place[0] += dr place[1] += dc probability[(d+2)%4][place[0]][place[1]] = new_p