Bedao Mini Contest 11 - SQRCUT

View as PDF
Submit solution
Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem type
Allowed languages
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.

Comments

Please read the guidelines before commenting.


  • 0
    linhlinhcute  commented on Oct. 4, 2023, 10:54 a.m.

    bài này test yếu đúng k ạ vì làm while trừ 2 vế dần dần mà cx ac ạ ?


  • 1
    DatNewBie  commented on Aug. 21, 2022, 9:11 a.m.

    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 ạ ?


    • 3
      jalsol  commented on Aug. 21, 2022, 1:17 p.m.

      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:

      int t; cin >> t;

for (int i = 0; i < t; i++) {
    int a, b; cin >> a >> b;
    int dem = 0;

    // giải quyết bài toán theo đề với 2 số a và b tại đây

    cout << dem << '\n';
}

      • 1
        DatNewBie  commented on Aug. 22, 2022, 3:36 a.m.

        dạ em cảm ơn anh, nhờ anh em làm được rồi ạ hehe