#1083960 (C++17) No.968 引き算をして門松列（その３）

• 問題: No.968 引き算をして門松列（その３）
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:11:02
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 5,964 bytes
• コンパイル時間: 640 ms
• コンパイル使用メモリ: 83,544 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:13:00
• 合計ジャッジ時間: 1,287 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
sample	AC * 2
other	AC * 1 WA * 9

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <tuple> // Required for std::tuple

using namespace std;

// Define long long type for large integers to avoid overflow
typedef long long ll;

// Function to check if three positive integers A_prime, B_prime, C_prime form a Kadomatsu sequence.
// A sequence is Kadomatsu if all three numbers are distinct positive integers,
// and the middle element B_prime is NOT the median (second largest) value among the three.
// This function assumes A_prime, B_prime, C_prime > 0, which is checked before calling.
bool is_kadomatsu(ll A_prime, ll B_prime, ll C_prime) {
    // Check for distinctness: all three values must be different.
    if (A_prime == B_prime || B_prime == C_prime || A_prime == C_prime) {
        return false; // Not distinct, so not Kadomatsu.
    }
    
    // Check if B_prime is the median element.
    // B_prime is the median if it lies strictly between A_prime and C_prime.
    // There are two cases for this: A' < B' < C' or C' < B' < A'.
    bool B_is_median = (A_prime < B_prime && B_prime < C_prime) || (C_prime < B_prime && B_prime < A_prime);
    
    // A Kadomatsu sequence requires that B_prime is NOT the median.
    // Therefore, the function returns true if B_is_median is false, and false otherwise.
    return !B_is_median;
}

int main() {
    // Use faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T; // Number of test cases
    cin >> T; // Read the number of test cases
    while (T--) { // Loop through each test case
        ll A, B, C; // Initial positive integers
        ll X, Y, Z; // Costs for the three types of operations
        cin >> A >> B >> C >> X >> Y >> Z; // Read input for the current test case

        ll min_cost = -1; // Initialize minimum cost to -1, indicating "impossible" or "not yet found".

        // Define a list of patterns to check. Each pattern represents a potential target state
        // defined by the total decrease (dA, dB, dC) from the initial state (A, B, C).
        // The list includes the cost associated with achieving these decreases.
        // This list covers patterns corresponding to minimal necessary changes based on analysis.
        // Each element is a tuple: (dA, dB, dC, cost)
        vector<tuple<ll, ll, ll, ll>> patterns;
        
        // Add patterns to the list. The costs are derived from the k1, k2, k3 values corresponding to dA, dB, dC.
        // Example derivation: For dA=1, dB=1, dC=0:
        // k1 = (dA+dB-dC)/2 = (1+1-0)/2 = 1
        // k2 = (-dA+dB+dC)/2 = (-1+1+0)/2 = 0
        // k3 = (dA-dB+dC)/2 = (1-1+0)/2 = 0
        // Cost = k1*X + k2*Y + k3*Z = 1*X + 0*Y + 0*Z = X.
        
        // Base case: No operations needed. (dA, dB, dC) = (0, 0, 0). Cost = 0.
        patterns.emplace_back(0, 0, 0, 0LL); 

        // Patterns representing small numbers of operations (sum of decreases is small).
        // Sum dA+dB+dC = 2
        patterns.emplace_back(1, 1, 0, X); // Target state (A-1, B-1, C)
        patterns.emplace_back(0, 1, 1, Y); // Target state (A, B-1, C-1)
        patterns.emplace_back(1, 0, 1, Z); // Target state (A-1, B, C-1)
        
        // Sum dA+dB+dC = 4
        patterns.emplace_back(2, 2, 0, 2 * X); // Target state (A-2, B-2, C)
        patterns.emplace_back(0, 2, 2, 2 * Y); // Target state (A, B-2, C-2)
        patterns.emplace_back(2, 0, 2, 2 * Z); // Target state (A-2, B, C-2)
        patterns.emplace_back(1, 1, 2, Y + Z); // Target state (A-1, B-1, C-2)
        patterns.emplace_back(2, 1, 1, X + Z); // Target state (A-2, B-1, C-1) 
        patterns.emplace_back(1, 2, 1, X + Y); // Target state (A-1, B-2, C-1)

        // Sum dA+dB+dC = 6
        patterns.emplace_back(2, 2, 2, X + Y + Z); // Target state (A-2, B-2, C-2)

        // Additional patterns derived from analyzing the case A=B=C. 
        // These patterns correspond to dA, dB, dC being a permutation of {1, 2, 3}
        // such that dB is not the median (2). These also have sum dA+dB+dC = 6.
        patterns.emplace_back(1, 3, 2, X + 2 * Y); // Target state (A-1, B-3, C-2)
        patterns.emplace_back(2, 1, 3, Y + 2 * Z); // Target state (A-2, B-1, C-3)
        patterns.emplace_back(2, 3, 1, 2 * X + Y); // Target state (A-2, B-3, C-1)
        patterns.emplace_back(3, 1, 2, X + 2 * Z); // Target state (A-3, B-1, C-2)

        // Iterate through all the defined patterns.
        for (const auto& p : patterns) {
            ll dA, dB, dC, current_cost;
            tie(dA, dB, dC, current_cost) = p; // Unpack the tuple for the current pattern

            // Calculate the potential target state (A', B', C') based on the decreases.
            ll A_prime = A - dA;
            ll B_prime = B - dB;
            ll C_prime = C - dC;

            // Check if the calculated target state values (A', B', C') are all positive integers.
            // If any value is less than or equal to 0, this pattern is invalid for the current A, B, C.
            if (A_prime <= 0 || B_prime <= 0 || C_prime <= 0) {
                 continue; // Skip this pattern and move to the next one.
            }

            // Check if the target state (A', B', C') forms a Kadomatsu sequence.
            if (is_kadomatsu(A_prime, B_prime, C_prime)) {
                 // If it is a valid Kadomatsu sequence:
                 // Update min_cost if this is the first valid sequence found (min_cost == -1)
                 // or if the current pattern's cost is less than the currently known minimum cost.
                if (min_cost == -1 || current_cost < min_cost) {
                    min_cost = current_cost;
                }
            }
        }
        
        // After checking all patterns, output the minimum cost found.
        // If no pattern resulted in a valid Kadomatsu sequence, min_cost will remain -1.
        cout << min_cost << "\n";
    }
    return 0; // Indicate successful execution
}