Hướng dẫn giải của [200 đề thầy Đức] Bài 89: Mua bưởi
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Gộp tiền lại thì số quả mua được tối đa là ⌊(x + y) / z⌋. Bài toán là tìm số tiền vay ít nhất để đạt được số quả đó.
Sub 1: Vét cạn số tiền chuyển — ~O(x + y)~
Thử lần lượt số tiền chuyển t = 0, ±1, ±2, ... (trong phạm vi không vay quá số tiền đang có), kiểm tra tổng số quả hai người mua được có bằng ⌊(x + y) / z⌋ không. Đạt 34/39 test, các test còn lại quá giờ.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long x, y, z;
cin >> x >> y >> z;
long long K = (x + y) / z; // số quả tối đa hai người có thể mua khi gộp tiền
// Vét cạn: t > 0 nghĩa là An cho Bình vay t; t < 0 nghĩa là Bình cho An vay -t.
// Thử lần lượt |t| = 0, 1, 2, ... (cả hai dấu), lấy |t| nhỏ nhất đạt K quả
for (long long d = 0; d <= x + y; d++) {
for (int sign = 0; sign < 2; sign++) {
long long t = (sign == 0) ? d : -d;
if (t > x || t < -y) continue; // không vay quá số tiền đang có
long long qa = (x - t) / z; // An mua được bao nhiêu
long long qb = (y + t) / z; // Bình mua được bao nhiêu
if (qa + qb == K) {
cout << K << " " << d << "\n";
return 0;
}
}
}
return 0;
}
Sub 2: Công thức theo số dư — ~O(1)~
Gọi rx = x mod z, R = (x + y) mod z. Nếu rx ≤ R thì không cần vay. Nếu không, có hai cách vay: rx - R, hoặc z - rx (nếu y đủ tiền). Lấy giá trị nhỏ hơn. Đạt 39/39 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long x, y, z;
cin >> x >> y >> z;
// Số quả tối đa hai người mua được khi gộp tiền
long long K = (x + y) / z;
long long R = (x + y) % z; // số dư của tổng
long long rx = x % z; // số dư của tiền An
// Nếu An không vay gì mà vẫn đạt K thì không cần vay
// Điều kiện: chỉ cần (x - t) mod z <= R, với t là số tiền chuyển
long long vay;
if (rx <= R) {
vay = 0;
} else {
vay = rx - R; // An cho Bình vay rx - R (bên trái)
if (z - rx <= y) // Bình cho An vay z - rx (bên phải)
vay = min(vay, z - rx);
}
cout << K << " " << vay << "\n";
return 0;
}
Bình luận