GOPMUCTIEU - Mức Góp Để Đạt Mục Tiêu
Xem dạng PDFMức Góp Để Đạt Mục Tiêu
Minh muốn lập một kế hoạch đầu tư có kỷ luật để sau ~n~ tháng đạt được một mục tiêu tài chính cụ thể, chẳng hạn như quỹ học tập, tiền mua xe hoặc khoản dự phòng dài hạn.
Minh đã có sẵn ~P~ đồng. Mỗi tháng, khoản tiền hiện có sẽ tăng trưởng với lãi suất ~r~ basis points, sau đó Minh nộp thêm một khoản cố định ~C~ đồng vào cuối tháng.
Để thử xem với từng mục tiêu thì mình cần góp bao nhiêu mỗi tháng, Minh thường dùng công cụ Behivest Tools - Goal Based Contribution. Trong bài này, bạn cần tự tính ra đáp án.
Cho ~P, X, r, n~, hãy tìm giá trị nguyên nhỏ nhất của ~C~ sao cho sau đúng ~n~ tháng, số dư đạt ít nhất ~X~ đồng.
Quy tắc cập nhật mỗi tháng:
~A = \left\lfloor A \times \frac{10000 + r}{10000} \right\rfloor + C~
Nếu ngay từ đầu ~P \ge X~, đáp án là ~0~. Nếu ~n = 0~ mà ~P < X~, in ra -1.
Input
Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 2000)~.
Mỗi test gồm 4 số nguyên ~P, X, r, n~:
- ~0 \le P \le 10^{12}~
- ~1 \le X \le 10^{18}~
- ~0 \le r \le 2000~
- ~0 \le n \le 2 \cdot 10^5~
Giới hạn thêm: tổng ~n~ của mọi test không vượt quá ~2 \cdot 10^5~.
Dữ liệu đảm bảo đáp án luôn nằm trong kiểu số nguyên 64-bit có dấu.
Output
Với mỗi test, in ra giá trị nhỏ nhất của ~C~, hoặc -1 nếu không thể.
Ví dụ
Input
4
1000000 5000000 50 12
5000000 5000000 123 24
500000 1000000 0 5
0 1 0 0
Output
319267
0
100000
-1
Bình luận
include <iostream>
using namespace std; bool check(long long P, long long X, long long r, long long n, long long C) { long long A = P; for (int i = 0; i < n; ++i) { int128t nextA = (int128t)A * (10000 + r) / 10000 + C; if (nextA >= X) return true; A = (long long)nextA; } return A >= X; } void solve() { long long P, X, r, n; if (!(cin >> P >> X >> r >> n)) return; if (P >= X) { cout << 0 << "\n"; return; } if (n == 0) { cout << -1 << "\n"; return; } long long low = 0, high = X; long long ans = high; while (low <= high) { long long mid = low + (high - low) / 2; if (check(P, X, r, n, mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } cout << ans << "\n"; } int main() { iosbase::syncwithstdio(false); cin.tie(NULL); int T; >> T) { while (T--) { solve(); if (cin } } return 0; }