結果
| 問題 |
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
}