#1083784 (C++17) No.1015 おつりは要らないです

• 問題: No.1015 おつりは要らないです
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:01:13
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 6,907 bytes
• コンパイル時間: 715 ms
• コンパイル使用メモリ: 95,304 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:02:52
• 合計ジャッジ時間: 2,438 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

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

ソースコード

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

// Function to check if k thousand yen can be paid with current available bills.
// It attempts to find a valid combination of bills (pay_x, pay_y, pay_z) such that 
// pay_x * 1 + pay_y * 5 + pay_z * 10 = k thousand yen,
// and pay_x <= current_x, pay_y <= current_y, pay_z <= current_z.
// The function uses a primary greedy strategy (largest denominations first).
// If the primary strategy fails due to insufficient 1000 yen bills, it attempts
// an alternative strategy: using one fewer 10000 yen bill (if possible) and
// compensating with 5000 and 1000 yen bills.
// If a valid combination is found, it returns true and outputs the combination via reference parameters.
// Otherwise, it returns false.
bool can_pay(long long k, long long current_x, long long current_y, long long current_z, 
             long long& used_x, long long& used_y, long long& used_z) {

    // Basic check: cannot pay non-positive amounts.
    if (k <= 0) return false;

    // Try standard greedy approach (largest denominations first)
    long long k_rem = k; // k is the target amount in thousands of yen
    
    // Calculate the number of 10000 yen bills to use greedily
    // Use at most current_z bills, and at most floor(k_rem / 10) bills.
    long long greedy_z = std::min(current_z, k_rem / 10);
    k_rem -= greedy_z * 10; // Subtract the value covered by 10k bills
    
    // Calculate the number of 5000 yen bills to use greedily
    // Use at most current_y bills, and at most floor(k_rem / 5) bills.
    long long greedy_y = std::min(current_y, k_rem / 5);
    k_rem -= greedy_y * 5; // Subtract the value covered by 5k bills
    
    // The remaining amount must be covered by 1000 yen bills
    long long greedy_x = k_rem;

    // Check if the greedy combination is possible (i.e., have enough 1000 yen bills)
    if (greedy_x <= current_x) {
        // Greedy combination works. Set the output parameters and return true.
        used_x = greedy_x;
        used_y = greedy_y;
        used_z = greedy_z;
        return true;
    }

    // If the greedy approach failed because we needed too many 1000 yen bills (greedy_x > current_x)
    // Check an alternative strategy: using one fewer 10000 yen bill.
    // This is only possible if the greedy approach attempted to use at least one 10000 yen bill (greedy_z >= 1).
    if (greedy_z >= 1) {
        
        // Try using one fewer 10k bill
        long long alt_z = greedy_z - 1; 
        
        // Recalculate the remaining amount to cover with 5k and 1k bills.
        // The new remaining amount is k - alt_z * 10 = k - (greedy_z - 1) * 10 = (k - greedy_z * 10) + 10
        // This is the remainder from the first step of greedy + 10.
        long long k_rem_alt = k - alt_z * 10; 

        // Cover k_rem_alt using 5k and 1k bills, again greedily
        long long alt_y = std::min(current_y, k_rem_alt / 5);
        k_rem_alt -= alt_y * 5;
        long long alt_x = k_rem_alt; // Remainder must be covered by 1k bills

        // Check if this alternative combination is valid: requires enough 1k and 5k bills.
        // We already know alt_z is valid because alt_z < greedy_z <= current_z.
        if (alt_x <= current_x && alt_y <= current_y) { 
             // Alternative combination works. Set output parameters and return true.
             used_x = alt_x;
             used_y = alt_y;
             used_z = alt_z;
             return true;
        }
    }
    
    // If both the standard greedy strategy and the alternative strategy (if applicable) failed
    return false;
}


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

    int N; // Number of shops
    long long X, Y, Z; // Initial counts of 1000, 5000, 10000 yen bills
    std::cin >> N >> X >> Y >> Z;

    std::vector<long long> A(N); // Costs at each shop
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    // Current available bills
    long long current_x = X;
    long long current_y = Y;
    long long current_z = Z;

    // Process purchases for each shop sequentially
    for (int i = 0; i < N; ++i) {
        long long k_min; // Minimum required payment amount in thousands of yen
        
        // Calculate k_min based on the cost A[i]
        if (A[i] % 1000 == 0) {
             // If A[i] is exactly a multiple of 1000, Yuki must pay strictly more.
             // The minimum payment is A[i] + 1000 yen.
            k_min = A[i] / 1000 + 1;
        } else {
            // If A[i] is not a multiple of 1000, Yuki must pay at least the next multiple of 1000.
            // This is ceil(A[i] / 1000.0) thousands of yen.
            // Using integer division: (A[i] + 999) / 1000
            k_min = (A[i] + 999) / 1000; 
        }

        bool paid = false; // Flag to track if payment was successful for the current shop
        long long k_to_pay = -1; // The actual amount paid (in thousands)
        long long pay_x = 0, pay_y = 0, pay_z = 0; // Bills used for the payment

        // Try to find the smallest payable amount k >= k_min.
        // We check a small range starting from k_min. Based on analysis, checking up to
        // k_min + 9 seems sufficient to cover cases where paying slightly more than
        // the minimum required amount becomes possible due to bill combinations.
        for (long long k = k_min; k <= k_min + 9; ++k) {
             // Check if 'k' thousand yen can be paid using current bills.
             // Pass temporary variables to receive the used bill counts if payment is possible.
             long long temp_used_x, temp_used_y, temp_used_z;
            if (can_pay(k, current_x, current_y, current_z, temp_used_x, temp_used_y, temp_used_z)) {
                // Found the smallest k >= k_min that is payable.
                k_to_pay = k; 
                // Store the bill combination used for this payment.
                pay_x = temp_used_x; 
                pay_y = temp_used_y;
                pay_z = temp_used_z;
                paid = true; // Mark payment as successful
                break; // Stop searching, as we want the minimum possible payment
            }
        }

        if (paid) {
            // Payment was successful for shop i. Update the available bill counts.
            current_x -= pay_x;
            current_y -= pay_y;
            current_z -= pay_z;
        } else {
            // If no payable amount k was found in the checked range [k_min, k_min + 9]
            // Yuki cannot make this purchase according to the rules.
            std::cout << "No" << std::endl;
            return 0; // Exit program indicating failure
        }
    }

    // If the loop completes, all N purchases were successfully made.
    std::cout << "Yes" << std::endl;

    return 0;
}