Ngân hàng 2

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp while Làm tròn số

Đề bài

Anh Bo có $n$ đồng và đem gửi ngân hàng với lãi suất $10\%$ mỗi năm. Cuối mỗi năm, tiền lãi được nhập vào tiền gốc để tính lãi cho năm sau. Ngân hàng chỉ trả tiền lãi là số nguyên: nếu tiền lãi có phần lẻ thì làm tròn đến hàng đơn vị theo quy tắc từ $0.5$ trở lên thì làm tròn lên, dưới $0.5$ thì làm tròn xuống.

Ví dụ: có $100$ đồng thì sau năm thứ nhất có $110$ đồng, sau năm thứ hai có $110 + 11 = 121$ đồng. Có $15$ đồng thì lãi là $1.5$, làm tròn thành $2$, sau một năm có $17$ đồng.

Anh Bo sẽ rút tiền ngay khi số tiền trong tài khoản lớn hơn hoặc bằng $m$ đồng. Hỏi sau bao nhiêu năm anh Bo rút được tiền? Nếu ngay từ đầu $n = m$ thì anh Bo rút luôn, đáp án là $0$.

Dữ liệu vào:

Một dòng gồm hai số nguyên $n$ và $m$.

Kết quả:

In ra một số nguyên là số năm ít nhất để số tiền đạt ít nhất $m$ đồng.

Giới hạn:

• $10 \le n \le m \le 10^9$

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

100 120

Ví dụ 1 – output

2

Ví dụ 2 – input

100 110

Ví dụ 2 – output

1

Ví dụ 3 – input

15 17

Ví dụ 3 – output

1

• Ví dụ 1: $100 \to 110 \to 121$. Sau 1 năm mới có $110 < 120$, sau 2 năm có $121 \ge 120$.
• Ví dụ 2: sau 1 năm có đúng $110$ đồng, đủ $m$ nên rút luôn.
• Ví dụ 3: lãi năm đầu $1.5$ được làm tròn lên $2$, có $17$ đồng.

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

Lời mở đầu

Bài gửi tiết kiệm kinh điển: mỗi năm tiền tăng 10%, hỏi bao lâu thì đủ $m$ đồng. Ta không biết trước phải lặp bao nhiêu lần – đó chính là lúc dùng while. Điểm khó nằm ở quy tắc làm tròn tiền lãi và điều kiện dừng "lớn hơn hoặc bằng". Ghi chú: đề gốc không nói trường hợp $n = m$; mình ghi rõ trong đề là rút luôn, đáp án $0$.

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ưởngmô phỏng từng nămLờ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ả $10 \le n \le m \le 10^9$.

Test	Nội dung kiểm tra
1–3, 13	Ví dụ đề, $n = m$ (đáp án 0), số tiền đạt đúng bằng $m$
4–8, 10	Số nhỏ có lãi lẻ $\ge 0.5$ (15, 25, 35, 45, 95…) phải làm tròn lên; $10 \to 20$ đi qua nhiều mức lãi lẻ
9, 11, 17–19	Gửi nhiều năm (tới 194 năm): sai số làm tròn cộng dồn
11–20	Số tiền gần $10^9$: phép nhân x * 11 vượt giới hạn int
20	Sau 10 năm số tiền đạt đúng bằng $m$

Ý tưởngMô phỏng từng năm bằng while

Gọi $x$ là số tiền hiện có (ban đầu $x = n$) và đếm số năm. Chừng nào $x < m$ thì gửi thêm một năm: cộng lãi vào $x$ và tăng số năm lên 1. Khi $x \ge m$ thì dừng và in số năm.

Lãi đúng là $x / 10$ (có thể lẻ). Làm tròn "từ 0.5 trở lên thì lên" với số nguyên có một mẹo quen thuộc: cộng thêm nửa đơn vị rồi chia nguyên:

lai = (x + 5) / 10

Ví dụ $x = 15$: $(15 + 5) / 10 = 2$ (lãi $1.5$ làm tròn lên $2$); $x = 14$: $(14 + 5) / 10 = 1$ (lãi $1.4$ làm tròn xuống $1$).

Điều kiện dừng

Anh Bo rút khi tiền lớn hơn hoặc bằng $m$ → vòng lặp chạy khi x < m. Viết nhầm x <= m thì khi tiền đúng bằng $m$ vẫn gửi thêm một năm, và với $n = m$ sẽ in 1 thay vì 0.

Vòng lặp chạy bao nhiêu lần? Mỗi năm tiền tăng ít nhất 1 đồng và khi tiền lớn thì tăng khoảng 10%, nên kể cả $n = 10$, $m = 10^9$ cũng chỉ cần 194 năm – rất nhanh.

Em nhập $n$, $m$ rồi bấm Tiếp để xem tiền trong tài khoản tăng qua từng năm:

n = m =

Ví dụ nhanh:

Lời giảiwhile (x < m)

Mọi biến dùng long long cho an toàn (số tiền có thể vượt $10^9$ một chút ở năm cuối).

C++▶ Chạy tay từng dòng codeLặp từng năm: cộng lãi đã làm tròn, đếm số năm.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. (x + 5) / 10 là phép chia nguyên của hai số nguyên nên tự bỏ phần lẻ – cộng 5 trước là để "từ 0.5 trở lên thì lên".
2. Python: dùng // (chia nguyên). Đừng dùng hàm round() của Python: nó làm tròn kiểu "ngân hàng" (round(2.5) = 2, round(3.5) = 4) chứ không phải luôn làm tròn lên.
3. Dùng int vẫn được nếu viết x + (x + 5) / 10, nhưng cách viết gộp (x * 11 + 5) / 10 sẽ tràn int khi $x$ khoảng $2 \cdot 10^8$ trở lên.

Không gian$O(1)$

Thời gian$O(\text{số năm})$ – tối đa 194 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.026s. 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ú
Lãi tính bằng x / 10 (luôn làm tròn xuống)	10/20	sai test 4, 5, 6, 7, 8, 10, 11, 17, 18, 20
Điều kiện lặp x <= m	11/20	sai test 2, 3, 4, 5, 7, 8, 10, 13, 20
Dùng double: x = x * 1.1, không làm tròn	14/20	sai test 4, 5, 7, 8, 10, 17
Dùng int và viết x = (x * 11 + 5) / 10	11/20	sai test 11, 12, 14, 15, 16, 17, 18, 19, 20
Python: x += round(x / 10)	18/20	sai test 5, 7

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.026s	Full điểm
Làm tròn xuống	C++	10/20	–	Mất 10 test
x <= m	C++	11/20	–	Mất 9 test
double, không làm tròn	C++	14/20	–	Mất 6 test
x*11 tràn int	C++	11/20	–	Mất 9 test
round() Python	C++	18/20	–	Mất 2 test

Ghi chú của mình: với bài có tiền và làm tròn, hãy giữ mọi thứ là số nguyên và tự làm tròn bằng phép chia nguyên. Số thực và các hàm làm tròn có sẵn đều có "tính cách" riêng dễ làm 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 😇