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