Xếp Khối Gỗ (Thi thử HSG9 SQRTOJ 2025 – Ngày 1 Bài 1)
Đề bài
XẾP KHỐI GỖ (7 điểm)
Quang có $n$ khối gỗ màu đỏ, mỗi khối có kích thước $1 \times 1 \times a$ (cm) và $m$ khối gỗ màu xanh, mỗi khối có kích thước $1 \times 1 \times b$ (cm). Quang xếp các khối gỗ thành một cột thẳng đứng có đáy là một hình vuông kích thước $1 \times 1$ (cm) và tiến hành đo chiều cao của cột gỗ, ký hiệu là $h$. Quang thử tất cả các cách xếp khác nhau và ghi lại các giá trị $h$ thu được.
Yêu cầu: Vì số lượng giá trị $h$ mà Quang ghi lại được là quá lớn, bạn hãy giúp Quang đếm xem có bao nhiêu giá trị $h$ khác nhau mà Quang đã tạo ra.
Dữ liệu vào: Nhập từ file WOOD.inp:
- Một dòng duy nhất gồm bốn số nguyên dương $a, b, n, m$ $(1 \le a, b, n, m \le 10^9)$.
Dữ liệu ra: Ghi ra file WOOD.out:
- Một dòng duy nhất là số giá trị $h$ khác nhau mà Quang tạo được. Vì số giá trị có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho $10^9 + 7$.
Ràng buộc bổ sung:
- $20\%$ số điểm có $n = m = 1$.
- $20\%$ số điểm khác có $a = b$.
- $10\%$ số điểm khác có $m = 1$.
- $10\%$ số điểm khác có $n, m \le 10$.
- $10\%$ số điểm khác có $n, m \le 1000$.
- $10\%$ số điểm khác có $b = 1$.
- $10\%$ số điểm khác có $m \le 10^5$.
- $10\%$ số điểm còn lại không có giới hạn gì thêm.
Lưu ý: đề gốc đọc/ghi file WOOD.inp / WOOD.out; nộp trên web thì đọc từ bàn phím, in ra màn hình (code bên dưới có đoạn if(fopen(...)) nên nộp kiểu nào cũng chạy đúng).
2 3 1 253 3 1 12Giải thích (theo đề):
- Ví dụ 1: các giá trị $h$ có thể tạo được là $2, 3, 5, 6, 8$. Để tạo được giá trị $h = 6$, có thể chồng hai khối gỗ màu xanh lên nhau; để tạo được giá trị $h = 5$, có thể chồng một khối gỗ màu đỏ lên một khối gỗ màu xanh.
- Ví dụ 2: có thể tạo ra được 2 giá trị $h = 3$ và $h = 6$.
Lời mở đầu
Đây là bài 1 ngày thi thứ nhất trong kỳ thi thử HSG lớp 9 năm 2025 của câu lạc bộ SQRT. Đề có tới 8 mức ràng buộc nhỏ, nên mình viết lời giải đi lên theo từng subtask để các bạn thấy cách "ăn điểm" từng phần rồi mới tới lời giải trọn vẹn nha. Hy vọng mang đến được giá trị cho các bạn 😇.
Mình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Nếu Quang dùng $x$ khối đỏ ($0 \le x \le n$) và $y$ khối xanh ($0 \le y \le m$) thì chiều cao cột là $h = a \cdot x + b \cdot y$ – thứ tự xếp không quan trọng. Cột phải có ít nhất 1 khối, nên ta bỏ trường hợp $x = y = 0$. Ở ví dụ 1: $a = 2$, $b = 3$, $n = 1$, $m = 2$:
Còn ví dụ 2 có $a = b = 3$, $n = m = 1$: các cách chọn cho $h = 3$ (1 đỏ), $h = 3$ (1 xanh), $h = 6$ (1 đỏ + 1 xanh). Hai cách đầu trùng chiều cao nên chỉ còn 2 giá trị. Cái khó của bài chính là đếm sao cho các chiều cao trùng nhau chỉ được tính 1 lần.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1n = m = 1 – O(1)
Nếu $n = m = 1$ thì mỗi màu chỉ có 1 khối, các chiều cao có thể là $a$ (1 khối đỏ), $b$ (1 khối xanh) và $a + b$ (cả hai). Ta có hai trường hợp sau:
- $a \ne b$: 3 trường hợp $a$, $b$, $a + b$. Ta nhận thấy rằng $a + b \gt a$ và $a + b \gt b$ nên không có trường hợp số này xuất hiện quá 1 lần. Xét hai số còn lại, $a \ne b$ nên hai số này cũng khác nhau. Do đó kết quả trong trường hợp này là 3.
- $a = b$: 3 trường hợp $a$, $a$, $2a$. Ta nhận thấy rằng $2a \gt a$ nên không có trường hợp số này xuất hiện quá 1 lần. Xét hai số còn lại, $a = b$ nên hai số này bị trùng nhau. Do đó kết quả trong trường hợp này là 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 a, b, n, m;
signed main(){
if(fopen("WOOD.inp", "r")){
freopen("WOOD.inp", "r", stdin);
freopen("WOOD.out", "w", stdout);
}
cin >> a >> b >> n >> m;
if (a == b) cout << 2 << endl;
else cout << 3 << endl;
}import sys, os
if os.path.exists('WOOD.inp'):
sys.stdin = open('WOOD.inp')
sys.stdout = open('WOOD.out', 'w')
a, b, n, m = map(int, sys.stdin.read().split())
if a == b:
print(2)
else:
print(3)Các bạn bấm Tiếp để chạy tay. Thử luôn nút "Ví dụ 1 (n, m ≠ 1)" để thấy code này in sai khi không còn $n = m = 1$ nữa nha:
Subtask 2a = b – O(1)
Nếu $a = b$, ta có $h = a \cdot x + b \cdot y = a \cdot (x + y)$.
Khác biệt duy nhất giữa các số $h$ sẽ là phần $(x + y)$. Do đó, ta sẽ đếm thử với $0 \le x \le n$, $0 \le y \le m$ thì có bao nhiêu giá trị $(x + y)$ phân biệt. Dễ thấy $x + y$ nhận được mọi giá trị nguyên từ $0$ đến $n + m$ (cứ tăng $x$ lên tới $n$ rồi tăng $y$), nên có $n + m + 1$ giá trị. Trừ đi trường hợp tổng bằng $0$ (không có khối nào) thì kết quả sẽ là:
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 a, b, n, m;
int MOD = 1e9 + 7;
signed main(){
if(fopen("WOOD.inp", "r")){
freopen("WOOD.inp", "r", stdin);
freopen("WOOD.out", "w", stdout);
}
cin >> a >> b >> n >> m;
if (a == b) cout << (n + m) % MOD << endl;
}import sys, os
MOD = 10**9 + 7
if os.path.exists('WOOD.inp'):
sys.stdin = open('WOOD.inp')
sys.stdout = open('WOOD.out', 'w')
a, b, n, m = map(int, sys.stdin.read().split())
if a == b:
print((n + m) % MOD)Subtask 4 + 5Duyệt mọi cặp (x, y) và lưu vào map – O(n·m·log(n·m))
Vì $n, m$ khá nhỏ ($\le 1000$) nên ta sẽ xét tất cả giá trị $h = a \cdot x + b \cdot y$ của các cặp $(x, y)$ với $0 \le x \le n$ và $0 \le y \le m$. Ta có thể sử dụng map để lưu các giá trị $h$ (map tự bỏ trùng) và lấy size của map này. Lưu ý nhớ trừ đi 1 để tránh trường hợp $h = 0$ (khi $x = y = 0$).
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 MOD = 1e9 + 7;
int a, b, n, m;
signed main(){
if(fopen("WOOD.inp", "r")){
freopen("WOOD.inp", "r", stdin);
freopen("WOOD.out", "w", stdout);
}
cin >> a >> b >> n >> m;
map<int, int> cnt;
for (int i = 0; i <= n; i++){
for (int j = 0; j <= m; j++){
cnt[a * i + j * b] = 1;
}
}
cout << cnt.size() - 1 << endl;
}import sys, os
if os.path.exists('WOOD.inp'):
sys.stdin = open('WOOD.inp')
sys.stdout = open('WOOD.out', 'w')
a, b, n, m = map(int, sys.stdin.read().split())
cnt = set()
for i in range(n + 1):
for j in range(m + 1):
cnt.add(a * i + j * b)
print(len(cnt) - 1)Bản Python dùng set thay cho map vì ta chỉ cần biết giá trị nào đã xuất hiện. Các bạn chạy tay để xem map cnt lớn dần và các giá trị trùng bị "nhập chung" như thế nào:
Đánh giá độ phức tạp của cách làm này:
- Không gian: map chứa tối đa $(n + 1)(m + 1)$ giá trị: $O(n \cdot m)$.
- Thời gian: có $(n + 1)(m + 1)$ lần thêm vào map, mỗi lần $O(\log(n \cdot m))$: tổng $O(n \cdot m \cdot \log(n \cdot m))$. Với $n = m = 1000$ là khoảng $10^6$ lần thêm.
Subtask 3 + 6 + 7 + 8Đếm bằng BCNN – O(log(min(a, b)))
Ta sẽ có hướng như sau: đối với mỗi $x$ (số khối đỏ), ta sẽ tìm số lượng số $y$ sao cho thu được $h = a \cdot x + b \cdot y$ mà không thể thu được từ một cặp $(u, v)$ có $u \lt x$. Nói cách khác, mỗi chiều cao $h$ ta chỉ đếm đúng một lần tại cách xếp dùng ít khối đỏ nhất.
Để tính toán, ta sẽ đảo ngược lại bằng cách xem xét thử với mỗi cặp $(x, y)$ thì có bao nhiêu cặp $(u, v)$ với $u \lt x$ mà $a \cdot u + b \cdot v = a \cdot x + b \cdot y$. Đẳng thức này tương đương:
Vế trái chia hết cho $a$, vế phải chia hết cho $b$, nên giá trị chung này là một bội chung của $a$ và $b$. Để đạt được điều này, ta nhận thấy $x - u$ và $v - y$ nên nhỏ nhất có thể (vẫn phải lớn hơn $0$) ⇒ $a \cdot (x - u) = b \cdot (v - y) = \text{BCNN}(a, b)$.
Do đó $(x - u)$ và $(v - y)$ nhỏ nhất là một hằng số. Ta đặt:
Bớt đi $dis\_$ khối đỏ và thêm $dis$ khối xanh thì chiều cao không đổi (vì $a \cdot dis\_ = b \cdot dis = L$).
Khi này $u = x - dis\_$ và $v = y + dis$ phải thoả mãn cả hai điều kiện sau:
- $u \ge 0$: nếu $x \lt dis\_$ thì $u \lt 0$ và điều này không thoả mãn điều kiện.
- $v \le m$: nếu $y \gt m - dis$ thì $v \gt m$ và điều này không thoả mãn điều kiện.
Từ trên, về lại bài toán gốc: với mỗi $x$, những $y$ cho ra chiều cao "mới" (không thu được từ $u \lt x$) là những $y$ làm một trong hai điều kiện trên không được thoả mãn. Vậy kết quả chia làm hai trường hợp:
- Nếu $x \lt dis\_$: mọi số $y$ đều thoả mãn (đã có một điều kiện bị vi phạm nên không cần quan tâm đến $y$). Số lượng $y$ cho mỗi $x$ như vậy là $m + 1$, và có $\min(n + 1, dis\_)$ giá trị $x$ như vậy.
- Nếu $x \ge dis\_$: cần $y \gt m - dis$, tức $y$ thuộc $[\max(0, m - dis + 1), m]$, dễ thấy số lượng $y$ như vậy cho mỗi $x$ là $\min(m + 1, dis)$. Có $(n + 1) - \min(n + 1, dis\_)$ giá trị $x$ như vậy.
Lưu ý: kết quả tổng quát sẽ trừ đi $1$ để tránh trường hợp $h = 0$ (cặp $(0, 0)$ luôn được đếm ở trường hợp đầu).
Kiểm tra với ví dụ 1: $a = 2$, $b = 3$ ⇒ $L = 6$, $dis\_ = 3$, $dis = 2$. Vì $n + 1 = 2 \lt 3$ nên mọi $x$ đều thuộc trường hợp đầu: $2 \cdot 3 - 1 = 5$ ✔. Ví dụ 2: $a = b = 3$ ⇒ $L = 3$, $dis\_ = dis = 1$: $1 \cdot 2 + 1 \cdot 1 - 1 = 2$ ✔.
Minh hoạ: ô nào được đếm?
Khung dưới vẽ bảng chiều cao $h = a \cdot x + b \cdot y$: hàng là $x$, cột là $y$. Bấm Tiếp để xét từng hàng $x$: ô xanh là chiều cao mới được đếm, ô xám là chiều cao đã có ở hàng $x - dis\_$ (ghi rõ trùng với ô nào). Thử nút "a = 4, b = 6" để thấy rõ các ô trùng nha:
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 a, b, n, m;
long long MOD = 1e9 + 7;
signed main(){
if(fopen("WOOD.inp", "r")){
freopen("WOOD.inp", "r", stdin);
freopen("WOOD.out", "w", stdout);
}
cin >> a >> b >> n >> m;
int need_ = a * b / __gcd(a, b);
int dis = need_ / b;
int dis_ = need_ / a;
long long res = 0;
res += min(n + 1, dis_) * (m + 1);
res %= MOD;
res += (n + 1 - min(n + 1, dis_)) * min(m + 1, dis);
res %= MOD;
cout << (res - 1 + MOD) % MOD;
}import sys, os
from math import gcd
MOD = 10**9 + 7
if os.path.exists('WOOD.inp'):
sys.stdin = open('WOOD.inp')
sys.stdout = open('WOOD.out', 'w')
a, b, n, m = map(int, sys.stdin.read().split())
need_ = a * b // gcd(a, b)
dis = need_ // b
dis_ = need_ // a
res = 0
res += min(n + 1, dis_) * (m + 1)
res %= MOD
res += (n + 1 - min(n + 1, dis_)) * min(m + 1, dis)
res %= MOD
print((res - 1 + MOD) % MOD)Giải thích 1 số chỗ trong code ở trên:
need_ = a * b / __gcd(a, b)chính là $L = \text{BCNN}(a, b)$. Vì $a, b \le 10^9$ nên $a \cdot b \le 10^{18}$, vẫn nằm tronglong long(tối đa khoảng $9.2 \cdot 10^{18}$) nên nhân trước chia sau vẫn an toàn.min(n + 1, dis_) * (m + 1)và(n + 1 - min(n + 1, dis_)) * min(m + 1, dis)mỗi tích tối đa cỡ $10^{18}$, nên mình lấy dưres %= MODngay sau mỗi lần cộng để không bị tràn.(res - 1 + MOD) % MOD: trừ 1 cho trường hợp $h = 0$; cộng thêmMODphòng khiressau khi lấy dư bằng $0$ thì không bị ra số âm.
Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ vài biến: $O(1)$.
- Thời gian: tính ƯCLN bằng thuật toán Euclid tốn $O(\log(\min(a, b)))$, phần còn lại là vài phép tính: tổng $O(\log(\min(a, b)))$ – chạy tức thì với mọi $a, b, n, m \le 10^9$.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét