GAGI - Gấp giấy
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.003s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
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àathì 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?
Input
- Là hai số nguyêna,bcách nhau một khoảng trắng (1 ≤a≤b≤ 1.000)
Output
- Là số nguyên xác định số lần gấp giấy.
Sample
Input #1
1 4
Output #1
2
Input #2
2 5
Output #2
1
Problem source: NTUCoder
Bình luận
Sqrt thì sao ạ, Căn bậc hai
Code trâu cũng là 1 cách. 谢谢你帮我
Ý tưởng: Dễ thấy độ dày của giấy sẽ tăng theo hàm a * 2^n (n là số lần gấp giấy, a là độ dày ban đầu).
Như vậy ta cần tìm n sao cho: a * 2^n <= b
<=> 2^n <= b / a
<=> n <= long long(log2(b / a)) (n nguyên lên ta ép kiểu long long là đc) (trong C++ có sẵn hàm log2)