Tiết kiệm ngân hàng

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp while Lãi kép

Đề bài

Bạn có $a$ đồng và gửi tiết kiệm ở ngân hàng với lãi suất $1{,}1\%$ mỗi tháng. Cuối mỗi tháng, tiền lãi (bằng $1{,}1\%$ số tiền đang có) được cộng dồn vào gốc, tức là số tiền được nhân với $1{,}011$. Tiền là số thực, không làm tròn.

Hỏi cần gửi ít nhất bao nhiêu tháng để số tiền lớn hơn hoặc bằng $x$ đồng? Nếu ngay từ đầu $a \ge x$ thì in ra $0$.

Dữ liệu vào:

Một dòng gồm hai số nguyên dương $a, x$ cách nhau bởi dấu cách.

Kết quả:

In ra một số nguyên là số tháng ít nhất cần gửi.

Giới hạn:

• $1 \le a \le x < 10^9$
• Dữ liệu đảm bảo số tiền sau mỗi tháng không quá sát $x$ (lệch nhau hơn $10^{-6}$ lần $x$), nên tính bằng double không bị sai số.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

2000000 2500000

Ví dụ 1 – output

21

Ví dụ 2 – input

100 101

Ví dụ 2 – output

1

Ví dụ 3 – input

777 777

Ví dụ 3 – output

0

• Ví dụ 1: sau 20 tháng có khoảng $2\,489\,161{,}7$ đồng (chưa đủ), sau 21 tháng có khoảng $2\,516\,542{,}5$ đồng.
• Ví dụ 2: sau 1 tháng có $101{,}1 \ge 101$ đồng.
• Ví dụ 3: đã có đủ $777$ đồng nên không cần gửi tháng nào.

Nguồn: phỏng theo bài "TIẾT KIỆM NGÂN HÀNG" – vinhdinhcoder.net (chủ đề Lặp WHILE).

Lời mở đầu

Bài toán lãi kép quen thuộc: mỗi tháng tiền được nhân với $1{,}011$, hỏi bao lâu thì đủ $x$ đồng. Không biết trước số vòng lặp → dùng while. Ghi chú: đề gốc chỉ nói "a và x là các số nguyên chưa đến 1 tỉ"; mình chốt $1 \le a \le x < 10^9$, nếu $a = x$ thì không cần gửi tháng nào (in 0), tiền là số thực không làm tròn, và các test được chọn để không có tháng nào số tiền sát $x$ (tránh sai số double).

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngwhile (tiền < x)Lời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Mọi test thoả $1 \le a \le x < 10^9$.

Test	Nội dung kiểm tra
1, 5, 6	Ví dụ đề và các trường hợp cần 1–2 tháng
2–4	$a = x$: đáp án 0 – bắt lỗi điều kiện tien <= x
7–9, 13, 16, 19	$a$ rất nhỏ (1, 2, 7, 10...): cần hàng trăm tới gần 1900 tháng; tiền kiểu long long sẽ "đứng yên"
10–12, 14–15, 17–18, 20	Các khoảng cách khác nhau giữa $a$ và $x$

Ý tưởngNhân 1,011 cho tới khi đủ tiền

Gọi tien là số tiền hiện có (bắt đầu bằng $a$), thang = 0. Chừng nào tien < x thì gửi thêm một tháng: tien = tien * 1.011; thang++;. Khi vòng lặp dừng, thang là đáp án.

Vì kiểm tra điều kiện trước khi vào vòng, trường hợp $a \ge x$ tự động cho 0 tháng.

Tiền phải là số thực

Lãi tháng đầu của 100 đồng là 1,1 đồng. Nếu tien là long long, phần lẻ bị cắt mất; tệ nhất là với $a = 1$: $1 \cdot 1{,}011 = 1{,}011 \to 1$, tiền không bao giờ tăng và chương trình lặp mãi!

Em nhập dữ liệu rồi bấm Tiếp để xem từng vòng lặp chạy thế nào:

a = x =

Ví dụ nhanh:

Lời giảiVòng lặp while với biến double

Biến tien là double, biến đếm thang là int.

C++▶ Chạy tay từng dòng codeNhân tiền với 1.011 cho tới khi tiền ≥ x, đếm số tháng.

Dữ liệu vào (stdin) – sửa thoải mái100 101

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. tien = tien * 1.011 tương đương tien += tien * 0.011 (gốc cộng lãi).
2. So sánh tien < x giữa double và long long là hợp lệ: $x$ được tự đổi sang double.
3. Số vòng lặp lớn nhất khoảng 1900 (khi $a = 1$, $x$ gần $10^9$) – rất nhanh.

Không gian$O(1)$

Thời gian$O(\log_{1{,}011} \frac{x}{a})$ (tối đa khoảng 1900 vòng)

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Bản Python đúng 20/20 test, chạy lâu nhất 0.022s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Tiền kiểu long long (phần lẻ của lãi bị cắt)	14/20	sai test 7, 8, 9, 13, 16, 19
Điều kiện lặp tien <= x (đòi lớn hơn hẳn $x$)	17/20	sai test 2, 3, 4
Lãi đơn: tien = a + a * 0.011 * k	10/20	sai test 1, 7, 8, 9, 12, 13, 14, 15, 16, 19
Nhầm 1,1% thành 11%: nhân 1.11	7/20	sai test 1, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 19, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.004s	Full điểm
	Python	20/20	0.022s	Full điểm
Tiền long long	C++	14/20	–	Mất 6 test
Điều kiện <=	C++	17/20	–	Mất 3 test
Lãi đơn	C++	10/20	–	Mất 10 test
Nhân 1.11	C++	7/20	–	Mất 13 test

Ghi chú của mình: với vòng lặp while, hãy thử ngay trường hợp không vào vòng lần nào (ở đây là $a = x$) – đó là chỗ điều kiện < hay <= lộ ra đúng sai.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇