Gấp Giấy (GAGI)

Nguồn: NTUCoder Độ khó: Dễ Toán học Logarit Công thức

Đề bài

GAGI – Gấp giấy

Thấy chân bàn bị gập ghềnh nên Nam lấy một tờ giấy lần lượt gấp đôi lại nhiều lần để kê chân bàn. Giả sử tờ giấy có bề dày là $a$ thì sau lần gấp đôi thứ nhất bề dày là $2a$, sau lần gấp đôi thứ 2 là $4a$, lần thứ 3 là $8a$, ... Nếu khoảng gập ghềnh là $b$ thì Nam cần gấp đôi giấy bao nhiêu lần để kê chân bàn ít bị gập ghềnh nhất?

Dữ liệu nhập:

• Là hai số nguyên $a$, $b$ cách nhau một khoảng trắng $(1 \le a \le b \le 1000)$.

Dữ liệu xuất:

• Là số nguyên xác định số lần gấp giấy.

Chú ý: Vì bàn khá nặng không khiêng được nên bề dày giấy gấp không được lớn hơn khoảng gập ghềnh.

Giới hạn: thời gian 1 giây, bộ nhớ 128 MB.

Ví dụ 1 – input

1 4

Ví dụ 1 – output

2

Ví dụ 2 – input

2 5

Ví dụ 2 – output

1

Lời mở đầu

Tội nghiệp Nam không có tiền mua bàn mới, các bạn hãy tính toán giúp Nam kê bàn với 😅. Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Trước khi vào bài, các bạn nhớ lại ngưỡng an toàn mình hay nhắc: với các hệ thống chấm giới hạn 1 giây thì toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần (C/C++), cao lắm là $10^8$ thì hên xui; Python, Java, C# chạy chậm hơn nên ngưỡng còn thấp hơn nữa. Đề cho 2 giây thì nhân 2 ngưỡng lên, 100 ms thì chia 10, cứ thế thôi. Bài này giới hạn 1 giây.

Giải thích ví dụ cho bạn nào chưa hiểu đề: bề dày tờ giấy cứ mỗi lần gấp thì gấp đôi lên, và bề dày đó không được vượt quá khoảng gập ghềnh $b$ (vì bàn nặng quá không nhấc lên nhét giấy dày hơn được). Muốn kê "ít gập ghềnh nhất" thì phải gấp càng nhiều lần càng tốt, miễn vẫn còn $\le b$.

Ví dụ	Số lần gấp	Bề dày	So với b
a = 1, b = 4	0	1	≤ 4
	1	2	≤ 4
	2	4	≤ 4 ✔ (dừng ở đây)
	3	8	> 4
a = 2, b = 5	0	2	≤ 5
	1	4	≤ 5 ✔ (dừng ở đây)
	2	8	> 5

Nên đáp án lần lượt là $2$ và $1$.

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:

Cách 1Gấp thử từng lần · O(log(b/a))Cách 2Công thức log2 · 1 dòng

Cách 1Làm theo đúng luật của đề – O(log(b/a))

Cách làm đơn giản nhất là cứ làm đúng theo luật đề đưa ra: liên tục kiểm tra xem còn gấp đôi được nữa không. Tức là kiểm tra a * 2, nếu vẫn thỏa <= b thì được phép gấp, ta gấp luôn (a *= 2) và tăng biến đếm lên. Cứ thế lặp lại đến khi nào không thể gấp đôi được nữa, tức là a * 2 > b, thì dừng lại và in biến đếm ra.

Ý chính

Kiểm tra trước khi gấp: điều kiện vòng lặp là a * 2 <= b chứ không phải a <= b. Nếu viết while(a <= b) rồi mới gấp thì sẽ đếm dư 1 lần (lần gấp cuối làm giấy dày hơn $b$).

Em nhập $a$, $b$ rồi bấm Tiếp để xem tờ giấy dày lên từng lần gấp, so với vạch $b$ màu cam:

a b

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    while(a * 2 <= b){
        a *= 2;
        cnt++;
    }
    cout << cnt;
    return 0;
}

a, b = map(int, input().split())
cnt = 0
while a * 2 <= b:
    a *= 2
    cnt += 1
print(cnt)

Bấm Tiếp để chạy tay từng dòng code:

C++▶ Chạy tay từng dòng codeCách 1: còn gấp đôi được (a * 2 <= b) thì gấp và đếm.

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

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 int a, b;

6 cin >> a >> b;

7 int cnt = 0;

8 while(a * 2 <= b){

9 a *= 2;

10 cnt++;

11 }

12 cout << cnt;

13 return 0;

14}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$, chỉ vài biến.
• Thời gian: $O(\log_2(b/a))$. Vì sao lại là logarit? Các bạn nhớ lại kiến thức Toán cấp 3: $\log_2(2^k) = k$, ví dụ $\log_2 8 = 3$, $\log_2 4 = 2$. Ta cần tìm số lần gấp $x$ lớn nhất sao cho:
  $a \cdot 2^x \le b \iff 2^x \le \dfrac{b}{a} \iff \log_2(2^x) \le \log_2\dfrac{b}{a} \iff x \le \log_2\dfrac{b}{a}$
  Vậy số lần lặp của vòng while chính là phần nguyên của $\log_2(b/a)$. Quy ước khi ghi độ phức tạp thì logarit cơ số mấy cũng chỉ cần viết gọn là $\log$, nên ghi $O(\log(b/a))$ cũng được.

Không gian$O(1)$

Thời gian$O(\log(b/a))$

Thực ra xem như O(1) luôn

Trường hợp xấu nhất $a = 1$, $b = 1000$ thì $\log_2 1000 \approx 9{,}97$, tức vòng lặp chạy có 9 lần – bé như một hằng số. Kể cả kiểu số nguyên 8 byte lớn nhất cũng chỉ cỡ $2^{64}$, $\log_2$ của nó cũng mới là $64$. Nên kết luận $O(1)$ cũng không sai, code này làm sao mà TLE được đúng không các bạn ^^

Kiểm tra công thức với vài ví dụ:

• $a = 2, b = 8$: $2 \to 4 \to 8$, nhân thêm thành $16 > 8$ nên gấp $2$ lần. Và $b/a = 4$, $\log_2 4 = 2$ ✔.
• $a = 1, b = 8$: $1 \to 2 \to 4 \to 8$ nên gấp $3$ lần. Và $b/a = 8$, $\log_2 8 = 3$ ✔.
• $a = 3, b = 16$: $3 \to 6 \to 12$, nhân thêm thành $24 > 16$ nên gấp $2$ lần. Và $b/a = 5{,}333\ldots$, $\log_2 5{,}333\ldots \approx 2{,}415$, lấy phần nguyên được $2$ ✔.

Nếu $b/a$ đúng dạng $2^k$ thì đáp án bằng đúng $\log_2(b/a)$; còn không thì đáp án là phần nguyên (nhỏ hơn) của nó.

Cách 2Một dòng với hàm log2

Đã nhìn ra số lần lặp cũng chính là đáp án $\left\lfloor \log_2(b/a) \right\rfloor$ thì ta đâu cần lặp làm gì nữa, chỉ cần 1 dòng lệnh là tính ra ngay. Thư viện toán học của C/C++ có sẵn hàm log2, gọi ra dùng cho khỏe; Python thì có math.log2.

Công thức

$\text{đáp án} = \left\lfloor \log_2 \dfrac{b}{a} \right\rfloor$  → trong C++: cout << (int)log2((double)b / a);

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    cout << (int)log2((double)b / a);
    return 0;
}

import math

a, b = map(int, input().split())
print(int(math.log2(b / a)))

C++▶ Chạy tay từng dòng codeCách 2: in phần nguyên của log2(b / a).

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

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 int a, b;

6 cin >> a >> b;

7 cout << (int)log2((double)b / a);

8 return 0;

9}

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

Thời gian$O(1)$

Nhớ ép kiểu (int)

Hàm log2 trả về số thực. Nếu không ép kiểu thì với $b/a = 8$ nó in ra 3.00000 (hoặc với $b/a = 16/3$ in ra 2.41503) và so với đáp án đúng là 3, 2 thì bị chấm sai. Ngoài ra mình ép (double)b để phép chia là chia số thực – nếu để b / a là chia nguyên thì $16/3$ thành $5$, may mắn vẫn ra đúng đáp án nhưng kiểu mình cẩn thận cho chắc, và mình nghĩ các bạn cũng nên như vậy.

Bài này rất dễ, nhưng trong kỳ thi có tính thời gian thì ăn nhau ở chỗ ai code nhanh hơn: dùng vòng lặp như cách 1 thì hơi dở, còn cách 2 chỉ cần 1 dòng là ra kết quả, rất gọn lẹ.

Mở rộng: nếu là gấp tư thì sao?

Giả sử mỗi lần bề dày tăng gấp 4 (tức a * 4), ta cần tính $\log_4(b/a)$. C/C++ không có hàm log4, chỉ có log2 và log10 thôi, nên phải "chế" ra bằng công thức đổi cơ số hồi cấp 3:

$\log_B A = \dfrac{\log_X A}{\log_X B}$  (X là cơ số tùy ý, miễn trên dưới giống nhau)

Áp dụng với $B = 4$, $A = b/a$: cout << (int)(log2((double)b / a) / log2(4.0));. Mình luôn ép kiểu số thực khi truyền vào các hàm log vì nguyên mẫu hàm nhận tham số số thực.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với toàn bộ 500.500 cặp $1 \le a \le b \le 1000$ (so với vòng lặp gấp đôi) – khớp hết, kể cả các trường hợp $b/a$ đúng bằng lũy thừa của 2; chạy thêm 300 bộ ngẫu nhiên trực tiếp với 4 chương trình cũng khớp. Hai cách đều chạy tức thì.

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 😇