結果
問題 |
No.2868 Another String of yuusaan
|
ユーザー |
![]() |
提出日時 | 2025-02-25 19:25:25 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,120 bytes |
コンパイル時間 | 1,544 ms |
コンパイル使用メモリ | 82,232 KB |
実行使用メモリ | 65,864 KB |
最終ジャッジ日時 | 2025-02-25 19:25:31 |
合計ジャッジ時間 | 4,830 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | RE * 1 TLE * 1 -- * 16 |
ソースコード
N, K = map(int, input().split()) #サイズ s(x) について、 #s(x+1) = 4s(x)+3 #s(x+1)+1 = 4(s(x)+1) #s(x) = 8 * 4^(x-1)-1 = 2 * 4^x - 1 def solve(n, k): # print(n, k) if n == 1: return "yuusaan"[k] if k == 0: return 'y' siz = 2 * 4**(n-1)-1 if k <= siz: #これを削減したい return solve(n-1, k-1) if k <= 2*siz: return solve(n-1, k-siz-1) if k == 2*siz+1: return 's' if k <= 3*siz+1: return solve(n-1, k-2*siz-1) if k <= 4*siz+1: return solve(n-1, k-3*siz-1) if k == 4*siz+2: return 'n' K -= 1 if N <= 25 and K <= 25: exit(print(solve(N, K))) """ n, k n-1, k-1 n-2, k-2 ... n-x, k-x sizのオーダーはkに比べて非常に大きい -> k-x > 2*4^(n-x)-1となる最小のxを求める -> k' > 2 * 4-(n-(k-k')) となる最大のk' """ memo = -1 for kd in range(1, K+1): if kd > 2 * 4**(N - (K - kd)-1): memo = kd else: break # print(memo, 2*4**(N - (K - memo))) # print(memo+1, 2*4**(N - (K - memo - 1))) x = K - memo # print(memo, x) print(solve(N-x, K-x))