Hướng dẫn giải của [200 đề thầy Đức] Bài 11: Ai sút phạt tốt hơn
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
Ta mô phỏng từng lượt. Mỗi lượt chỉ có một cú sút: nếu năng lượng thủ môn L là ước của năng lượng T của Văn Toàn thì Văn Toàn ghi bàn (T giảm 1); nếu không thì xét Văn Quyết với Q; nếu cả hai đều không ghi được thì thủ môn bắt bóng và L giảm 1. Dừng khi L = 1.
Sub 1: Mô phỏng, kiểm tra ước bằng vòng lặp — ~O((T+Q+L) \times L)~
Mô phỏng đúng như trên, nhưng kiểm tra "d là ước của n" bằng cách duyệt mọi số từ 1 đến d. Đúng nhưng chậm, đạt 1/21 test.
#include <bits/stdc++.h>
using namespace std;
// Vét cạn: kiểm tra d có là ước của n bằng cách duyệt từng số i từ 1 đến d
bool laUoc(long long d, long long n) {
bool ok = false;
for (long long i = 1; i <= d; i++)
if (i == d && n % i == 0) ok = true;
return ok;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int TC;
cin >> TC;
while (TC--) {
long long T, Q, L;
cin >> T >> Q >> L;
long long goalT = 0, goalQ = 0;
// Mỗi lượt: Văn Toàn thử trước, nếu không ghi được thì Văn Quyết thử, nếu cả hai đều không thì thủ môn giảm 1
while (L > 1) {
if (laUoc(L, T)) {
T--;
goalT++;
} else if (laUoc(L, Q)) {
Q--;
goalQ++;
} else {
L--;
}
}
cout << goalT << " " << goalQ << "\n";
}
return 0;
}
Sub 2: Mô phỏng với phép chia lấy dư — ~O(T+Q+L)~
Kiểm tra ước bằng phép T % L == 0. Số lượt tối đa là O(T+Q+L) nên đủ nhanh. Ghi bàn chỉ xảy ra khi T \ge L \ge 2 nên T, Q không bao giờ về 0. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int TC;
cin >> TC;
while (TC--) {
long long T, Q, L;
cin >> T >> Q >> L;
long long goalT = 0, goalQ = 0;
// Mô phỏng từng lượt, mỗi lượt chỉ có một cú sút (Văn Toàn được ưu tiên)
// Số lượt tối đa là O(T + Q + L) nên đủ nhanh
while (L > 1) {
if (T % L == 0) { // L là ước năng lượng của Văn Toàn -> ghi bàn
T--;
goalT++;
} else if (Q % L == 0) { // Văn Quyết ghi bàn
Q--;
goalQ++;
} else { // thủ môn bắt được bóng -> năng lượng giảm 1
L--;
}
}
cout << goalT << " " << goalQ << "\n";
}
return 0;
}
Bình luận