Hướng dẫn giải của [200 đề thầy Đức] Bài 109: Trâu và cỏ
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ọi d, b, c lần lượt là số trâu đứng, trâu nằm, trâu già; d + b + c = x. Trâu già ăn theo nhóm 3 con một bó nên c phải chia hết cho 3. Tổng cỏ là 5d + 3b + c/3 = y.
Sub 1: Vét cạn hai biến — ~O(X^2)~
Thử mọi d và b, suy ra c = x - d - b, kiểm tra c chia hết cho 3 và số cỏ đúng y. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int x, y;
cin >> x >> y;
vector<array<int, 3>> res;
// Vet can: thu moi so trau dung d va trau nam b, suy ra trau gia c = x - d - b
for (int d = 0; d <= x; d++)
for (int b = 0; b <= x - d; b++) {
int c = x - d - b;
if (c % 3 != 0) continue; // trau gia an theo nhom 3 con
if (5 * d + 3 * b + c / 3 == y) // tong bo co an dung y
res.push_back({d, b, c});
}
cout << res.size() << "\n";
for (auto &r : res) cout << r[0] << ' ' << r[1] << ' ' << r[2] << "\n";
}
return 0;
}
Sub 2: Giải công thức theo d — ~O(X)~
Đặt c = 3g. Từ hai phương trình, khử b ta có 8g = 3x + 2d - y. Với mỗi d chỉ cần kiểm tra g nguyên và không âm, rồi tính b = x - d - 3g, cần b ≥ 0. Mỗi d cho đúng một đáp án nên đã in theo thứ tự số trâu đứng tăng dần. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int x, y;
cin >> x >> y;
vector<array<int, 3>> res;
// Goi g = so nhom 3 trau gia (c = 3g). Ta co:
// d + b + 3g = x va 5d + 3b + g = y
// Khu b: 8g = 3x + 2d - y, nen voi moi d chi can kiem tra g nguyen, >= 0
for (int d = 0; d <= x; d++) {
int num = 3 * x + 2 * d - y;
if (num < 0 || num % 8 != 0) continue;
int g = num / 8;
int b = x - d - 3 * g;
if (b < 0) continue;
res.push_back({d, b, 3 * g});
}
cout << res.size() << "\n";
for (auto &r : res) cout << r[0] << ' ' << r[1] << ' ' << r[2] << "\n";
}
return 0;
}
Bình luận