Cắt Bìa (HSG9 TP Đà Nẵng 2018-2019 – Bài 2)

Nguồn: HSG lớp 9 TP Đà Nẵng 2018-2019 – Bài 2 Độ khó: Dễ Toán học Ước chung lớn nhất

Đề bài

Câu 2. Cắt bìa (3 điểm) – Kì thi chọn học sinh giỏi lớp 9 cấp thành phố Đà Nẵng, năm học 2018-2019, môn Tin học

Lan có 1 tấm bìa hình chữ nhật có các kích thước là $x$ (cm) và $y$ (cm), $(x, y \in \mathbb{N}^*)$. Lan muốn cắt tấm bìa này thành những hình vuông bằng nhau có độ dài cạnh là số nguyên (đơn vị cm) sao cho tấm bìa được cắt hết không còn thừa mảnh nào. Hỏi Lan có thể cắt được ít nhất mấy hình vuông?

Viết chương trình nhập từ bàn phím 2 số nguyên dương $x, y$ $(x, y \le 10^9$, mỗi số trên 1 dòng$)$ và in ra màn hình số nguyên $m$ là số lượng hình vuông cần tìm theo yêu cầu trên.

Giới hạn thời gian trên hệ thống chấm: 1 giây.

Nhập từ bàn phím

6
8

In ra màn hình

12

Lời mở đầu

Bài này nằm trong đề thi học sinh giỏi Tin học lớp 9 TP Đà Nẵng, 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 đi vào vấn đề chính, các bạn nhớ giúp mình: với giới hạn 1 giây, muốn không bị TLE thì toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất là $10^8$ (hên xui). Ngưỡng này là cho C/C++, Python, Java, C#... chạy chậm hơn thì ngưỡng phải thấp hơn.

Theo dữ kiện đề bài thì có 2 điều các bạn phải lưu ý:

1. Tấm bìa phải được cắt hết, không còn thừa mảnh nào.
2. Số lượng hình vuông cắt được là ít nhất.

Hình vuông có 4 cạnh bằng nhau nên ta chỉ lấy đại diện 1 cạnh ra xét. Tiêu chí 1 nghĩa là các hình vuông xếp sát nhau phải phủ kín tấm bìa, không dư không thiếu. Nói cách khác, cả chiều dài lẫn chiều rộng của tấm bìa đều phải chia hết cho cạnh hình vuông. Các bạn tưởng tượng xem có đúng không? Ví dụ tấm bìa $6 \times 8$:

Cạnh 2: $8 / 2 = 4$ cột, $6 / 2 = 3$ hàng ⇒ phủ kín, 12 hình vuông ✔

Cạnh 3: $6$ chia hết cho $3$ nhưng $8$ không ⇒ thừa một dải rộng 2 cm (đỏ) ✘

Tiêu chí 2: cạnh hình vuông càng nhỏ thì số hình vuông cắt ra càng nhiều. Đây là quy luật toán học đơn giản thôi: diện tích tấm bìa chỉ có nhiêu đó, diện tích tấm bìa chia cho diện tích hình vuông ra số lượng, hình vuông càng nhỏ thì kết quả càng lớn. Như ví dụ bìa $6 \times 8$ có diện tích $48$, lấy cạnh 1 thì cắt được tới $48 / 1 = 48$ hình vuông. Đề hỏi ít nhất nên ta phải chọn hình vuông có cạnh lớn nhất có thể.

Mấu chốt của bài

Tìm cạnh hình vuông lớn nhất sao cho cả $x$ và $y$ đều chia hết cho nó ⇒ đó chính là ước chung lớn nhất $g = \gcd(x, y)$.
Số hình vuông $= \dfrac{x \cdot y}{g^2} = \dfrac{x}{g} \cdot \dfrac{y}{g}$.

Với ví dụ: các ước chung của $6$ và $8$ là $1, 2$, lớn nhất là $g = 2$, nên số hình vuông là $\dfrac{6}{2} \cdot \dfrac{8}{2} = 3 \cdot 4 = 12$. Đúng output của đề.

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 1Thử cạnh từ min(x, y) lùi về 1 · O(min(x, y))Cách 2Dùng ƯCLN (Euclid) · O(log) · AC

Cách 1Thử cạnh từ min(x, y) lùi về 1 – O(min(x, y))

Bạn nào chưa nghĩ ra ƯCLN thì cứ làm vét cạn trước cho chắc: cạnh hình vuông không thể vượt quá cạnh ngắn hơn của tấm bìa, nên cho cạnh $a$ chạy từ $\min(x, y)$ lùi về 1. Gặp $a$ đầu tiên mà cả $x$ và $y$ đều chia hết thì đó là cạnh lớn nhất, in $(x / a) \cdot (y / a)$ rồi dừng luôn. Vòng lặp chắc chắn dừng vì $a = 1$ thì luôn chia hết.

Em nhập kích thước tấm bìa rồi bấm Tiếp để xem từng cạnh được thử, phần thừa (đỏ) xuất hiện khi nào:

x y

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() {
    long long x, y;
    cin >> x >> y;
    for(long long a = min(x, y); a >= 1; --a){
        if(x % a == 0 && y % a == 0){
            cout << (x / a) * (y / a);
            return 0;
        }
    }
    return 0;
}

x = int(input())
y = int(input())
a = min(x, y)
while a >= 1:
    if x % a == 0 and y % a == 0:
        print((x // a) * (y // a))
        break
    a -= 1

C++▶ Chạy tay từng dòng codeCách 1: a chạy từ min(x, y) lùi về 1, gặp a chia hết cả x và y thì in (x / a) * (y / a).

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main() {

5 long long x, y;

6 cin >> x >> y;

7 for(long long a = min(x, y); a >= 1; --a){

8 if(x % a == 0 && y % a == 0){

9 cout << (x / a) * (y / a);

10 return 0;

11 }

12 }

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)$.
• Thời gian: trường hợp xấu nhất là khi ƯCLN bằng 1 (ví dụ $x, y$ là 2 số nguyên tố khác nhau), vòng lặp phải chạy đủ $\min(x, y)$ lần ⇒ $O(\min(x, y))$.

Không gian$O(1)$

Thời gian$O(\min(x, y))$

TLE khi x, y lớn

Với $x, y$ gần $10^9$ và nguyên tố cùng nhau thì phải lặp gần $10^9$ lần, vượt xa ngưỡng $10^8$. Mình đo với $x = 999\,999\,937$, $y = 999\,999\,929$ (2 số nguyên tố) thì bản C++ chạy khoảng 3,3 giây ⇒ TLE, Python còn chậm hơn nhiều.

Cách 2Dùng ước chung lớn nhất – O(log(min(x, y)))

Tổng hợp 2 tiêu chí ở phần mở đầu thì bài toán nói rõ ra là: tìm ước chung lớn nhất của 2 cạnh tấm bìa, đó chính là cạnh hình vuông. Rồi lấy diện tích tấm bìa chia cho diện tích hình vuông là ra số lượng, cũng chính là đáp án.

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() {
    long long x, y;
    cin >> x >> y;
    long long gcd = __gcd(x, y);
    cout << (x / gcd) * (y / gcd);
    return 0;
}

import math

x = int(input())
y = int(input())
g = math.gcd(x, y)
print((x // g) * (y // g))

Giải thích 1 số chỗ trong cách làm ở trên:

1. Hàm __gcd

Để tìm ƯCLN mình dùng hàm __gcd có sẵn trong thư viện algorithm của C++ với trình biên dịch GCC (có ở các IDE như Code::Blocks, Dev-C++, Visual Studio Code...). Bạn nào dùng Visual Studio (trình biên dịch MSVC) thì gọi theo cú pháp std::gcd trong thư viện numeric nhé. Mình đang #include <bits/stdc++.h> là bao hết các thư viện, còn nếu không dùng thư viện này thì nhớ #include <algorithm> mới dùng được __gcd. Python thì có sẵn math.gcd.
Bạn nào không biết hàm có sẵn thì tự code thuật toán Euclid cũng rất đơn giản, đệ quy vài dòng là xong: long long gcd(long long a, long long b){ return b == 0 ? a : gcd(b, a % b); }. Mình thì thích dùng hàm có sẵn cho nhanh gọn mà luôn đảm bảo chính xác, chứ tự code lỡ xui gõ nhầm chỗ nào thì mệt lắm 😅.

2. Dùng long long và chia trước, nhân sau

Cạnh tấm bìa chỉ tối đa $10^9$, nhưng giả sử $x, y$ là 2 số nguyên tố gần $10^9$ thì ƯCLN chỉ là 1, đáp án là $x \cdot y$ gần $10^{18}$ ⇒ dùng int (4 byte) chắc chắn bị tràn số, phải dùng long long.
Thay vì tính diện tích $x \cdot y$ rồi chia cho $g \cdot g$, mình lấy (x / gcd) * (y / gcd): kết quả như nhau, nhưng chia trước khi số còn nhỏ rồi mới nhân 2 kết quả nhỏ thì đỡ phải tính toán với số lớn (với bài này $x \cdot y \le 10^{18}$ vẫn vừa long long, nhưng tập thói quen này thì sau gặp bài khác đỡ bị tràn).

Bấm Tiếp để chạy tay từng dòng code C++ ở trên, ở dòng gọi __gcd mình cho các bạn xem luôn bên trong thuật toán Euclid chạy thế nào:

C++▶ Chạy tay từng dòng codeCách 2: gcd = __gcd(x, y) (thuật toán Euclid), in (x / gcd) * (y / gcd).

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main() {

5 long long x, y;

6 cin >> x >> y;

7 long long gcd = __gcd(x, y);

8 cout << (x / gcd) * (y / gcd);

9 return 0;

10}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(1)$.
• Thời gian: code chỉ có mỗi hàm __gcd là đáng kể, còn nhập dữ liệu, nhân, chia đều là $O(1)$. Hàm __gcd dùng thuật toán Euclid, độ phức tạp $O(\log(\min(x, y)))$. Với $\min(x, y) \le 10^9$ thì số bước chỉ cỡ vài chục (trường hợp tệ nhất của Euclid là 2 số Fibonacci liên tiếp, như nút "Fibonacci liên tiếp" ở khung chạy tay), gần như là $O(1)$ luôn, rất tối ưu. Nên yên tâm bài này không thể bị TLE với cách làm này.

Không gian$O(1)$

Thời gian$O(\log(\min(x, y)))$

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output ví dụ của đề, và đã được so với một chương trình vét cạn độc lập (thử mọi cạnh hình vuông, lấy số lượng ít nhất) trên 400 bộ test ngẫu nhiên ($x \le 300$, $y \le 1500$, có cả bộ $y$ là bội của $x$) – khớp hết. Với $x = 999\,999\,937$, $y = 999\,999\,929$: bản C++ cách 2 chạy tức thì và in đúng $999\,999\,866\,000\,004\,473$ (không bị tràn số), còn cách 1 mất khoảng 3,3 giây.

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 😇