結果

問題 No.281 門松と魔法(1)
ユーザー lam6er
提出日時 2025-03-31 17:59:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,296 bytes
コンパイル時間 393 ms
コンパイル使用メモリ 82,848 KB
実行使用メモリ 67,228 KB
最終ジャッジ日時 2025-03-31 18:00:57
合計ジャッジ時間 3,814 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 5 TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    d = int(sys.stdin.readline())
    H = [int(sys.stdin.readline()) for _ in range(3)]
    h1, h2, h3 = H

    def is_valid(a, b, c):
        if a == b or b == c or a == c:
            return False
        return (b > a and b > c) or (b < a and b < c)

    if is_valid(h1, h2, h3):
        print(0)
        return

    if d == 0:
        print(-1)
        return

    min_total = float('inf')

    def calculate_modeA():
        nonlocal min_total
        min_modeA = float('inf')
        for k2 in range(0, 200):
            current_h2 = h2 - k2 * d
            if current_h2 < 0:
                break
            k1_min = max(0, (h1 - (current_h2 - 1) + d - 1) // d)
            h1_candidate = h1 - k1_min * d
            if h1_candidate < 0:
                req_k1 = h1 // d
                if h1 - req_k1 * d > current_h2 - 1:
                    continue
                k1_min = req_k1
                h1_candidate = h1 - k1_min * d
                if h1_candidate < 0:
                    continue
            if h1_candidate >= current_h2:
                continue

            k3_min = max(0, (h3 - (current_h2 - 1) + d - 1) // d)
            h3_candidate = h3 - k3_min * d
            if h3_candidate < 0:
                req_k3 = h3 // d
                if h3 - req_k3 * d > current_h2 - 1:
                    continue
                k3_min = req_k3
                h3_candidate = h3 - k3_min * d
                if h3_candidate < 0:
                    continue
            if h3_candidate >= current_h2:
                continue

            total = k2 + k1_min + k3_min

            if h1_candidate != h3_candidate:
                if total < min_modeA:
                    min_modeA = total
            else:
                if h1_candidate == h3_candidate:
                    opt1 = (k1_min + 1, k3_min)
                    h1_opt = h1 - opt1[0] * d
                    if h1_opt >= 0 and h1_opt < current_h2:
                        total_opt1 = k2 + opt1[0] + opt1[1]
                        if total_opt1 < min_modeA:
                            min_modeA = total_opt1
                    opt2 = (k1_min, k3_min + 1)
                    h3_opt = h3 - opt2[1] * d
                    if h3_opt >= 0 and h3_opt < current_h2:
                        total_opt2 = k2 + opt2[0] + opt2[1]
                        if total_opt2 < min_modeA:
                            min_modeA = total_opt2
        return min_modeA

    def calculate_modeB():
        nonlocal min_total
        min_modeB = float('inf')
        for k2 in range(0, 200):
            current_h2 = h2 - k2 * d
            if current_h2 < 0:
                break
            rem = h1 - current_h2 - 1
            k1_min = 0
            if rem > 0:
                k1_min = 0
            else:
                needed = (-rem + d - 1) // d
                k1_min = needed

            h1_candidate = h1 - k1_min * d
            if h1_candidate <= current_h2 or h1_candidate < 0:
                k1_max = h1 // d
                possible = False
                for k1 in range(0, k1_max + 1):
                    temp_h1 = h1 - k1 * d
                    if temp_h1 > current_h2 and temp_h1 >= 0:
                        possible = True
                        k1_min = k1
                        h1_candidate = temp_h1
                        break
                if not possible:
                    continue

            rem3 = h3 - current_h2 - 1
            k3_min = 0
            if rem3 > 0:
                k3_min = 0
            else:
                needed = (-rem3 + d - 1) // d
                k3_min = needed

            h3_candidate = h3 - k3_min * d
            if h3_candidate <= current_h2 or h3_candidate < 0:
                k3_max = h3 // d
                possible = False
                for k3 in range(0, k3_max + 1):
                    temp_h3 = h3 - k3 * d
                    if temp_h3 > current_h2 and temp_h3 >= 0:
                        possible = True
                        k3_min = k3
                        h3_candidate = temp_h3
                        break
                if not possible:
                    continue

            total = k2 + k1_min + k3_min

            if h1_candidate != h3_candidate:
                if total < min_modeB:
                    min_modeB = total
            else:
                if h1_candidate == h3_candidate:
                    opt1 = (k1_min + 1, k3_min)
                    h1_opt = h1 - opt1[0] * d
                    if h1_opt > current_h2 and h1_opt >= 0:
                        total_opt1 = k2 + opt1[0] + opt1[1]
                        if total_opt1 < min_modeB:
                            min_modeB = total_opt1
                    opt2 = (k1_min, k3_min + 1)
                    h3_opt = h3 - opt2[1] * d
                    if h3_opt > current_h2 and h3_opt >= 0:
                        total_opt2 = k2 + opt2[0] + opt2[1]
                        if total_opt2 < min_modeB:
                            min_modeB = total_opt2
        return min_modeB

    modeA_min = calculate_modeA()
    modeB_min = calculate_modeB()

    min_total = min(modeA_min, modeB_min)

    if min_total != float('inf'):
        print(min_total)
    else:
        print(-1)

if __name__ == '__main__':
    main()
0