結果

問題 No.467 隠されていたゲーム
ユーザー qwewe
提出日時 2025-05-14 13:16:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,970 bytes
コンパイル時間 284 ms
コンパイル使用メモリ 82,772 KB
実行使用メモリ 53,980 KB
最終ジャッジ日時 2025-05-14 13:18:23
合計ジャッジ時間 2,318 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def solve():
    # Read the number of allowed distances
    n = int(sys.stdin.readline())
    # Read the allowed distances
    d = list(map(int, sys.stdin.readline().split()))
    # Read the target coordinates
    x, y = map(int, sys.stdin.readline().split())

    # Calculate the target Chebyshev distance from the origin (0,0)
    # The Chebyshev distance between (x1, y1) and (x2, y2) is max(|x1-x2|, |y1-y2|).
    # From origin (0,0) to (x, y), the distance is max(|x-0|, |y-0|) = max(|x|, |y|).
    target_dist = max(abs(x), abs(y))

    # Case 1: Target is the origin (0,0)
    # If the target distance is 0, we are already at the target. Requires 0 moves.
    if target_dist == 0:
        print(0)
        return

    # Use a set for efficient checking if a distance is allowed (O(1) average time complexity)
    d_set = set(d)

    # Check for impossibility due to parity constraints.
    # If all allowed distances d_i are even:
    # A move involves changing coordinates by (dx, dy) such that max(|dx|, |dy|) is an even d_i.
    # This implies either |dx| = d_i (even) or |dy| = d_i (even), or both.
    # Starting from (0,0) (even, even), any reachable point (X, Y) must have at least one even coordinate.
    # It's impossible to reach a point where both coordinates are odd, i.e., (odd, odd).
    all_even = True
    for val in d:
        if val % 2 != 0:
            all_even = False
            break # Found an odd distance, no need to check further

    # If all distances are even and the target coordinates are both odd
    if all_even:
        # Check the parity of the absolute values of coordinates. Parity is same for x and |x|.
        if abs(x) % 2 != 0 and abs(y) % 2 != 0:
             # Target is unreachable
             print("-1")
             return

    # Case 2: Target reachable in 1 move
    # If the target Chebyshev distance is exactly one of the allowed distances d_i.
    if target_dist in d_set:
        print(1)
        return

    # Cases 3 and 4 require finding the maximum allowed distance.
    # Constraints state N >= 1 and d_i >= 1, so d is not empty and d_max >= 1.
    d_max = 0
    for val in d:
        d_max = max(d_max, val)
    
    # Case 3: Target distance is less than the maximum allowed distance.
    # If target_dist < d_max and target_dist is not one of the allowed distances (checked in Case 2),
    # it implies at least 2 moves are needed.
    # Based on analysis and examples, it appears that any such target point is reachable in exactly 2 moves,
    # unless prevented by the parity constraint (already checked).
    # For instance, one could potentially make a move of distance d_max to an intermediate point,
    # and then a second move of an appropriate distance d_j to reach the target.
    if target_dist < d_max:
         print(2)
         return

    # Case 4: Target distance is greater than the maximum allowed distance.
    # Each move can increase the Chebyshev distance from the origin by at most d_max.
    # To reach a target distance `target_dist`, we need at least ceil(target_dist / d_max) moves.
    # The analysis suggests this lower bound is generally achievable due to the flexibility of movement in 2D.
    # Calculate ceil(target_dist / d_max) using integer arithmetic.
    # ceil(A / B) = (A + B - 1) // B for positive integers A, B.
    if target_dist > d_max:
        # Python's // operator performs floor division.
        ans = (target_dist + d_max - 1) // d_max
        print(ans)
        return
    
    # Logical Fallback:
    # The case target_dist == d_max should have been handled by the 'if target_dist in d_set:' check (Case 2).
    # This is because d_max is guaranteed to be one of the values in the list d, and therefore in d_set.
    # If the program flow reaches this point, it indicates an unexpected scenario or a flaw in the logic.
    # Based on the derived logic and problem constraints, this part should not be reachable.

solve()
0