Kê chân bàn

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp while Lũy thừa của 2

Đề bài

Cái bàn học của Tí bị cập kênh vì một chân bàn ngắn hơn ba chân còn lại, khoảng hở dưới chân bàn đó là $b$. Tí lấy một tờ giấy dày $a$ để kê. Tí có thể gấp đôi tờ giấy nhiều lần: gấp lần thứ nhất thì xấp giấy dày $2a$, gấp lần thứ hai dày $4a$, gấp lần thứ ba dày $8a$, …

Xấp giấy kê vào phải không được dày hơn $b$ (nếu không sẽ không nhét vừa), nhưng càng dày thì bàn càng ít cập kênh. Hỏi Tí cần gấp tờ giấy bao nhiêu lần để bàn ít cập kênh nhất?

Dữ liệu vào:

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

Kết quả:

In ra số lần gấp $k$ lớn nhất sao cho $a \cdot 2^k \le b$ ($k$ có thể bằng $0$ – không cần gấp lần nào).

Giới hạn:

• $1 \le a \le b \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

1 4

Ví dụ 1 – output

2

Ví dụ 2 – input

2 5

Ví dụ 2 – output

1

Ví dụ 3 – input

5 5

Ví dụ 3 – output

0

• Ví dụ 1: $1 \to 2 \to 4$: gấp 2 lần được xấp dày $4 = b$, vừa khít.
• Ví dụ 2: $2 \to 4$, gấp thêm lần nữa sẽ dày $8 > 5$ nên chỉ gấp 1 lần.
• Ví dụ 3: tờ giấy đã dày đúng bằng khoảng hở, không cần gấp.

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

Lời mở đầu

Gấp đôi tờ giấy tới khi không gấp được nữa – một bài while rất "đời". Chỗ cần cẩn thận là điều kiện lặp: ta chỉ gấp thêm khi xấp giấy sau khi gấp vẫn không dày hơn $b$. Ghi chú: đề gốc diễn đạt hơi khó hiểu ("kê ít gập ghềnh nhất"); mình ghi rõ trong đề: tìm $k$ lớn nhất để $a \cdot 2^k \le b$, và $k$ có thể bằng 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ưởnggấp khi 2a ≤ bLờ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 b \le 10^9$.

Test	Nội dung kiểm tra
1–3	Ví dụ đề: vừa khít ($1 \to 4$), không khít, $a = b$
4–7	Không gấp được lần nào ($b < 2a$), $a = b = 1$, gấp đúng 1 lần
8–10	Gấp vừa khít ($3 \cdot 2^4 = 48$) và thiếu 1 đơn vị ($47$)
11–20	Số tới $10^9$: $1 \to 2^{29}$, $2^{29} - 1$, $a = b = 10^9$, $a$ lớn hơn một nửa $b$…

Ý tưởngGấp chừng nào còn gấp được

Gọi $a$ là độ dày hiện tại, $k$ là số lần đã gấp (ban đầu $k = 0$). Nếu gấp thêm một lần, xấp giấy dày $2a$. Chừng nào $2a \le b$ thì gấp: $a = 2a$, $k$ tăng 1. Khi $2a > b$ thì gấp thêm sẽ không nhét vừa → dừng, in $k$.

Kiểm tra trước, gấp sau

Điều kiện phải là a * 2 <= b (độ dày sau khi gấp). Viết a <= b rồi gấp thì vòng lặp gấp quá tay 1 lần; viết a * 2 < b thì bỏ lỡ trường hợp vừa khít như ví dụ 1.

Độ dày tăng gấp đôi mỗi lần nên chỉ cần tối đa khoảng $\log_2 10^9 \approx 30$ lần lặp. Ở đây $a \le b \le 10^9$ nên a * 2 không vượt $2 \cdot 10^9$, vẫn vừa int – nhưng mình vẫn dùng long long cho yên tâm.

Em nhập $a$, $b$ rồi bấm Tiếp để xem từng lần gấp:

a = b =

Ví dụ nhanh:

Lời giảiwhile (a * 2 <= b)

Biến $a$ được dùng luôn làm "độ dày hiện tại".

C++▶ Chạy tay từng dòng codeGấp đôi chừng nào độ dày sau khi gấp vẫn không vượt b.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Với $a = b$ hoặc $b < 2a$, điều kiện sai ngay từ đầu, thân vòng lặp không chạy lần nào và chương trình in 0 – đúng như mong muốn. Đây là ưu điểm của while so với do … while.
2. Cách khác: lặp chia b / a cho 2 tới khi nhỏ hơn 2 cũng ra cùng đáp án, nhưng mô phỏng gấp giấy dễ hiểu hơn.

Không gian$O(1)$

Thời gian$O(\log (b / a))$ – tối đa 29 vòng

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. 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ú
Điều kiện a * 2 < b (bỏ lỡ trường hợp vừa khít)	14/20	sai test 1, 6, 8, 12, 15, 17
Lặp while (a <= b) rồi in $k$ (gấp quá tay 1 lần)	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Hiểu nhầm: gấp tới khi xấp giấy dày $\ge b$	9/20	sai test 2, 4, 7, 9, 10, 11, 13, 16, 18, 19, 20
Dùng do … while (luôn gấp ít nhất 1 lần)	14/20	sai test 3, 4, 5, 7, 14, 16

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.003s	Full điểm
	Python	20/20	0.022s	Full điểm
a * 2 < b	C++	14/20	–	Mất 6 test
Thừa 1 lần	C++	0/20	–	Mất 20 test
Hiểu nhầm đề	C++	9/20	–	Mất 11 test
do … while	C++	14/20	–	Mất 6 test

Ghi chú của mình: trước khi viết while, hãy tự hỏi: "điều kiện này kiểm tra trạng thái trước hay sau khi làm?" và thử ngay với trường hợp vòng lặp không chạy lần nào ($a = b$).

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 😇