結果

問題 No.1286 Stone Skipping
ユーザー FromBooskaFromBooska
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
57,920 KB
testcase_01 AC 44 ms
57,728 KB
testcase_02 AC 51 ms
62,592 KB
testcase_03 AC 46 ms
59,008 KB
testcase_04 AC 46 ms
58,624 KB
testcase_05 AC 47 ms
59,008 KB
testcase_06 AC 45 ms
59,136 KB
testcase_07 AC 46 ms
58,752 KB
testcase_08 AC 53 ms
61,440 KB
testcase_09 AC 48 ms
61,312 KB
testcase_10 AC 49 ms
61,952 KB
testcase_11 AC 49 ms
61,440 KB
testcase_12 AC 50 ms
61,440 KB
testcase_13 AC 53 ms
63,616 KB
testcase_14 AC 52 ms
63,104 KB
testcase_15 AC 51 ms
62,592 KB
testcase_16 AC 51 ms
62,848 KB
testcase_17 AC 51 ms
62,976 KB
testcase_18 AC 43 ms
57,856 KB
testcase_19 AC 43 ms
57,984 KB
testcase_20 AC 51 ms
62,720 KB
testcase_21 AC 51 ms
62,592 KB
testcase_22 AC 51 ms
61,824 KB
testcase_23 AC 50 ms
61,824 KB
testcase_24 AC 51 ms
62,976 KB
testcase_25 AC 52 ms
63,488 KB
testcase_26 AC 51 ms
62,848 KB
testcase_27 AC 52 ms
63,104 KB
testcase_28 AC 51 ms
62,720 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