Hướng dẫn giải của Ốc sên (đề HSG 12 Phú Thọ 2017-2018)
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
Ốc sên bò lên ngọn cây cao v mét, mỗi lần bò được a mét rồi tụt b mét khi nghỉ. Tìm số lần bò ít nhất để lên được ngọn. Đọc từ CAU1.INP, ghi ra CAU1.OUT.
Sub 1: Mô phỏng từng lần bò — ~O(v/(a-b))~
Lặp: tăng số lần bò, cộng a vào vị trí; nếu vị trí đã đạt v thì dừng, ngược lại trừ b. Cách này đúng nhưng với v lên tới 10^18 thì số vòng lặp quá lớn.
Kết quả chấm: đạt 24/32 test (SUB ok 24/32, TLE 8, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
}
long long v, a, b;
cin >> v >> a >> b;
// Mô phỏng từng lần bò
long long vitri = 0, solan = 0;
while (true) {
solan++;
vitri += a; // bò lên a mét
if (vitri >= v) break; // tới ngọn
vitri -= b; // nghỉ rồi tụt b mét
}
cout << solan << "\n";
return 0;
}
Sub 2: Công thức — ~O(1)~
Nếu v ≤ a thì chỉ cần 1 lần. Ngược lại, mỗi lần bò (trừ lần cuối) đi thêm được d = a - b mét. Sau k-1 lần đầu đạt (k-1)·d, lần thứ k leo thêm a, nên cần (k-1)·d + a ≥ v, suy ra k = ⌈(v-a)/d⌉ + 1. Tính số làm tròn lên bằng (v-a+d-1)/d. Lưu ý: v đến 10^18 nên dùng long long.
Kết quả chấm: đạt 32/32 test
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
}
long long v, a, b;
cin >> v >> a >> b;
if (v <= a) {
// Chỉ cần một lần bò là tới ngọn
cout << 1 << "\n";
return 0;
}
// Mỗi lần bò (trừ lần cuối) đi thêm được d = a - b mét thực sự.
// Sau k-1 lần đầu đạt (k-1)*d, lần thứ k leo thêm a: cần (k-1)*d + a >= v
// => k - 1 >= ceil((v - a) / d)
long long d = a - b;
long long k = (v - a + d - 1) / d + 1;
cout << k << "\n";
return 0;
}
Bình luận