結果

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

ソースコード

diff # 

def solve():
    n = int(input())
    d_list = list(map(int, input().split()))
    x, y = map(int, input().split())
    x_abs = abs(x)
    y_abs = abs(y)
    D = max(x_abs, y_abs)
    if D == 0:
        print(0)
        return
    
    # Check if all d_i are even and D is odd
    all_even = True
    for d in d_list:
        if d % 2 != 0:
            all_even = False
            break
    if all_even and (D % 2 != 0):
        print(-1)
        return
    
    max_d = max(d_list)
    k_min = (D + max_d - 1) // max_d  # ceil(D / max_d)
    
    # Check k in k_min, k_min+1, k_min+2
    for k in [k_min, k_min + 1, k_min + 2]:
        # Initialize DP for k steps
        # At step 0, sum is 0 (mod0=0, mod1=-1)
        current_mod0 = 0
        current_mod1 = -1
        for step in range(1, k+1):
            next_mod0 = -1
            next_mod1 = -1
            # For each possible previous mod
            for d in d_list:
                # Previous mod0
                if current_mod0 != -1:
                    s = current_mod0 + d
                    mod = s % 2
                    if mod == 0:
                        if s > next_mod0:
                            next_mod0 = s
                    else:
                        if s > next_mod1:
                            next_mod1 = s
                # Previous mod1
                if current_mod1 != -1:
                    s = current_mod1 + d
                    mod = s % 2
                    if mod == 0:
                        if s > next_mod0:
                            next_mod0 = s
                    else:
                        if s > next_mod1:
                            next_mod1 = s
            # Update current_mod for next step
            current_mod0, current_mod1 = next_mod0, next_mod1
            # If no possible sums, break
            if current_mod0 == -1 and current_mod1 == -1:
                break
        # After k steps, check if possible
        if step != k:
            continue  # didn't complete all steps
        target_mod = D % 2
        max_s = -1
        if target_mod == 0:
            if current_mod0 != -1 and current_mod0 >= D:
                max_s = current_mod0
        else:
            if current_mod1 != -1 and current_mod1 >= D:
                max_s = current_mod1
        if max_s != -1 and (max_s - D) % 2 == 0:
            print(k)
            return
    print(-1)

solve()
0