Bố con

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp while Tìm công thức

Đề bài

Bố con Tí sống trên Sao Hoả, nơi con người sống thọ tới hàng tỷ tỷ năm. Hiện tại bố $a$ tuổi, Tí $b$ tuổi. Hỏi bao nhiêu năm nữa thì tuổi bố gấp đôi tuổi Tí?

Đề bài đảm bảo $a \ge 2b$, tức là thời điểm tuổi bố gấp đôi tuổi Tí là bây giờ hoặc trong tương lai.

Dữ liệu vào:

Một dòng gồm hai số nguyên dương $a$ và $b$ lần lượt là tuổi bố và tuổi Tí hiện tại.

Kết quả:

In ra một số nguyên không âm là số năm nữa tuổi bố gấp đôi tuổi Tí (in $0$ nếu bây giờ tuổi bố đã gấp đôi tuổi Tí).

Giới hạn:

• $1 \le b < a \le 10^{18}$, $a \ge 2b$

Subtask:

• Subtask 1 (40% số điểm): $a \le 1000$.
• Subtask 2 (30% số điểm): $a \le 10^9$.
• Subtask 3 (30% số điểm): không có ràng buộc gì thêm.

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

30 5

Ví dụ 1 – output

20

Ví dụ 2 – input

100 50

Ví dụ 2 – output

0

• Ví dụ 1: sau 20 năm bố $50$ tuổi, Tí $25$ tuổi, $50 = 2 \cdot 25$.
• Ví dụ 2: bây giờ bố $100$ tuổi đã gấp đôi Tí $50$ tuổi.

Nguồn: phỏng theo bài "BỐ CON" – vinhdinhcoder.net (chủ đề Lặp WHILE).

Lời mở đầu

Cách nghĩ đầu tiên: cho thời gian trôi từng năm bằng while tới khi tuổi bố gấp đôi tuổi Tí. Cách này đúng, nhưng bố con Tí sống trên Sao Hoả, tuổi tới $10^{18}$ – lặp từng năm thì đợi tới… Sao Hoả mọc đằng Tây. Bài này dạy em biết khi nào nên bỏ vòng lặp để dùng công thức. Ghi chú: đề gốc không có phần dữ liệu vào và giới hạn, và nếu tuổi bố nhỏ hơn 2 lần tuổi Tí thì "gấp đôi" đã ở trong quá khứ. Mình bổ sung: đảm bảo $a \ge 2b$, $a \le 10^{18}$, chia 3 subtask để cả cách lặp lẫn cách công thức đều có điểm phù hợp.

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ưởnga − 2bLờ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. Test 1–8 thuộc subtask 1 ($a \le 1000$), test 9–14 thuộc subtask 2 ($a \le 10^9$), test 15–20 có $a$ tới $10^{18}$.

Test	Nội dung kiểm tra
1–8	Ví dụ đề, đáp án 0 ($a = 2b$), $a = 2, b = 1$, Tí mới 1 tuổi
9–14	Tuổi tới $10^9$: đáp án gần $10^9$ – lặp từng năm bằng Python quá chậm
15–20	Tuổi tới $10^{18}$: vượt int, và mọi vòng lặp từng năm đều quá chậm

Ý tưởngTừ vòng lặp tới công thức

Cách 1 – mô phỏng: mỗi năm bố và Tí cùng thêm 1 tuổi. Chừng nào tuổi bố còn lớn hơn 2 lần tuổi Tí thì cho qua thêm 1 năm và đếm. Số vòng lặp đúng bằng đáp án – tới $10^{18}$ vòng thì không máy nào chạy kịp.

Cách 2 – công thức: sau $x$ năm, bố $a + x$ tuổi, Tí $b + x$ tuổi. Cần:

$a + x = 2(b + x) \iff a + x = 2b + 2x \iff x = a - 2b$

Nhìn vào "khoảng cách"

Xét hiệu $a - 2b$: mỗi năm tuổi bố tăng 1, còn 2 lần tuổi Tí tăng 2, nên hiệu này giảm đúng 1 mỗi năm. Vòng lặp chỉ đang đếm ngược hiệu từ $a - 2b$ về $0$ – vậy in luôn $a - 2b$! Đề đảm bảo $a \ge 2b$ nên kết quả không âm.

Hãy xem mô phỏng: chương trình lặp vài năm đầu, rồi "nhảy" thẳng tới đáp án bằng công thức.

Em nhập tuổi bố $a$, tuổi Tí $b$ rồi bấm Tiếp để cho thời gian trôi:

a = b =

Ví dụ nhanh:

Lời giảiMột dòng công thức

Code đầy đủ chỉ có đọc và in. Mọi biến là long long vì tuổi tới $10^{18}$.

C++▶ Chạy tay từng dòng codeTính thẳng x = a − 2b.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Đề đảm bảo $a \ge 2b$ nên $2b \le a \le 10^{18}$, phép 2 * b không tràn long long.
2. Code lặp từng năm vẫn là một lời giải tốt cho subtask 1 – nhiều khi em nên viết nó trước để kiểm tra công thức trên các số nhỏ.

Không gian$O(1)$

Thời gian$O(1)$ (lặp từng năm là $O(a - 2b)$)

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.028s. 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ú
C++: lặp từng năm while (bo > 2 * con)	16/20	sai test 15, 17, 18, 19
Python: lặp từng năm	12/20	sai test 9, 11, 12, 13, 15, 17, 18, 19
Công thức đúng nhưng dùng int	14/20	sai test 15, 16, 17, 18, 19, 20
In $a - b$ (hiệu tuổi, không phải số năm)	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Dùng do … while (luôn đếm ít nhất 1 năm)	11/20	sai test 2, 3, 5, 10, 15, 16, 17, 18, 19

Vì sao bản C++ lặp vẫn qua được subtask 2? Máy tính chạy được khoảng $10^8$–$10^9$ phép tính đơn giản mỗi giây: với đáp án gần $10^9$, vòng lặp C++ trên máy mình mất khoảng 0,7–1 giây – rất sát giới hạn 1 giây, nộp lên có thể bị TLE vài test. Python chậm hơn chục lần nên chỉ qua subtask 1. Còn với $10^{18}$ vòng thì không ngôn ngữ nào cứu nổi.

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.028s	Full điểm
Lặp từng năm	C++	16/20	–	Mất 4 test
Lặp từng năm (Py)	C++	12/20	–	Mất 8 test
Dùng int	C++	14/20	–	Mất 6 test
In a − b	C++	0/20	–	Mất 20 test
do … while	C++	11/20	–	Mất 9 test

Ghi chú của mình: khi một vòng lặp chỉ "đếm" một đại lượng thay đổi đều đặn (mỗi bước giảm đúng 1), hãy thử tính thẳng số bước bằng công thức. Đó là bước đầu tiên của tư duy tối ưu thuật toán.

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 😇