Cắt Hình (HSG9 Hà Nội 2025 – Bài 1)

Nguồn: Đề thi HSG lớp 9 Hà Nội 2025 (CLUE OJ) Độ khó: Dễ Toán học Công thức Chia lấy dư

Đề bài

Bài I. Cắt hình (5,0 điểm)

Cho một tờ giấy hình chữ nhật kích thước $M\,(cm) \times N\,(cm)$ và một số tự nhiên $K$.

Yêu cầu: Nếu cắt những hình vuông có kích thước $K\,(cm) \times K\,(cm)$ từ tờ giấy này thì diện tích còn lại nhỏ nhất là bao nhiêu $cm^2$?

Dữ liệu vào từ file văn bản CATHINH.INP: Gồm ba số tự nhiên $M, N, K$ lần lượt mỗi số trên một dòng $(1 \le M, N, K \le 10^9)$.

Kết quả ghi ra file văn bản CATHINH.OUT: Một số nguyên duy nhất là kết quả của bài toán.

Lưu ý: đề gốc đọc/ghi file CATHINH.INP / CATHINH.OUT; trên CLUE OJ thì đọc từ bàn phím, in ra màn hình (giới hạn trên CLUE: 1 giây, 1 GB).

CATHINH.INP

8
7
3

CATHINH.OUT

20

Giải thích

Hình giải thích của đề (vẽ lại): tờ giấy 8 × 7 cắt được 4 hình vuông 3 × 3 (viền đậm), phần màu đỏ còn lại có diện tích 20.

Lời mở đầu

Đây là bài 1 – bài "khởi động" trong đề thi học sinh giỏi Tin học lớp 9 thành phố Hà Nội năm 2025. Code chỉ có vài dòng, nhưng muốn ăn trọn điểm thì phải để ý 2 thứ: tìm ra công thức (vì $M, N$ tới $10^9$, không thể "đặt thử" từng hình vuông) và tràn số (vì $M \times N$ có thể tới $10^{18}$). Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

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

Mình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Tờ giấy có $M = 8$ hàng ô và $N = 7$ cột ô (mỗi ô $1\,cm \times 1\,cm$), diện tích $8 \times 7 = 56\,cm^2$. Ta cắt các hình vuông $3 \times 3$:

• Theo chiều dọc (dài $8$) xếp được $2$ hình vuông, vì $2 \times 3 = 6 \le 8$ nhưng $3 \times 3 = 9 \gt 8$.
• Theo chiều ngang (dài $7$) xếp được $2$ hình vuông, vì $2 \times 3 = 6 \le 7$ nhưng $9 \gt 7$.

Vậy cắt được $2 \times 2 = 4$ hình vuông, tổng diện tích $4 \times 9 = 36\,cm^2$. Diện tích còn lại là $56 - 36 = 20\,cm^2$ – đúng như đáp án.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Đếm bằng vòng lặp · O(M/K + N/K)Cách 2Công thức chia lấy dư · O(1) · 100%

Cách 1Đếm số hình vuông dọc mỗi cạnh bằng vòng lặp – O(M/K + N/K)

Ta sẽ xem xét thử xem là viền trên (cạnh dài $N$) của hình chữ nhật thì có thể giáp với tối đa bao nhiêu hình vuông, và viền trái (cạnh dài $M$) có thể giáp với tối đa bao nhiêu hình vuông. Sau đó ta nhận thấy rằng mỗi lần phủ một hình vuông giáp với viền trên, ta có thể phủ liền dưới nó tiếp tục các hình vuông sao cho không vượt quá viền dưới. Do đó số hình vuông cắt được chính là hai số trên nhân với nhau.

Cách "ngây thơ" nhất để đếm số hình vuông dọc theo cạnh $M$ là đặt từng cái một: đang có $x$ hình vuông thì thử đặt thêm cái thứ $x + 1$, nếu $(x + 1) \cdot K \le M$ (vẫn còn nằm trong tờ giấy) thì đặt được, tăng $x$ lên. Làm tương tự với cạnh $N$ được $y$. Đáp án là:

Diện tích còn lại

$S = M \cdot N - x \cdot y \cdot K^2$

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

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, k;
signed main(){
    if(fopen("cathinh.inp", "r")){
        freopen("cathinh.inp", "r", stdin);
        freopen("cathinh.out", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n >> k;
    int x = 0, y = 0;
    while ((x + 1) * k <= m) x++; // đặt thêm 1 hình vuông dọc cạnh M
    while ((y + 1) * k <= n) y++; // đặt thêm 1 hình vuông dọc cạnh N
    cout << m * n - x * y * k * k << endl;
}

import sys
m, n, k = map(int, sys.stdin.read().split())
x = 0
y = 0
while (x + 1) * k <= m:  # đặt thêm 1 hình vuông dọc cạnh M
    x += 1
while (y + 1) * k <= n:  # đặt thêm 1 hình vuông dọc cạnh N
    y += 1
print(m * n - x * y * k * k)

Trong khung chạy tay, phần "Dữ liệu" vẽ luôn tờ giấy (khi $M, N \le 16$): ô xanh/tím là các hình vuông đã đặt, ô đỏ là phần thừa.

C++▶ Chạy tay từng dòng codeCách 1: đặt từng hình vuông dọc cạnh M (đếm x) và dọc cạnh N (đếm y), đáp án M*N - x*y*K*K.

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

Dữ liệu mẫu:

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

2#define int long long

3using namespace std;

4int n, m, k;

5signed main(){

6 if(fopen("cathinh.inp", "r")){

7 freopen("cathinh.inp", "r", stdin);

8 freopen("cathinh.out", "w", stdout);

9 }

10 ios::sync_with_stdio(0);

11 cin.tie(0);

12 cin >> m >> n >> k;

13 int x = 0, y = 0;

14 while ((x + 1) * k <= m) x++; // đặt thêm 1 hình vuông dọc cạnh M

15 while ((y + 1) * k <= n) y++; // đặt thêm 1 hình vuông dọc cạnh N

16 cout << m * n - x * y * k * k << endl;

17}

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: vòng while thứ nhất chạy $\lfloor M/K \rfloor$ lần, vòng thứ hai chạy $\lfloor N/K \rfloor$ lần, nên là $O(M/K + N/K)$.

Không gian$O(1)$

Thời gian$O(M/K + N/K)$

Dễ TLE khi K nhỏ

Với $K = 1$ và $M = N = 10^9$ thì 2 vòng lặp chạy tổng cộng $2 \cdot 10^9$ lần. Mình đo thử: bản C++ mất khoảng 1.1 giây (sát nút giới hạn 1 giây), còn bản Python chạy hơn 60 giây vẫn chưa xong. Nên ta cần một công thức tính $x, y$ ngay lập tức.

Cách 2Dùng phép chia lấy nguyên / chia lấy dư – O(1)

Để ý vòng lặp ở cách 1 đang làm gì: nó tìm số $x$ lớn nhất sao cho $x \cdot K \le M$. Đó chính là phần nguyên của phép chia $M$ cho $K$:

Số hình vuông dọc mỗi cạnh

Viền trái (dài $M$) giáp tối đa $x = \left\lfloor \dfrac{M}{K} \right\rfloor$ hình vuông, viền trên (dài $N$) giáp tối đa $y = \left\lfloor \dfrac{N}{K} \right\rfloor$ hình vuông.
Đáp án bài toán: $S = M \cdot N - \left\lfloor \dfrac{M}{K} \right\rfloor K \cdot \left\lfloor \dfrac{N}{K} \right\rfloor K$.

Trong code mình không tính $\lfloor M/K \rfloor$ rồi nhân $K$, mà tính thẳng độ dài phần được phủ trên mỗi cạnh: phần thừa ra ở cạnh $M$ chính là số dư $M \bmod K$, nên phần được phủ dài $M - (M \bmod K)$ (bằng đúng $\lfloor M/K \rfloor \cdot K$). Tương tự cạnh $N$. Phần được phủ là một hình chữ nhật $(M - M \bmod K) \times (N - N \bmod K)$, lấy diện tích tờ giấy trừ đi là xong.

Ví dụ đề: $M = 8$, $K = 3$: $8 \bmod 3 = 2$, phần phủ dài $8 - 2 = 6$. $N = 7$: $7 \bmod 3 = 1$, phần phủ dài $7 - 1 = 6$. Đáp án $56 - 6 \cdot 6 = 20$.

Vì sao không cắt được nhiều hơn?

Bạn nào tò mò có thể tự thuyết phục mình bằng lập luận sau (cắt các hình vuông có cạnh song song với cạnh tờ giấy). Đặt tờ giấy trong hệ trục toạ độ: $0 \le$ hoành độ $\le N$, $0 \le$ tung độ $\le M$. Đánh dấu các điểm $(iK, jK)$ với $1 \le i \le \lfloor N/K \rfloor$, $1 \le j \le \lfloor M/K \rfloor$ – có đúng $\lfloor N/K \rfloor \cdot \lfloor M/K \rfloor$ điểm. Một hình vuông cạnh $K$ chiếm đoạn hoành độ $(a, a + K]$ dài đúng $K$ nên chứa đúng một bội của $K$ (và bội đó nằm trong $[K, N]$); tung độ cũng vậy. Tức là mỗi hình vuông "chiếm" đúng một điểm đánh dấu, các hình vuông không chồng lên nhau thì chiếm các điểm khác nhau. Vậy số hình vuông không vượt quá số điểm đánh dấu – và cách xếp thẳng hàng ở trên đạt đúng con số đó.

Minh hoạ cách cắt

Các bạn nhập $M, N, K$ rồi bấm Tiếp để xem từng hình vuông được cắt ra (theo từng hàng, viền trên trước rồi phủ dần xuống dưới):

M N K

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>
#define int long long
using namespace std;
int n, m, k;
signed main(){
    if(fopen("cathinh.inp", "r")){
        freopen("cathinh.inp", "r", stdin);
        freopen("cathinh.out", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n >> k;
    int sus = m - (m % k);
    int sus_ = n - (n % k);
    cout << m * n - sus * sus_ << endl;
}

m, n, k = map(int, open(0).read().split())
sus = m - (m % k)
sus_ = n - (n % k)
print(m * n - sus * sus_)

C++▶ Chạy tay từng dòng codeCách 2: phần được phủ dài m - m % k và n - n % k, đáp án m*n - sus*sus_.

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

Dữ liệu mẫu:

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

2#define int long long

3using namespace std;

4int n, m, k;

5signed main(){

6 if(fopen("cathinh.inp", "r")){

7 freopen("cathinh.inp", "r", stdin);

8 freopen("cathinh.out", "w", stdout);

9 }

10 ios::sync_with_stdio(0);

11 cin.tie(0);

12 cin >> m >> n >> k;

13 int sus = m - (m % k);

14 int sus_ = n - (n % k);

15 cout << m * n - sus * sus_ << endl;

16}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong code ở trên:

1. #define int long long rồi viết signed main(): mọi biến int trong bài đều thành long long. Hàm main bắt buộc trả về kiểu int thật, nên phải viết signed main (signed chính là int).
2. if(fopen("cathinh.inp", "r")): nếu có file cathinh.inp (lúc thi chấm bằng file) thì mới chuyển sang đọc/ghi file; nộp trên CLUE OJ không có file này nên vẫn đọc bàn phím, in màn hình bình thường. Một code dùng được cho cả 2 kiểu chấm.

Nhớ dùng long long

$M \cdot N$ có thể tới $10^9 \cdot 10^9 = 10^{18}$, vượt xa giới hạn của int (khoảng $2.1 \cdot 10^9$). Kiểu long long chứa được tới khoảng $9.2 \cdot 10^{18}$ nên vừa đủ. Bạn nào khai báo int thì sẽ bị tràn số và sai ngay các test lớn.

Đánh giá độ phức tạp của cách làm này: chỉ có vài phép tính nên là $O(1)$ cả về thời gian lẫn bộ nhớ.

Không gian$O(1)$

Thời gian$O(1)$

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output ví dụ, và đã được so với một code vét cạn (thử mọi cách đặt các hình vuông lên lưới ô vuông, $M, N \le 7$) trên 300 bộ test ngẫu nhiên – khớp hết. Với $M = N = 10^9$, $K = 1$: cách 1 bản C++ chạy khoảng 1.1 giây, bản Python hơn 60 giây; cách 2 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 😇