Hướng dẫn giải của [200 đề thầy Đức] Bài 14: Trò chơi với các con số
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
Hai người lần lượt nhân đôi số của mình, người có X đi trước, tổng cộng N lượt. Người X đi các lượt lẻ nên nhân đôi ~\lceil N/2 \rceil~ lần, người Y nhân đôi ~\lfloor N/2 \rfloor~ lần. Cần thương của max(W, Z) chia min(W, Z).
Sub 1: Mô phỏng từng lượt — ~O(N)~
W và Z quá lớn (N có thể đến 10^9) nên chỉ theo dõi tỉ số r = W/Z dạng số thực: lượt của X thì r nhân 2, lượt của Y thì r chia 2. Cuối cùng lấy phần nguyên của \max(r, 1/r). Đúng nhưng chậm, đạt 13/21 test (phần còn lại TLE).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long X, Y, N;
cin >> X >> Y >> N;
// Vét cạn: mô phỏng từng lượt. Chỉ cần tỉ số W/Z nên giữ r = W/Z (dạng số thực).
// Lượt chẵn (bắt đầu từ 0) là người có X nhân đôi: r *= 2; lượt lẻ là người có Y: r /= 2.
long double r = (long double)X / Y;
for (long long i = 0; i < N; i++) {
if (i % 2 == 0) r *= 2;
else r /= 2;
}
long long ans = (r >= 1) ? (long long)floorl(r) : (long long)floorl(1 / r);
cout << ans << "\n";
}
return 0;
}
Sub 2: Công thức — ~O(1)~
Nhân cả W và Z với cùng lũy thừa của 2 không đổi thương. Do đó W/Z tương đương X \cdot 2^d / Y với d = 1 nếu N lẻ, d = 0 nếu N chẵn. Đáp án là \max(r1, r2) / \min(r1, r2) với r1 = X \cdot 2^d và r2 = 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--) {
long long X, Y, N;
cin >> X >> Y >> N;
// Người X đi lượt 1, 3, 5, ... nên nhân đôi ceil(N/2) lần; người Y nhân đôi floor(N/2) lần.
// Tỉ số W/Z = X * 2^(ceil - floor) / Y, và thương cần tìm không đổi khi nhân cả hai với 2^floor.
long long r1 = X, r2 = Y;
if (N % 2 == 1) r1 *= 2; // N lẻ: người X nhân đôi thêm 1 lần
cout << max(r1, r2) / min(r1, r2) << "\n";
}
return 0;
}
Bình luận