Hướng dẫn giải của [200 đề thầy Đức] Bài 23: Thạch Sanh đánh 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
Thạch Sanh mua thêm sức khỏe, tấn công và phòng thủ. Nếu tấn công của Thạch Sanh là A thì mỗi giây yêu tinh mất max(0, A - Dy) sức khỏe. Mỗi giây Thạch Sanh mất max(0, Ay - D). Ta chọn số điểm mua thêm y (tấn công), z (phòng thủ) và hp (sức khỏe) với chi phí nhỏ nhất để thắng.
Sub 1: Vét cạn ba tham số, mô phỏng từng giây — ~O(200 \cdot 100 \cdot 10^4 \cdot 100)~
Thử mọi y \in [0, 200], z \in [0, 100], và với mỗi cặp thử hp tăng dần từ 0 đến 10001 cho đến khi mô phỏng từng giây cho thấy thắng. Đúng nhưng chậm, đạt 46/46 test.
#include <bits/stdc++.h>
using namespace std;
// Mô phỏng từng giây: trả về true nếu Thạch Sanh thắng với các chỉ số cho trước
bool thang(long long H, long long A, long long D, long long Hy, long long Ay, long long Dy) {
long long dO = max(0LL, A - Dy); // sát thương Thạch Sanh gây ra mỗi giây
long long dT = max(0LL, Ay - D); // sát thương yêu tinh gây ra mỗi giây
if (dO <= 0) return false; // không bao giờ hạ được yêu tinh
while (true) {
Hy -= dO;
H -= dT;
if (H <= 0) return false; // Thạch Sanh chết trước hoặc cùng lúc
if (Hy <= 0) return true; // yêu tinh chết, Thạch Sanh còn sống
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long Ht, At, Dt, Hy, Ay, Dy, h, a, d;
cin >> Ht >> At >> Dt;
cin >> Hy >> Ay >> Dy;
cin >> h >> a >> d;
long long best = LLONG_MAX;
// Vét cạn: thử mọi số điểm mua thêm y (sức tấn công), z (phòng thủ), hp (sức khỏe)
// Cần y <= 200 và z <= 100 là đủ; hp <= 10001
for (long long y = 0; y <= 200; y++)
for (long long z = 0; z <= 100; z++)
for (long long hp = 0; hp <= 10001; hp++) {
long long cost = h * hp + a * y + d * z;
if (cost >= best) break;
if (thang(Ht + hp, At + y, Dt + z, Hy, Ay, Dy)) {
best = cost;
break; // hp tăng thì chi phí tăng, nên dừng ở hp nhỏ nhất thắng
}
}
cout << best << "\n";
return 0;
}
Sub 2: Công thức theo số giây — ~O(200 \cdot 100)~
Với (y, z) cố định, số giây để hạ yêu tinh là t = ~\lceil H_y / (A - D_y) \rceil~ (bỏ qua nếu A \le Dy). Thạch Sanh phải còn sống sau t giây nên Ht' \ge t \cdot \max(0, Ay - Dt') + 1. Chi phí sức khỏe mua thêm là phần thiếu so với H_t. Lấy min chi phí trên mọi (y, z). Đạt 46/46 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long Ht, At, Dt, Hy, Ay, Dy, h, a, d;
cin >> Ht >> At >> Dt;
cin >> Hy >> Ay >> Dy;
cin >> h >> a >> d;
long long best = LLONG_MAX;
// Chỉ cần thử y (tấn công mua thêm) trong [0, 200] và z (phòng thủ mua thêm) trong [0, 100]
for (long long y = 0; y <= 200; y++)
for (long long z = 0; z <= 100; z++) {
long long A = At + y, D = Dt + z;
long long dO = A - Dy; // sát thương mỗi giây lên yêu tinh
if (dO <= 0) continue; // không hạ được yêu tinh
long long t = (Hy + dO - 1) / dO; // số giây để hạ yêu tinh (làm tròn lên)
long long dT = max(0LL, Ay - D); // sát thương yêu tinh gây ra mỗi giây
// Thạch Sanh phải còn sống sau t giây: Ht' - t * dT >= 1
long long need = t * dT + 1;
long long hp = max(0LL, need - Ht); // số sức khỏe cần mua thêm
best = min(best, h * hp + a * y + d * z);
}
cout << best << "\n";
return 0;
}
Bình luận