結果

問題 No.2868 Another String of yuusaan
コンテスト
ユーザー Iroha_3856
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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))
0