結果

問題 No.853 河原の石
ユーザー qwewe
提出日時 2025-05-14 12:59:08
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,498 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 60,416 KB
最終ジャッジ日時 2025-05-14 13:00:21
合計ジャッジ時間 4,171 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to compute ceil(a / b) using integer division
# ceil(a / b) = (a + b - 1) // b for positive integers b
# Note: Standard Python integer division // behaves like floor.

def solve():
    # Read H and W from input
    # H: initial height of the tower (number of stones)
    # W: target displacement distance
    h, w = map(int, sys.stdin.readline().split())
    
    # Calculate A = |W|, the absolute distance to move.
    # The problem is symmetric for positive and negative W.
    a = abs(w)
    
    # Base case: If the tower has 0 height (H=0) or the distance is 0 (W=0, so A=0),
    # no operations are needed.
    if h == 0 or a == 0:
        print(0)
        return

    # Initialize the total sum of operations.
    # We will use Python's arbitrary precision integers, which handle large numbers.
    total_sum = 0
    
    # Initialize the current stone layer index 'k'. We iterate k from 1 to H.
    # The cost formula derived is Sum_{k=1 to H} ceil(A / k).
    # We compute this sum efficiently using blocks.
    k = 1
    
    # Iterate while k is within the valid range [1, H].
    while k <= h:
        
        # Calculate the value q = ceil(A / k) for the current k.
        # Using integer arithmetic: q = (A + k - 1) // k
        q = (a + k - 1) // k
        
        # The value q = ceil(A / k) is non-increasing as k increases.
        
        # Optimization: If q becomes 1, it means for all subsequent k' (from k to H),
        # ceil(A / k') will also be 1 (since A/k' <= A/k <= 1 if A/k <= 1).
        # So, we can add the remaining count (H - k + 1) * 1 to the sum and terminate early.
        if q == 1:
            total_sum += (h - k + 1) 
            break
        
        # If q > 1, we are in a block where the value ceil(A / k') is q.
        # We need to find the largest k' in [k, H] such that ceil(A / k') = q.
        # This condition is equivalent to q-1 < A/k' <= q.
        # From A/k' > q-1, we get k' < A / (q - 1).
        # The largest integer k' satisfying this is floor((A - 1) / (q - 1)).
        
        # Calculate the theoretical end of the block where the value is q.
        # Note: This assumes q > 1, which is true in this branch.
        k_end_calc = (a - 1) // (q - 1)
        
        # The actual end of the block is limited by the maximum height H.
        k_end = min(h, k_end_calc)
        
        # Calculate the number of terms (k values) in the current block [k, k_end].
        # Need to ensure k_end >= k. This should hold because q = ceil(A/k) implies
        # A/k <= q, and k_end_calc is derived from the condition related to q-1.
        # If k_end calculated is less than k, there might be an edge case or error.
        # However, for positive A and k, this calculation method is standard and generally robust.
        if k_end < k:
             # This state should not be reached with correct logic.
             # If it occurs, break to prevent infinite loop or incorrect results.
             break 
             
        num_terms = k_end - k + 1
        
        # Add the contribution of this block to the total sum: value * number_of_terms
        total_sum += q * num_terms
        
        # Move k to the start of the next block.
        k = k_end + 1
        
    # Print the final calculated minimum number of operations.
    # The result needs to be followed by a newline, which print() does by default.
    print(total_sum)

# Call the solve function to execute the solution logic.
solve()
0