Đếm số bộ 3
Đề bài
Cho hai số nguyên $T$ và $S$, hãy đếm số lượng bộ ba số nguyên không âm $(a, b, c)$ sao cho:
- $a + b + c \le T$
- $a \cdot b \cdot c \le S$
- $0 \le a, b, c$
Đầu vào
- Gồm hai số nguyên $T$ và $S$.
- $0 \le T \le 8000$
- $0 \le S \le 10^7$
Đầu ra
- Dòng duy nhất chứa kết quả của bài toán.
Note
- 70% test: $0 \le T \le 700$
- 20% test: $0 \le T \le 1200$
- 10% test: $0 \le T \le 8000$
1 042 51010 1021330 1002471Giải thích Example 1: bộ ba $(a, b, c)$ thỏa mãn điều kiện là (0,0,0); (0,1,0); (1,0,0) và (0,0,1), do đó kết quả là 4.
Giải thích Example 2: bộ ba $(a, b, c)$ thỏa mãn điều kiện là (0,0,0) (0,0,1) (0,0,2) (0,1,0) (0,1,1) (0,2,0) (1,0,0) (1,0,1) (1,1,0) (2,0,0).
Lời mở đầu
Bài này 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 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesBài này đưa ra thời gian chạy giới hạn là 0.3 giây, nên tổng số lần lặp ta chỉ nên tầm từ 10 triệu đến 30 triệu thôi.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
50%Cách 1: vét cạn 3 vòng lặp – O(T³)
Một cách giải quyết đơn giản nhất cho bài này là ta xét hết tất cả các bộ 3 số có thể, với mỗi số sẽ chạy từ 0 đến $T$, rồi khi có bộ 3 số sẽ kiểm tra bộ nào thỏa mãn a + b + c <= T và a * b * c <= S thì tăng res++, với res là biến lưu đáp án. Sau cùng in ra res là kết quả.
Xem code cách 1
#include <iostream>
using namespace std;
int main(){
long long t, s, res = 0;
cin >> t >> s;
for(long long a = 0; a <= t; ++a){
for(long long b = 0; b <= t; ++b){
for(long long c = 0; c <= t; ++c){
if(a + b + c <= t && a * b * c <= s){
res++;
}
}
}
}
cout << res;
return 0;
}t, s = map(int, input().split())
res = 0
for a in range(t + 1):
for b in range(t + 1):
for c in range(t + 1):
if a + b + c <= t and a * b * c <= s:
res += 1
print(res)Giải thích một số chỗ trong code ở trên: như các bạn thấy toàn bộ các biến trong bài này mình đều để kiểu long long (số nguyên 8 byte với phạm vi lưu trữ hơn 9 tỷ tỷ) hết. Lý do là nếu theo thói quen các bạn hay xài kiểu int (số nguyên 4 byte với phạm vi hơn 2 tỷ), mà theo đề $T$ có thể tối đa là 8000, thì $a, b, c$ tối đa cũng là 8000, và $8000 \cdot 8000 \cdot 8000$ $= 512\,000\,000\,000$ (512 tỷ), đã vượt quá phạm vi của int rồi các bạn nha.
long long mul = a * b * c; thì vẫn sẽ bị tràn số nếu $a, b, c$ để kiểu int. Bởi vì nguyên tắc nó sẽ nhân với nhau ra kết quả lưu vào các vùng nhớ tạm trước rồi sau cùng mới gán qua biến mul. Và các vùng nhớ tạm đó sẽ có kiểu dữ liệu của các biến thành phần, nên nếu $a, b, c$ đang là kiểu int thì vùng nhớ tạm cũng có kiểu int, như thế đã bị tràn số trước khi được gán qua biến mul kiểu long long rồi. Các bạn lưu ý chỗ này nhé.Đánh giá độ phức tạp: không gian $O(1)$; thời gian $O(T^3)$ (T lũy thừa 3, ký hiệu ^ ở đây là lũy thừa chứ không phải phép xor bit nha các bạn). Trong trường hợp xấu nhất $T = 8000$ thì $8000^3 = 512$ tỷ, gấp sơ sơ hơn 15 360 lần ngưỡng 0.3 giây (10 → 30 triệu) ⇒ phải cỡ 4 tiếng rưỡi đồng hồ mới chạy ra kết quả, trong khi đề chỉ cho tối đa 0.3 giây, nên cách này TLE là cái chắc rồi ahihi.
Thực tế code C++ nộp lên sẽ được 50/100, còn code Python được 40/100 (do Python chạy chậm hơn C++). Subtask 1 (70% test đầu có $T \le 700$): $700^3 = 343$ triệu, nên trường hợp xấu nhất cũng phải chạy gần 4 giây, không ăn trọn được 70% mà chỉ được 50% thôi.
97%Cách 2: dừng vòng lặp sớm
Code ở trên ta có thể tối ưu lại 1 chút để tốt hơn như sau: giả sử $T = 700$ và $a$ đã xét đến 700 luôn rồi, thì có phải mọi trường hợp từ $b = 1$ trở đi ta không cần phải xét nữa đúng không các bạn? Vì lúc này $a + b$ đã thành 701, không còn thỏa $\le T$ nữa, nên coi như ta không cần xét các trường hợp $b$ từ 1 đến 700, cũng như với mỗi $b$ đó các trường hợp $c$ từ 0 đến 700 bên trong, vì có xét thì sau cùng tổng $a + b + c$ cũng không thỏa $\le T$, thì tại sao phải xét làm gì đúng không? Vậy ta có code cải tiến như sau:
Xem code cách 2
#include <iostream>
using namespace std;
int main(){
long long t, s, res = 0;
cin >> t >> s;
for(long long a = 0; a <= t; ++a){
for(long long b = 0; a + b <= t; ++b){
for(long long c = 0; a + b + c <= t && a * b * c <= s; ++c){
res++;
}
}
}
cout << res;
return 0;
}t, s = map(int, input().split())
res = 0
for a in range(t + 1):
for b in range(t - a + 1):
c = 0
while a + b + c <= t and a * b * c <= s:
res += 1
c += 1
print(res)Như các bạn thấy, ở điều kiện vòng lặp for b ta sẽ xét điều kiện để lặp tiếp là khi a + b <= T. Tương tự vòng lặp for c điều kiện để lặp tiếp là khi a + b + c <= T && a * b * c <= S. Vòng lặp nào không thỏa thì dừng không làm nữa.
for b thì sẽ sai nha các bạn. Ta chỉ để điều kiện đó ở vòng lặp for c thôi, vì lúc này $c$ đang tăng, nếu tại 1 giá trị $c$ mà tích lớn hơn $S$ thì càng tăng $c$ lên tích sẽ càng lớn hơn, nên kết thúc luôn là được rồi.Code C++ ở trên được 97/100 còn Python thì 88/100 (do Python chạy chậm hơn C++). Vẫn còn bị TLE nhưng đã ăn được nhiều test hơn. Nếu ở vòng lặp for c ta không để thêm điều kiện a * b * c <= s mà chỉ để a + b + c <= t, rồi bên trong xét if(a * b * c <= s) res++;, thì nộp thử sẽ chỉ được 90/100. Tại vì nếu để như thế thì dù bắt đầu gặp những $c$ không thỏa, nó vẫn cứ lặp đến hết; rõ ràng dừng sớm sẽ tốt hơn đúng không các bạn.
100%Cách 3: tính thẳng số giá trị c – O(T²)
Ta có thể tối ưu thêm nữa: bản chất không cần 3 vòng lặp lồng nhau mà có thể rút xuống chỉ còn 2 vòng lặp lồng nhau thôi nha các bạn. Một chút toán học thôi, đề bài cho ta:
a · b · c ≤ s ⇔ c ≤ s / (a · b)
Vậy ý tưởng bây giờ là ta sẽ xét các cặp $a$, $b$ rồi tính tổng và tích của chúng, sau đó thế vào để ra 2 ngưỡng giới hạn của $c$, rồi chọn theo ngưỡng nhỏ nhất để thỏa cả 2. Ví dụ $t = 10$, $s = 10$, đang xét cặp $a = 1$, $b = 3$: thế vào ta có $c \le 10 - (1 + 3) = 6$ và $c \le 10 / (1 \cdot 3) = 3$ (phép chia lấy phần nguyên). Kết hợp $c \le 6$ và $c \le 3$ thì ta có $c \le 3$ sẽ thỏa cả 2. Nghĩa là có 4 giá trị $c$ thỏa mãn là 0, 1, 2, 3, ứng với các bộ (1,3,0), (1,3,1), (1,3,2), (1,3,3). Vậy mỗi cặp $(a, b)$ đóng góp Min + 1 bộ vào đáp án.
Một vài cặp khác với $t = 10$, $s = 10$ cho các bạn dễ hình dung:
| Cặp (a, b) | c ≤ t − (a + b) | c ≤ s / (a · b) | Kết hợp | Số giá trị c |
|---|---|---|---|---|
| (0, 0) | 10 − 0 = 10 | bỏ qua (a·b = 0) | c ≤ 10 | 11 |
| (0, 5) | 10 − 5 = 5 | bỏ qua (a·b = 0) | c ≤ 5 | 6 |
| (1, 3) | 10 − 4 = 6 | 10 / 3 = 3 | c ≤ 3 | 4 |
| (2, 2) | 10 − 4 = 6 | 10 / 4 = 2 | c ≤ 2 | 3 |
| (3, 4) | 10 − 7 = 3 | 10 / 12 = 0 | c ≤ 0 | 1 |
| (5, 5) | 10 − 10 = 0 | 10 / 25 = 0 | c ≤ 0 | 1 |
s / (a * b) chỉ thực hiện được khi $a \cdot b$ khác 0 nha, nếu không máy tính sẽ báo lỗi chia cho 0 đấy. Nếu $a \cdot b = 0$ thì tích $a \cdot b \cdot c$ luôn bằng 0, ta bỏ qua điều kiện $c \le s / (a \cdot b)$ và chỉ xét $c \le t - (a + b)$ thôi.Em nhập $T$, $S$ rồi bấm Tiếp để xem từng cặp $(a, b)$ được tính ra bao nhiêu giá trị $c$, cộng dồn lại thành đáp án:
Vậy theo ý tưởng này ta có code như sau:
#include <iostream>
using namespace std;
int main(){
long long t, s, res = 0;
cin >> t >> s;
for(long long a = 0; a <= t; ++a){
for(long long b = 0; a + b <= t; ++b){
long long x = a + b;
long long c = t - x;
if(c >= 0){
long long y = a * b;
long long Min = c;
if(y != 0){
Min = min(Min, s / y);
}
res += Min + 1;
}
}
}
cout << res;
return 0;
}t, s = map(int, input().split())
res = 0
for a in range(t + 1):
for b in range(t - a + 1):
x = a + b
c = t - x
if c >= 0:
y = a * b
Min = c
if y != 0:
Min = min(Min, s // y)
res += Min + 1
print(res)Độ phức tạp thời gian của cách làm này giờ đây chỉ là $O(T^2)$ thôi nha các bạn: với $T = 8000$ thì chỉ khoảng 32 triệu cặp $(a, b)$. Code C++ sẽ full 100/100, còn code Python sẽ được 90/100 (do Python chạy chậm hơn C++).
Mình đã kiểm tra cả 3 cách với 200 bộ $(T, S)$ ngẫu nhiên, đều ra cùng kết quả và khớp cả 4 ví dụ. Với $T = 8000$, $S = 10^7$ thì bản C++ cách 3 chạy khoảng 0.11 giây, còn bản Python mất khoảng 14 giây vì phải lặp 32 triệu lần. Nếu hệ thống chấm có trình dịch PyPy 3 thì các bạn dùng Python nên chọn PyPy, nó chạy các vòng lặp kiểu này nhanh hơn nhiều lần.