結果

問題 No.1935 Water Simulation
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-02-25 00:24:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 238 ms / 2,000 ms
コード長 2,460 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 167,148 KB
最終ジャッジ日時 2024-09-29 10:28:15
合計ジャッジ時間 3,982 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
62,976 KB
testcase_01 AC 49 ms
63,744 KB
testcase_02 AC 40 ms
57,600 KB
testcase_03 AC 141 ms
114,388 KB
testcase_04 AC 81 ms
81,280 KB
testcase_05 AC 186 ms
142,348 KB
testcase_06 AC 56 ms
71,808 KB
testcase_07 AC 54 ms
71,808 KB
testcase_08 AC 113 ms
108,992 KB
testcase_09 AC 192 ms
148,244 KB
testcase_10 AC 185 ms
137,584 KB
testcase_11 AC 85 ms
78,976 KB
testcase_12 AC 41 ms
58,624 KB
testcase_13 AC 40 ms
58,240 KB
testcase_14 AC 71 ms
78,208 KB
testcase_15 AC 107 ms
102,320 KB
testcase_16 AC 127 ms
109,192 KB
testcase_17 AC 95 ms
90,556 KB
testcase_18 AC 40 ms
57,600 KB
testcase_19 AC 172 ms
120,964 KB
testcase_20 AC 56 ms
65,408 KB
testcase_21 AC 136 ms
113,792 KB
testcase_22 AC 112 ms
94,348 KB
testcase_23 AC 72 ms
78,336 KB
testcase_24 AC 238 ms
167,148 KB
testcase_25 AC 67 ms
72,064 KB
testcase_26 AC 45 ms
60,800 KB
testcase_27 AC 93 ms
90,028 KB
testcase_28 AC 75 ms
79,360 KB
testcase_29 AC 37 ms
52,224 KB
testcase_30 AC 40 ms
57,728 KB
testcase_31 AC 63 ms
71,424 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1935


def main():
    V1, V2, V3, V4, N = map(int, input().split())

    state_array = []
    for v1 in range(V1 + 1):
        for v2 in range(V2 + 1):
            for v3 in range(V3 + 1):
                if V1 < v1 + v2 + v3:
                    break

                v4 = V1 - v1 - v2 - v3
                if v4 > V4:
                    continue

                state_array.append((v1, v2, v3, v4))
    state_map = {}
    state_max = len(state_array)
    for i, state in enumerate(state_array):
        state_map[state] = i

    func_map = [-1] * state_max
    for i, state in enumerate(state_array):
        v1, v2, v3, v4 = state

        # 操作1を実施
        new_v1 = v1 - min(v1, V2 - v2)
        new_v2 = v2 + min(v1, V2 - v2)
        v1 = new_v1
        v2 = new_v2

        # 操作2を実施
        new_v2 = v2 - min(v2, V3 - v3)
        new_v3 = v3 + min(v2, V3 - v3)
        v2 = new_v2
        v3 = new_v3

        # 操作3を実施
        new_v3 = v3 - min(v3, V4 - v4)
        new_v4 = v4 + min(v3, V4 - v4)
        v3 = new_v3
        v4 = new_v4

        # 操作4を実施
        new_v4 = v4 - min(v4, V1 - v1)
        new_v1 = v1 + min(v4, V1 - v1)
        v4 = new_v4
        v1 = new_v1

        func_map[i] = state_map[(v1, v2, v3, v4)]

    n0 = N // 4
    # ダブリングを実施
    state = state_map[(V1, 0, 0, 0)]
    while n0 > 0:
        if n0 % 2 == 1:
            state = func_map[state]
        
        func_map = [func_map[func_map[s]] for s in range(state_max)]
        n0 //= 2

    n1 = N - (N // 4) * 4
    if n1 > 0:
        v1, v2, v3, v4 = state_array[state]
    
        # 操作1を実施
        new_v1 = v1 - min(v1, V2 - v2)
        new_v2 = v2 + min(v1, V2 - v2)
        v1 = new_v1
        v2 = new_v2
        if n1 == 1:
            print(v1, v2, v3, v4)
            return

        # 操作2を実施
        new_v2 = v2 - min(v2, V3 - v3)
        new_v3 = v3 + min(v2, V3 - v3)
        v2 = new_v2
        v3 = new_v3
        if n1 == 2:
            print(v1, v2, v3, v4)
            return

        # 操作3を実施
        new_v3 = v3 - min(v3, V4 - v4)
        new_v4 = v4 + min(v3, V4 - v4)
        v3 = new_v3
        v4 = new_v4
        if n1 == 3:
            print(v1, v2, v3, v4)
            return
    else:
        v1, v2, v3, v4 = state_array[state]
        print(v1, v2, v3, v4)
        return










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