Hướng dẫn giải của [200 đề thầy Đức] Bài 32: Tiêu diệt yêu tinh
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 a là số đòn của Bát Giới, b là số đòn của Sa Tăng. Yêu tinh bị tiêu diệt đúng khi tồn tại a, b không âm sao cho a·A + b·B = C. Nếu không tồn tại thì yêu tinh có sức mạnh âm và trốn thoát (in No).
Sub 1: Vét cạn hai biến — ~O(\frac{C}{A} \cdot \frac{C}{B})~
Thử mọi cặp (a, b) với a·A ≤ C và a·A + b·B ≤ C. Có cặp nào bằng đúng C thì in Yes. Đạt 134/134 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long A, B, C;
cin >> A >> B >> C;
bool ok = false;
// Vet can: thu moi cap so lan danh (a cua Bat Gioi, b cua Sa Tang)
for (long long a = 0; a * A <= C && !ok; a++)
for (long long b = 0; a * A + b * B <= C; b++)
if (a * A + b * B == C) {
ok = true;
break;
}
cout << (ok ? "Yes" : "No") << "\n";
return 0;
}
Sub 2: Chỉ thử số lần của Bát Giới — ~O(\frac{C}{A})~
Với mỗi a, phần còn lại C - a·A phải chia hết cho B. Chỉ cần kiểm tra điều này cho a từ 0 đến C/A, nên không cần duyệt b. Bẫy: C ≤ 10 000 nên không tràn số, nhưng cần dùng kiểu số nguyên 64 bit để chắc chắn. Đạt 134/134 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long A, B, C;
cin >> A >> B >> C;
bool ok = false;
// Voi moi so lan a cua Bat Gioi, phan con lai C - a*A phai chia het cho B
for (long long a = 0; a * A <= C; a++) {
if ((C - a * A) % B == 0) {
ok = true;
break;
}
}
cout << (ok ? "Yes" : "No") << "\n";
return 0;
}
Bình luận