Tặng Quà (QUA) (HSG 12 Nam Định 2021 – 2022)
Đề bài
Bài 1. (5 điểm) Tặng quà – file chương trình QUA.*, dữ liệu vào QUA.INP, kết quả QUA.OUT.
Trong một trận đấu bóng đá, người ta bán được $N$ vé $(N \lt 3 \cdot 10^5)$. Mỗi khán giả có một vé, trên vé ghi số nguyên dương. Người ta muốn tặng quà cho những người có vé thuộc dãy số hạnh phúc. Dãy số hạnh phúc là một dãy số chỉ bao gồm các số hoàn thiện.
(Số hoàn thiện được định nghĩa là một số mà nó có tổng các ước không kể nó bằng chính nó. VD: $6$ có 3 ước thỏa mãn là $1, 2, 3$ tổng các ước là $6$.)
Yêu cầu: Từ số vé bóng đá đã cho, em hãy tìm ra những người được tặng quà thỏa mãn yêu cầu trên.
Dữ liệu: Vào từ tệp văn bản QUA.INP gồm:
- Dòng đầu tiên là số nguyên $N$ là số lượng vé đã bán $(1 \le N \le 3 \cdot 10^5)$.
- Dòng tiếp theo ghi $N$ số nguyên dương $A_1, A_2, \ldots, A_N$ $(0 \lt A_i \lt 3 \cdot 10^5$, $i = 1, 2, \ldots, N)$. Mỗi số cách nhau một khoảng trắng (dấu cách).
Kết quả: Ghi ra file QUA.OUT gồm:
- Dòng đầu tiên là số lượng người được tặng quà. Nếu không có ai được tặng quà thì đưa ra số $0$.
- Dòng thứ hai là số vé được tặng quà theo thứ tự xuất hiện trong tệp dữ liệu vào, mỗi số cách nhau một dấu cách.
Thời gian làm bài cả đề: 150 phút (4 bài). Bài được viết bằng Pascal hoặc C++. (Code trong bài đọc/ghi chuẩn – bàn phím/màn hình; khi đi thi đọc ghi file thì các bạn thêm freopen nhé, không là 0 điểm đó.)
9
5 18 7 4 6 13 8 11 271
6Lời mở đầu
Bài này là bài đầu tiên (cũng là bài dễ nhất) trong đề thi học sinh giỏi Tin học lớp 12 của tỉnh Nam Định năm học 2021 – 2022 mà bạn học viên mình đi thi. Sẵn bạn nhờ giải đề thì mình chịu khó viết chi tiết ra luôn. 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é:
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Đề bài thì dông dài quá, chốt lại là bài này yêu cầu các bạn đếm và liệt kê các số hoàn thiện có trong dãy số. Số hoàn thiện là số mà tổng các ước số của nó (những số mà nó chia hết), không tính chính nó, cộng lại bằng đúng nó. Ví dụ $6$ có 4 ước là $1, 2, 3, 6$; bỏ ước $6$ ra thì $1 + 2 + 3 = 6$ ⇒ $6$ là số hoàn thiện. Cứ thế xét qua toàn bộ dãy, in ra số lượng số hoàn thiện, rồi in cụ thể từng số theo thứ tự xuất hiện từ trái qua phải.
Với ví dụ: dãy $5, 18, 7, 4, 6, 13, 8, 11, 27$ chỉ có đúng số $6$ là số hoàn thiện (thử số $18$: $1 + 2 + 3 + 6 + 9 = 21 \ne 18$) ⇒ in $1$ rồi in $6$.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Tính tổng ước trong O(√X) + mảng đánh dấu
Để làm được bài này, chắc chắn trước tiên phải có bước kiểm tra một số có là số hoàn thiện không, rồi gọi bước đó với từng số trong dãy, số nào thỏa thì đưa vào mảng kết quả. Sau cùng in số phần tử của mảng kết quả rồi in từng phần tử. Do đề bắt in số lượng trước rồi mới tới các số, nên ta buộc phải lưu lại kết quả; chứ nếu đề chỉ cần in các số thỏa mãn thì gặp số nào in số đó luôn, khỏi cần mảng.
Duyệt qua từng phần tử là bước không thể bỏ qua được (nó chính là bước đọc dữ liệu). Vậy tối ưu hay không là nằm ở bước kiểm tra số hoàn thiện: tính tổng các ước nhỏ hơn nó rồi so sánh. Có 3 cách liệt kê ước số với độ phức tạp tối ưu dần: duyệt $1..X$ là $O(X)$, duyệt $1..X/2$ là $O(X/2)$, và duyệt tới $\sqrt{X}$ là $O(\sqrt{X})$.
Duyệt ước tới √X
Với mỗi $j$ từ $1$ trong khi $j \cdot j \le X$: nếu $X$ chia hết cho $j$ thì ta có luôn 2 ước là $j$ và $X / j$, cộng cả hai vào tổng. Sau vòng lặp:
- Nếu $(j - 1) \cdot (j - 1) = X$ (tức $X$ là số chính phương, $j - 1 = \sqrt{X}$) thì ước $\sqrt{X}$ bị cộng trùng 2 lần ⇒ trừ đi $j - 1$ một lần. Ví dụ $X = 36$: xét $j = 6$ thì ước còn lại $36/6$ cũng là $6$.
- Trừ đi chính $X$, vì ngay lần đầu $j = 1$ thì ước còn lại $X / 1 = X$ đã bị cộng vào rồi.
Em nhập một số $X$ rồi bấm Tiếp để xem từng bước $j$ chạy tới $\sqrt{X}$, cặp ước nào được cộng vào tổng:
Ước lượng độ phức tạp
Nếu cứ thế gọi hàm kiểm tra cho từng số thì với $N$ tối đa $3 \cdot 10^5$ và mỗi giá trị $X$ cũng tối đa cỡ $3 \cdot 10^5$:
| Cách liệt kê ước | Độ phức tạp | Trường hợp xấu nhất | Kết luận |
|---|---|---|---|
| Duyệt $1..X$ | $O(N \cdot X)$ | $9 \cdot 10^{10}$ (90 tỷ) | TLE |
| Duyệt $1..X/2$ | $O(N \cdot X/2)$ | $4.5 \cdot 10^{10}$ (45 tỷ) | TLE |
| Duyệt tới $\sqrt{X}$ | $O(N \cdot \sqrt{X})$ | $3 \cdot 10^5 \cdot 548 \approx 1.6 \cdot 10^8$ | Hên xui |
Cách duyệt tới $\sqrt{X}$ đã tốt hơn hai cách trước rất nhiều, nhưng vẫn vượt ngưỡng $10^8$ gần gấp đôi. Theo quan điểm cá nhân mình, may mắn không gặp test xấu nhất thì vẫn ăn trọn điểm, còn xui thì chắc chỉ được tầm 90%.
Đã làm thì ta đều muốn làm theo cách tốt nhất đúng không các bạn? Trường hợp xấu nhất là khi $N = 3 \cdot 10^5$ và số nào cũng chạm mức lớn nhất. Mà chờ đã, các bạn có thấy điều gì chứ? 🤔 Nếu các giá trị trong mảng giống nhau như vậy thì việc gì phải chạy vòng lặp xét lại? Chỉ cần làm lần đầu tiên, các lần sau lấy kết quả đã kiểm tra ra dùng thôi.
check có $3 \cdot 10^5$ phần tử, ban đầu tất cả là $-1$ (chưa xét). Gặp $X$:
check[X] == -1: đi kiểm tra $X$ trong $O(\sqrt{X})$, thỏa thì gáncheck[X] = 1, không thỏa thìcheck[X] = 0.check[X] == 1: đã biết là số hoàn thiện, đưa luôn vào kết quả trong $O(1)$.check[X] == 0: đã biết không thỏa, bỏ qua.
Nhờ vậy mỗi giá trị khác nhau chỉ bị kiểm tra đúng 1 lần. Mà các giá trị khác nhau chỉ có tối đa $3 \cdot 10^5$ số, nên tổng số lần lặp không bao giờ vượt quá $\sum_{X=1}^{3\cdot 10^5} \sqrt{X} \approx \tfrac{2}{3}\,(3 \cdot 10^5)^{1.5} \approx 1.1 \cdot 10^8$ – và đó là khi dãy chứa đủ mọi giá trị khác nhau, còn dãy toàn số lớn lặp lại thì gần như không tốn gì.
check $3 \cdot 10^5$ phần tử hay mảng a $N$ phần tử thì nên dùng mảng động (vector hoặc con trỏ cấp phát động) chứ đừng khai báo mảng tĩnh cục bộ trong hàm. Ví dụ Visual Studio chỉ cấp cho stack tầm 1 MB $= 1\,048\,576$ byte; mảng int 4 byte thì chỉ chứa được $262\,144$ phần tử là hết. Dùng short 2 byte thì chứa được $524\,288$ phần tử (vì check chỉ cần 3 giá trị $-1, 0, 1$), còn quen xài int thì cứ cấp phát động – vùng nhớ heap cho tới cỡ 1 GB, xài thoải mái.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() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
vector<int> check(300000, -1);
vector<int> res;
for(int i = 0; i < n; ++i){
if(check[a[i]] == -1){
int sum = 0;
int j;
for(j = 1; j * j <= a[i]; ++j){
if(a[i] % j == 0){
sum += j;
sum += a[i] / j;
}
}
if((j - 1) * (j - 1) == a[i]){
sum -= (j - 1);
}
sum -= a[i];
if(sum == a[i]){
res.push_back(a[i]);
check[a[i]] = 1;
}
else{
check[a[i]] = 0;
}
}
else if(check[a[i]] == 1){
res.push_back(a[i]);
}
}
cout << (int)res.size() << endl;
for(int i = 0; i < (int)res.size(); ++i){
cout << res[i] << " ";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
check = [-1] * 300000
res = []
for x in a:
if check[x] == -1:
s = 0
j = 1
while j * j <= x:
if x % j == 0:
s += j
s += x // j
j += 1
if (j - 1) * (j - 1) == x:
s -= (j - 1)
s -= x
if s == x:
res.append(x)
check[x] = 1
else:
check[x] = 0
elif check[x] == 1:
res.append(x)
print(len(res))
print(*res)
main()Giải thích một số chỗ trong code:
- 3 dòng đầu hàm
main(ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);): hiểu cơ bản là giúpcin/coutchạy nhanh gần bằng nhập xuất của C. Bài này phải đọc tới $3 \cdot 10^5$ số nên nhớ thêm 3 dòng này vào đầu hàm main nhé. vector<int> check(300000, -1);: khởi tạo mảng $300\,000$ phần tử, tất cả mang giá trị $-1$.- Biến
jkhai báo ngoài vòngfor: để sau vòng lặp vẫn dùng được, $j - 1$ chính là $\lfloor\sqrt{X}\rfloor$ – dùng để kiểm tra số chính phương.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N + V)$ với $V = 3 \cdot 10^5$ là kích thước mảng đánh dấu.
- Thời gian: mỗi giá trị khác nhau chỉ kiểm tra 1 lần trong $O(\sqrt{X})$, các lần gặp lại chỉ $O(1)$ ⇒ tối đa cỡ $N + 1.1 \cdot 10^8$ phép lặp trong trường hợp xấu nhất (dãy gồm toàn số khác nhau và lớn), thực tế phép lặp rất đơn giản nên C++ chạy chưa tới nửa giây.
Cách 2Nhận xét: chỉ có 4 số hoàn thiện – O(N)
Thực ra bài này giải như trên là chưa tối ưu đâu các bạn nha. Ta có thể làm tốt hơn nữa cả về thời gian, bộ nhớ lẫn code trình bày.
Bạn nào từng làm qua sẽ biết các số hoàn thiện rất ít, không nhiều như số nguyên tố đâu. 4 số hoàn thiện nhỏ nhất là $6, 28, 496, 8128$, còn số tiếp theo đã là $33\,550\,336$. Vậy nên với $0 \lt A_i \lt 3 \cdot 10^5$ thì yên tâm chỉ có đúng 4 trường hợp:
| Số hoàn thiện | Các ước nhỏ hơn nó |
|---|---|
| $6$ | $1 + 2 + 3$ |
| $28$ | $1 + 2 + 4 + 7 + 14$ |
| $496$ | $1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248$ |
| $8128$ | $1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064$ |
Đến đây mọi thứ đơn giản hẳn: với mỗi giá trị đọc vào, không cần mảng đánh dấu hay vòng lặp gì cả, chỉ một câu if xem nó có rơi vào 4 số này không, có thì đưa vào mảng kết quả. Thậm chí chẳng cần mảng lưu dãy đầu vào, vừa đọc vừa kiểm tra luôn, tiết kiệm thêm bộ nhớ hihi.
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() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, x;
cin >> n;
vector<int> res;
while(n--){
cin >> x;
if(x == 6 || x == 28 || x == 496 || x == 8128){
res.push_back(x);
}
}
cout << (int)res.size() << endl;
for(int i = 0; i < (int)res.size(); ++i){
cout << res[i] << " ";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
res = []
for i in range(1, n + 1):
x = int(data[i])
if x == 6 or x == 28 or x == 496 or x == 8128:
res.append(x)
print(len(res))
print(*res)
main()while(n--) là cách viết gọn của vòng lặp chạy đúng $n$ lần (mỗi lần kiểm tra $n \ne 0$ rồi giảm $n$ đi 1). Mỗi lần lặp đọc một giá trị vào $x$, kiểm tra $x$ có là 1 trong 4 số thỏa mãn không, thỏa thì đưa vào mảng kết quả; sau cùng in mảng kết quả.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(K)$ với $K$ là số phần tử của mảng kết quả.
- Thời gian: $O(N)$ đọc dữ liệu + $O(K)$ in kết quả; $K$ chỉ là tập con của $N$, theo quy tắc cộng Big-O lấy thành phần lớn nhất ⇒ $O(N)$. Xấu nhất toàn bộ đều là số hoàn thiện thì lặp $2N = 6 \cdot 10^5$ lần, ít hơn ngưỡng cả 100 đến 200 lần, yên tâm không thể TLE.
Đến đây các bạn đã thấy cái hay của giải thuật chưa? Từ cách làm cần lặp hết 90 tỷ lần, rút xuống 45 tỷ, rồi gần 200 triệu, cuối cùng chỉ còn 600 ngàn lần lặp. Quá là tuyệt vời đúng không các bạn 😍
- 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