結果

問題 No.968 引き算をして門松列（その３）
ユーザー qwewe
提出日時 2025-05-14 13:19:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,530 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 78,360 KB
最終ジャッジ日時 2025-05-14 13:20:09
合計ジャッジ時間 2,769 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to check if a state (A, B, C) is a Kadomatsu sequence
def is_kadomatsu(A, B, C):
    """
    Checks if the triplet (A, B, C) forms a Kadomatsu sequence.
    A triplet (A, B, C) is a Kadomatsu sequence if:
    1. A, B, C are positive integers.
    2. All values A, B, C are distinct.
    3. The middle element B is not the median element. This means B must be 
       either strictly the smallest or strictly the largest of the three.
    """
    # Condition 1: Check if A, B, C are positive integers.
    # The operations guarantee that A', B', C' remain integers if started with integers.
    # We only need to check if they are >= 1.
    if A <= 0 or B <= 0 or C <= 0:
        return False
    
    # Condition 2: Check if all values are distinct.
    if A == B or B == C or A == C:
        return False
        
    # Condition 3: Check if B is the minimum or the maximum element.
    # Check if B is strictly smaller than both A and C.
    is_min = (B < A and B < C)
    # Check if B is strictly greater than both A and C.
    is_max = (B > A and B > C)
    
    # If B is either the minimum or the maximum, it satisfies the condition.
    if is_min or is_max:
        return True
        
    # If B is the median (neither min nor max), it's not a Kadomatsu sequence.
    return False

def solve():
    """
    Solves a single test case of the problem.
    Reads input A, B, C, X, Y, Z. Finds the minimum cost to transform (A, B, C)
    into a Kadomatsu sequence using the given operations.
    """
    # Read input values for a single test case using sys.stdin.readline for efficiency.
    line = sys.stdin.readline().split()
    A = int(line[0])
    B = int(line[1])
    C = int(line[2])
    X = int(line[3]) # Cost to decrease A and B by 1
    Y = int(line[4]) # Cost to decrease B and C by 1
    Z = int(line[5]) # Cost to decrease A and C by 1

    # First, check if the initial state (A, B, C) is already a Kadomatsu sequence.
    # If yes, the minimum cost is 0.
    if is_kadomatsu(A, B, C):
        print(0)
        return

    # Initialize the minimum cost found so far to a very large value.
    # The maximum possible cost could be large (e.g., if x,y,z=2 and costs are 10^9),
    # so use a sufficiently large number. 10^19 is safe.
    current_min_cost = 10**19 
    
    # Flag to track if we have found any reachable Kadomatsu state.
    found_kadomatsu = False 

    # The core strategy is to check states reachable by applying a small number of operations.
    # We iterate through combinations of operations (x, y, z) where x, y, z are counts
    # for each operation type. We limit counts up to 2 based on analysis:
    # For cases like A=B=C, we need distinct operation counts to break symmetry.
    # The minimal distinct non-negative integers are {0, 1, 2}, suggesting max count 2 might be sufficient.
    # This covers 3*3*3 = 27 combinations of operations beyond the initial state.
    for x in range(3): # Number of times operation 1 (decrease A, B) is applied: 0, 1, or 2
        for y in range(3): # Number of times operation 2 (decrease B, C) is applied: 0, 1, or 2
            for z in range(3): # Number of times operation 3 (decrease A, C) is applied: 0, 1, or 2
                
                # The case (x, y, z) = (0, 0, 0) corresponds to the initial state.
                # We already checked it and know it's not Kadomatsu, so skip.
                if x == 0 and y == 0 and z == 0: 
                    continue

                # Calculate the resulting state (A', B', C') after applying operations.
                # The total decrease in A is x + z.
                # The total decrease in B is x + y.
                # The total decrease in C is y + z.
                A_prime = A - x - z
                B_prime = B - x - y
                C_prime = C - y - z

                # Check if the resulting state is valid: all components must be positive integers (>= 1).
                if A_prime >= 1 and B_prime >= 1 and C_prime >= 1:
                    
                    # Check if the resulting state (A', B', C') is a Kadomatsu sequence.
                    if is_kadomatsu(A_prime, B_prime, C_prime):
                         # If it is a valid Kadomatsu sequence, calculate the total cost.
                         # Use integer arithmetic. Python handles large integers automatically.
                         cost = x * X + y * Y + z * Z
                         
                         # Update the minimum cost found so far if this path is cheaper.
                         if cost < current_min_cost:
                             current_min_cost = cost
                         
                         # Set flag indicating that at least one reachable Kadomatsu state has been found.
                         found_kadomatsu = True 


    # After checking all considered combinations of operations (up to x,y,z=2):
    if found_kadomatsu:
         # If we found at least one Kadomatsu state, print the minimum cost discovered.
         print(current_min_cost)
    else:
         # If no Kadomatsu state was found within the limited search range,
         # it implies either it's impossible or requires more operations than checked.
         # Based on the problem structure and analysis, this usually indicates impossibility. Output -1.
         print("-1")


# Read the number of test cases from the first line of input.
T = int(sys.stdin.readline())
# Process each test case by calling the solve function.
for _ in range(T):
    solve()
0