Hướng dẫn giải của Mức Góp Để Đạt Mục Tiêu
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Nguyễn Hiếu
Phân tích
Ta cần tìm giá trị nhỏ nhất của ~C~ sao cho sau ~n~ tháng số dư đạt ít nhất ~X~.
Nhận xét quan trọng:
- Nếu tăng ~C~, số dư cuối cùng không giảm.
- Nghĩa là tính chất "đạt mục tiêu" theo ~C~ là đơn điệu.
Vì vậy ta có thể dùng binary search trên đáp án.
Kiểm tra một giá trị ~C~
Mô phỏng ~n~ tháng:
~A = \left\lfloor A \times \frac{10000 + r}{10000} \right\rfloor + C~
Nếu ở bất kỳ thời điểm nào ~A \ge X~, ta có thể dừng sớm và kết luận ~C~ là đủ.
Cận tìm kiếm
- Trái: ~0~
- Phải: ~X~
Với ~C = X~, chỉ cần nộp rất nhiều mỗi tháng nên chắc chắn đủ nếu ~n > 0~.
Độ phức tạp
Mỗi lần kiểm tra tốn ~O(n)~, binary search tốn ~O(\log X)~.
Tổng cộng: ~O(n \log X)~ mỗi test.
Code mẫu
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
bool canReach(int64 P, long long X, int64 r, int64 n, long long C) {
long long A = P;
if (A >= X) return true;
for (int64 i = 0; i < n; ++i) {
i128 grown = (i128)A * (10000 + r) / 10000;
A = (long long)grown + C;
if (A >= X) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long P, X, r, n;
cin >> P >> X >> r >> n;
if (P >= X) {
cout << 0 << '\n';
continue;
}
if (n == 0) {
cout << -1 << '\n';
continue;
}
long long lo = 0, hi = X;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (canReach(P, X, r, n, mid)) hi = mid;
else lo = mid + 1;
}
cout << lo << '\n';
}
return 0;
}
Bình luận