結果
問題 | No.2551 2, 3, 5, 7 Game |
ユーザー |
![]() |
提出日時 | 2023-11-21 21:49:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 214 ms / 2,357 ms |
コード長 | 1,892 bytes |
コンパイル時間 | 655 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 85,708 KB |
最終ジャッジ日時 | 2024-09-26 07:20:08 |
合計ジャッジ時間 | 2,763 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
from heapq import heappop, heappushfrom bisect import bisect_leftdef solve(t, n_list):borders = [2, 14]while True:borders.append(borders[-1] * 2)borders.append(borders[-1] * 7)if borders[-1] > 10 ** 16:breakres = []for n in n_list:i = bisect_left(borders, n)if i % 2 == 0:res.append("ryota")else:res.append("sepa")return resdef solve_tle(t, n_list):reduce_dict = {2: -1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1,10: 1, 11: 1, 12: 1, 13: 1, 14: 1, 15: -1}h = []for n in n_list:heappush(h, -n)while len(h):p = heappop(h)p *= -1if p in reduce_dict.keys():continueelse:reduce_dict[p] = 0for d in [2, 3, 5, 7]:q = (p + d - 1) // dif q in reduce_dict.keys():continueelse:heappush(h, -q)# print(len(reduce_dict))for p in sorted(reduce_dict.keys()):if reduce_dict[p] != 0:continuer = -1for d in [2, 3, 5, 7]:q = (p + d - 1) // dif reduce_dict[q] == -1:r = 1reduce_dict[p] = r# for p in sorted(reduce_dict.keys()):# print(p, reduce_dict[p])res = []for n in n_list:if reduce_dict[n] == 1:res.append("sepa")else:res.append("ryota")return resdef main():t = int(input())n_list = [int(input()) for _ in range(t)]res = solve(t, n_list)for r in res:print(r)def test():assert solve(3, [11, 2, 2357]) == ["sepa", "ryota", "sepa"]# print([(i + 2, r) for i, r in enumerate(solve(10000, [i + 2 for i in range(10000)]))])if __name__ == "__main__":test()main()