結果

問題 No.1286 Stone Skipping
コンテスト
ユーザー FromBooska
提出日時 2023-02-26 11:56:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 53 ms / 2,000 ms
コード長 1,136 bytes
コンパイル時間 227 ms
コンパイル使用メモリ 82,200 KB
実行使用メモリ 63,616 KB
最終ジャッジ日時 2024-09-14 03:53:56
合計ジャッジ時間 2,828 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 跳ね返る回数をKとすれば、Kとxという2つの不確定要素があるのでKを固定して探索
# 跳ね返る回数Kのときのxの到達距離
# (10**18)//(2**60)=0なので、K<60, そこまでのKを全探索して最小のxを求める
# Kを固定すればdistance(x, K)はxに関して単調増加

def distance(x, K):
    d = x
    for k in range(1, K+1):
        d += x//(2**k)
        # x//(2**k)式でよいかは別途チェックした
    return d

#distance(5, 2)

D = int(input())

ans = 10**20
for k in range(0, 61):
    # find smallest x
    OK = D+1
    NG = 0
    while OK-NG>1:
        mid = (OK+NG)//2
        if distance(mid, k) >= D:
            OK = mid
        else:
            NG = mid
    #print(k, OK)
    if distance(OK, k) == D:
        # Dぴったりに止まる必要ある
        # そのkにおける最低値xでDぴったりに止まらなければ、それ以上のxということはないのか?
        # それ以上のxが、その他のkで見つかったxより小さい可能性はないのか?
        # よくわからない
        ans = min(ans, OK)
print(ans)
0