結果

問題 No.1286 Stone Skipping
ユーザー FromBooskaFromBooska
提出日時 2023-02-26 11:56:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 1,136 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 87,160 KB
実行使用メモリ 76,464 KB
最終ジャッジ日時 2023-10-12 04:22:57
合計ジャッジ時間 4,996 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
75,412 KB
testcase_01 AC 79 ms
75,208 KB
testcase_02 AC 93 ms
76,464 KB
testcase_03 AC 81 ms
75,160 KB
testcase_04 AC 83 ms
75,412 KB
testcase_05 AC 82 ms
75,388 KB
testcase_06 AC 83 ms
75,412 KB
testcase_07 AC 82 ms
75,112 KB
testcase_08 AC 85 ms
76,256 KB
testcase_09 AC 86 ms
75,836 KB
testcase_10 AC 88 ms
76,392 KB
testcase_11 AC 84 ms
76,004 KB
testcase_12 AC 83 ms
76,120 KB
testcase_13 AC 88 ms
76,200 KB
testcase_14 AC 85 ms
76,116 KB
testcase_15 AC 85 ms
76,208 KB
testcase_16 AC 88 ms
76,140 KB
testcase_17 AC 85 ms
76,276 KB
testcase_18 AC 79 ms
75,112 KB
testcase_19 AC 80 ms
75,376 KB
testcase_20 AC 86 ms
76,384 KB
testcase_21 AC 84 ms
76,000 KB
testcase_22 AC 87 ms
76,132 KB
testcase_23 AC 85 ms
76,200 KB
testcase_24 AC 88 ms
76,000 KB
testcase_25 AC 90 ms
76,280 KB
testcase_26 AC 87 ms
76,200 KB
testcase_27 AC 87 ms
76,148 KB
testcase_28 AC 87 ms
76,300 KB
権限があれば一括ダウンロードができます

ソースコード

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