結果

問題 No.1286 Stone Skipping
ユーザー lam6er
提出日時 2025-03-20 21:11:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 1,514 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 62,976 KB
最終ジャッジ日時 2025-03-20 21:12:26
合計ジャッジ時間 2,574 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

def find_min_x(D):
    min_x = float('inf')
    max_k = 60  # Sufficiently large upper bound for k

    for k in range(max_k + 1):
        low = 1
        high = 2 * D
        best = None

        # Binary search for x in [1, 2D] that satisfies the sum condition
        while low <= high:
            mid = (low + high) // 2
            current_sum = 0
            current_x = mid
            for _ in range(k + 1):
                current_sum += current_x
                current_x = current_x // 2
                if current_x == 0:
                    break  # Further terms are zero, so break early
            if current_sum == D:
                best = mid
                high = mid - 1  # Try to find a smaller x
            elif current_sum < D:
                low = mid + 1
            else:
                high = mid - 1

        # After binary search, check if low is a solution
        if low <= 2 * D:
            current_sum = 0
            current_x = low
            for _ in range(k + 1):
                current_sum += current_x
                current_x = current_x // 2
                if current_x == 0:
                    break
            if current_sum == D:
                if best is None or low < best:
                    best = low

        # Update the minimum x if a valid x is found
        if best is not None and best < min_x:
            min_x = best

    return min_x if min_x != float('inf') else D

# Read input and output the result
D = int(input())
print(find_min_x(D))
0