Bedao Mini Contest 11 - SQRCUT
Xem dạng PDF
Gửi bài giải
Điểm:
0,10 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho tờ giấy hình chữ nhật có kích thước ~a \times b~ ~(a > b)~. tahp sau đó gấp chéo tờ giấy tạo thành đường gấp có góc ~45~ ~độ~, một mép trùng với một cạnh của tờ giấy, sau đó cắt phần giấy thừa không bị gấp đè lên đi. Sau khi cắt thì tahp sẽ có một mảnh giấy hình vuông kích thước ~b~ x ~b~ và một mảnh kích thước ~b \times (a - b)~. tahp lại tiếp tục thực hiện thao tác như trên với mảnh giấy ~b \times (a - b)~ cho đến khi tất cả mảnh giấy đều là hình vuông.
Yêu cầu: hãy xác định số lần tahp cần cắt để các mảnh giấy trở thành hình vuông.
Input
- Dòng đầu tiên ~t~ số lượng test case ~(1 \le t \le 100)~.
- Gồm ~t~ dòng mỗi dòng chứa hai số nguyên ~a~ và ~b~ ~(1 \le a, b \le 10^{9})~, cách bởi ~1~ dấu cách.
Output
- Ghi ra số lần cắt.
Sample Input
1
10 7
Sample Output
5
Subtask
- ~50\%~ số test có ~t \le 10~ và ~(1 \le a, b \le 10^{6})~
- Số test còn lại không có điều kiện gì thêm.
Note
Ta có ~a~, ~b~ ~(a > b)~ là độ dài các cạnh của hình có diện tích bé nhất sau mỗi lần cắt.
Ta có: ~a = 10~, ~b = 7~
- Lần cắt thứ ~1~ : ~a~ = ~7~, ~b~ = ~3~.
- Lần cắt thứ ~2~ : ~a~ = ~4~, ~b~ = ~3~.
- Lần cắt thứ ~3~ : ~a~ = ~3~, ~b~ = ~1~.
- Lần cắt thứ ~4~ : ~a~ = ~2~, ~b~ = ~1~.
- Lần cắt thứ ~5~ : ~a~ = ~1~, ~b~ = ~1~.
Vậy sau ~5~ lần cắt các mảnh giấy đều thành hình vuông.
Bình luận
bài này test yếu đúng k ạ vì làm while trừ 2 vế dần dần mà cx ac ạ ?
Mọi người ơi em có làm bài này theo cách dùng while ... do nhưng mà nó bị quá thời gian ý ạ, em có xem lời giải nhưng mà không hiểu được, không biết có cách nào có thể giúp em làm bài này không ạ ?
Bạn hiểu sai đề bài rồi. Lời giải cho các dạng bài nhiều test case thường có dạng:
dạ em cảm ơn anh, nhờ anh em làm được rồi ạ hehe