Quà Trung Thu (QUATANG – HSG 18.19)
Đề bài
QUATANG – Quà Trung Thu – HSG 18.19 · Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte
Nhân dịp tết trung thu, Nam được mẹ cho đi dự lễ hội "Đêm trăng rằm", tại lễ hội Nam đã tích cực tham gia các chương trình đố vui và giành được số điểm là $X$. Nam muốn tặng bố mẹ mỗi người một món quà theo chương trình đổi điểm lấy quà của ban tổ chức. Biết rằng ban tổ chức có $N$ món quà, món thứ $i$ phải dùng $a[i]$ điểm để đổi $(1 \le i \le N)$. Với số điểm có được Nam quyết định sẽ đổi 2 món quà khác nhau có tổng giá trị lớn nhất có thể được.
Yêu cầu: Hãy xác định số điểm Nam dùng để đổi quà tặng bố mẹ.
Dữ liệu nhập:
- Dòng thứ nhất là hai số nguyên $N$ và $X$ $(2 \le N \le 10^5;\ 2 \le X \le 10^9)$.
- Dòng thứ hai là dãy $a[1], a[2], \ldots, a[N]$ $(1 \le a[i] \le 10^9)$.
Kết quả:
- In ra một số duy nhất là số điểm quà đã đổi của Nam.
Ràng buộc:
- 50% test: $1 \le N \le 1000$.
(Đề thi gốc dùng file quatangtt.inp / quatangtt.out; trên hệ thống chấm online thì đọc/ghi chuẩn, nên trong code bên dưới mình để 2 dòng freopen ở dạng chú thích. Khi đi thi đọc ghi file thì các bạn bỏ dấu // ra nhé.)
8 8
6 3 8 10 6 1 9 477 6
5 2 7 7 9 6 24Lời mở đầu
Đề bài thì dài dòng nhưng tóm gọn lại các bạn có thể hiểu là: có $N$ số nguyên $a[1] \ldots a[N]$ và một số $X$, hãy tìm 2 số $a[i], a[j]$ ở 2 vị trí khác nhau sao cho tổng của chúng là lớn nhất có thể nhưng không vượt quá $X$ (tốt nhất là đúng bằng $X$, không được thì cố gắng lớn nhất có thể), rồi in ra tổng đó.
Vì sao phải ràng buộc tổng 2 số $\le X$? Vì $X$ là số điểm Nam có, chỉ đổi được 2 phần quà có tổng giá trị $\le X$ thôi chứ đâu thể hơn được. Giống như bạn có 10 đồng thì chỉ mua hàng trong 10 đồng đó thôi, các bạn hiểu rõ chỗ này hen 😄.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ:
- Ví dụ 1: $X = 8$, các món quà giá
6 3 8 10 6 1 9 4. Không có cặp nào cộng lại đúng bằng 8 (thử đi: 6 + ? = 8 cần số 2, 3 + ? cần 5, 4 + ? cần 4 mà chỉ có một số 4...). Tổng lớn nhất không vượt 8 là $7$, ví dụ $6 + 1$ hoặc $3 + 4$. - Ví dụ 2: $X = 6$, giá
5 2 7 7 9 6 2. Số 6 đứng một mình thì phải ghép với món khác, mà món rẻ nhất là 2 ⇒ 8 > 6, không được. Cặp $5 + 2 = 7$ cũng vượt. Chỉ còn $2 + 2 = 4$ (hai món giá 2 khác nhau) ⇒ đáp án $4$.
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:
Cách 1Vét cạn tất cả các cặp – O(N²)
Cách cơ bản nhất là vét cạn: xét tất cả các cặp $(i, j)$ với $i \lt j$, tính tổng và tìm Max trong các cặp có tổng $\le X$. Nếu gặp cặp nào tổng bằng đúng $X$ thì in luôn $X$ và kết thúc, không cần xét các cặp tiếp theo nữa, vì $X$ đã là tổng lớn nhất hợp lệ rồi, không còn cặp nào lớn hơn được.
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(){
// freopen("quatangtt.inp", "r", stdin);
// freopen("quatangtt.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
int Max = 0;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
int sum = a[i] + a[j];
if(sum == x){
cout << x;
return 0;
}
else if(sum < x){
Max = max(Max, sum);
}
}
}
cout << Max;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, x = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
Max = 0
for i in range(n):
for j in range(i + 1, n):
s = a[i] + a[j]
if s == x:
print(x)
return
elif s < x:
Max = max(Max, s)
print(Max)
main()Giải thích một số chỗ trong code ở trên:
- 2 dòng
ios::sync_with_stdio(0); cin.tie(0);giúp đẩy nhanh tốc độ nhập xuất khi code C++ (các bạn gõ mấy từ này lên Google sẽ ra rất nhiều bài giải thích). Bài này có thể nhập tới $10^5$ số nên thêm vào cho chương trình chạy nhanh hơn. - $N$ tối đa chỉ $10^5$ nên khai báo
int a[n];trên stack vẫn ổn. Nếu $N$ lớn hơn nữa, ví dụ $3 \cdot 10^5$ trở lên, thì nên dùng bộ nhớ heap:int *a = new int[n];hoặcvector<int> a(n);để tránh tràn stack. - $a[i] \le 10^9$ nên tổng 2 phần tử cao lắm là $2 \cdot 10^9$, vẫn nằm trong giới hạn của
int(tối đa khoảng 2.147 tỷ), nên dùngintcho tất cả. Nếu $a[i]$ lớn hơn, ví dụ $10^{10}$, thì phải dùnglong longđể tránh tràn số. - Vòng
for itheo lẽ chỉ cầni < n - 1. Nhưng đểi < ncũng không sao: khii = n - 1thì vòngfor jkhông chạy, chỉ thừa đúng 1 lần lặp. - $a[i] \ge 1$ nên tổng 2 phần tử tối thiểu là 2; khởi tạo
Max = 0thì lần so sánh hợp lệ đầu tiên chắc chắn cập nhật được. - Hàm
max(a, b)trả về số lớn hơn trong 2 số (tương tự cómin). Hàm này nằm trong thư việnalgorithm; ta dùngbits/stdc++.hđã bao hết nên không cần include thêm.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian: bước đọc dữ liệu $O(N)$ + bước xử lý chạy $\dfrac{N(N-1)}{2} = 0.5 \cdot (N^2 - N)$ lần. Theo quy tắc nhân Big-O bỏ hằng số, rồi quy tắc cộng lấy thành phần lớn nhất ⇒ $O(N^2)$. Cả bài: $O(N) + O(N^2) = O(N^2)$.
Cách 2Sắp xếp + tìm kiếm nhị phân (lower_bound) – O(N log N)
Cái dở của cách trên là ta phải vét đến tận cùng – bản chất là tìm kiếm tuyến tính (Linear Search), do dữ liệu nằm lộn xộn không có thứ tự. Nếu ta sắp xếp dãy tăng dần (hoặc giảm dần, miễn có trật tự) thì có thể nâng cấp lên tìm kiếm nhị phân (Binary Search).
Lấy ví dụ 1, sau khi sắp xếp: 1 3 4 6 6 8 9 10, $X = 8$.
- $a[i] = 1$: cần tìm $a[j]$ lớn nhất $\le X - a[i] = 7$ ở phía sau $i$ ⇒ tìm được $6$ ⇒ tổng $1 + 6 = 7$.
- $a[i] = 3$: cần $a[j] \le 5$ ⇒ tìm được $4$ ⇒ tổng $3 + 4 = 7$.
- $a[i] = 4$: cần $a[j] \le 4$ ở phía sau ⇒ phía sau toàn $\ge 6$, không có thằng nào thỏa.
- $a[i] = 6$: cần $a[j] \le 2$, giờ giá trị cần tìm còn nhỏ hơn cả $a[i]$, mà phía sau toàn số $\ge a[i]$ ⇒ không thể tìm ra, và càng về sau càng tệ hơn ⇒ dừng luôn.
Vậy tổng lớn nhất là $7$. Để tìm "phần tử lớn nhất $\le f$" ta dùng lower_bound (trả về vị trí phần tử đầu tiên $\ge f$), rồi lùi lại 1 nếu phần tử đó $\gt f$. Bạn nào chưa biết hàm này thì nên tìm hiểu nhé, nó rất tiện và ứng dụng rất nhiều.
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(){
// freopen("quatangtt.inp", "r", stdin);
// freopen("quatangtt.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a, a + n);
int Max = 0;
for(int i = 0; i < n - 1; ++i){
int f = x - a[i];
if(f < a[i] || (f == a[i] && a[i + 1] != f)){
break;
}
int idx = lower_bound(a + i + 1, a + n, f) - a;
if(idx == n){
idx--;
}
if(a[idx] == f){
cout << x;
return 0;
}
else if(a[idx] > f){
idx--;
}
if(idx == i){
break;
}
Max = max(Max, a[i] + a[idx]);
}
cout << Max;
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n, x = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
a.sort()
Max = 0
for i in range(n - 1):
f = x - a[i]
if f < a[i] or (f == a[i] and a[i + 1] != f):
break
idx = bisect_left(a, f, i + 1, n)
if idx == n:
idx -= 1
if a[idx] == f:
print(x)
return
elif a[idx] > f:
idx -= 1
if idx == i:
break
Max = max(Max, a[i] + a[idx])
print(Max)
main()Giải thích một số chỗ trong code ở trên:
sort(a, a + n)sắp tăng dần từ vị trí đầu (a) đủnphần tử, luôn đảm bảo $O(N \log N)$. Nếu tự cài thì phải dùng thuật toán $O(N \log N)$ như Quick Sort, Merge Sort, Heap Sort; dùng Selection Sort, Bubble Sort, Interchange Sort... $O(N^2)$ thì nội bước sắp xếp đã ngang cách 1 rồi, chắc chắn TLE.- Với mỗi $a[i]$ tính $f = x - a[i]$ là giá trị lớn nhất mà món thứ hai được phép có. Trước khi tìm, kiểm tra dừng sớm: nếu $f \lt a[i]$ thì phía sau toàn số $\ge a[i] \gt f$, không có thằng nào thỏa, các $i$ sau còn tệ hơn ⇒
break. Trường hợp đặc biệt $f = a[i]$ thì chỉ hợp lệ khi $a[i+1]$ cũng bằng $f$ (2 món cùng giá), nếu không cũngbreak. - Vòng lặp chỉ chạy
i < n - 1vì cặp cuối cùng là $a[n-2], a[n-1]$. Nếu choi = n - 1thì có thể "tìm" ra chính nó, mà ta phải chọn 2 món khác nhau. lower_boundtìm trong đoạn $[i+1, n)$ vị tríidxđầu tiên có $a[idx] \ge f$. Nếuidx == n(mọi phần tử đều $\lt f$) thì lấy phần tử cuối:idx--. Nếu $a[idx] = f$ thì tổng đúng bằng $x$ ⇒ in $x$, kết thúc luôn. Còn nếu $a[idx] \gt f$ thì phần tử liền trước là phần tử lớn nhất $\lt f$ ⇒idx--. Cuối cùng cập nhậtMax.
lower_bound trả về i + 1, rồi idx-- làm idx lùi về đúng i – tức là đem món quà $a[i]$ ghép với chính nó! Ví dụ 2 4 / 1 5: sau sắp xếp là 1 5, $i = 0$, $f = 3$, idx lùi về 0 ⇒ code gốc in $1 + 1 = 2$, trong khi đáp án đúng là $0$ (vì $1 + 5 = 6 \gt 4$). Hay như 3 9 / 1 4 6: code gốc in 8 (ghép 4 với chính nó) thay vì đáp án đúng 7. Mình thêm 3 dòng:
if(idx == i){
break;
}break là đúng luôn. Các bạn bấm nút "Bẫy ghép với chính nó" trong khung chạy tay bên dưới để xem tận mắt nhé.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian: đọc dữ liệu $O(N)$ + sắp xếp $O(N \log N)$ + vòng lặp tối đa $N$ lần, mỗi lần một
lower_boundtốn $O(\log N)$ ⇒ $O(N \log N)$. Tổng quát cả bài là $O(N \log N)$ (log cơ số 2).
Với $N = 10^5$ thì $N \log N \approx 10^5 \cdot 17 = 1.7$ triệu, ít hơn ngưỡng 1 giây cả chục lần ⇒ yên tâm không bị TLE.
Cách 3Sắp xếp + kỹ thuật hai con trỏ – O(N log N)
Cách trên đã AC rồi, nhưng chưa phải tối ưu nhất. Sau khi sắp xếp, thay vì tìm kiếm nhị phân $O(N \log N)$, ta dùng kỹ thuật Two Pointers (hai con trỏ) để bước xử lý chỉ còn $O(N)$. Tổng quát lý thuyết thì vẫn là $O(N \log N)$ vì còn bước sort, nhưng thực tế bước xử lý sau cùng đã nhanh hơn.
Yên tâm, "con trỏ" ở đây không phải kiến thức con trỏ/bộ nhớ trong C/C++ đâu nha, nó chỉ là tên gọi: đơn giản là 2 biến lưu vị trí và di chuyển phối hợp với nhau.
l = 0 (phần tử nhỏ nhất), r = n - 1 (phần tử lớn nhất). Khi l < r, tính sum = a[l] + a[r]:
sum < x: hợp lệ ⇒ cập nhậtMax, rồil++để thử tổng lớn hơn.sum == x: tốt nhất rồi ⇒Max = x,break.sum > x: vượt số điểm ⇒ không cập nhật,r--để tổng nhỏ lại.
l >= r thì không còn 2 món khác nhau để chọn nữa ⇒ dừng.Vì sao l++ khi tổng còn nhỏ mà không sợ bỏ sót? Khi a[l] + a[r] < x thì a[r] đã là món lớn nhất còn ghép được với a[l], mọi cặp $(l, r')$ với $r' \lt r$ chỉ cho tổng nhỏ hơn, nên a[l] đã "xài hết giá trị", bỏ đi được. Ngược lại khi a[l] + a[r] > x thì a[r] ghép với món nhỏ nhất còn lại mà vẫn vượt, thì ghép với ai cũng vượt ⇒ bỏ a[r].
Minh hoạ hai con trỏ
Em nhập $x$ và dãy giá quà rồi bấm Tiếp để xem l, r chạy lại gần nhau thế nào:
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(){
// freopen("quatangtt.inp", "r", stdin);
// freopen("quatangtt.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a, a + n);
int Max = 0, l = 0, r = n - 1;
while(l < r){
int sum = a[l] + a[r];
if(sum < x){
Max = max(Max, sum);
l++;
}
else if(sum == x){
Max = x;
break;
}
else{
r--;
}
}
cout << Max;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, x = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
a.sort()
Max, l, r = 0, 0, n - 1
while l < r:
s = a[l] + a[r]
if s < x:
Max = max(Max, s)
l += 1
elif s == x:
Max = x
break
else:
r -= 1
print(Max)
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian: sắp xếp $O(N \log N)$ + hai con trỏ $O(N)$ (mỗi bước
ltăng hoặcrgiảm, 2 đầu tiến lại tới khi chạm nhau là đi qua đủ $N$ phần tử). Tổng quát vẫn là $O(N \log N)$, ngang cách 2 về lý thuyết, nhưng bước xử lý sau cùng nhanh hơn.
Cách 4Hai con trỏ, đặt R thông minh bằng upper_bound
Ta còn có thể làm thêm một chút: vị trí r ban đầu không nhất thiết phải là cuối mảng. Khi l = 0 (món rẻ nhất $a[0]$), mọi món $a[r] \gt X - a[0]$ chắc chắn không ghép được với ai (ghép với món rẻ nhất còn vượt). Vậy r nên bắt đầu từ vị trí lớn nhất thỏa $a[r] \le X - a[0]$.
idx = upper_bound(a, a + n, x - a[0]) - a; trả về vị trí đầu tiên có giá trị $\gt X - a[0]$, nên r = idx - 1. Nếu không có phần tử nào lớn hơn thì idx = n ⇒ r = n - 1, vẫn hợp lý.Phần còn lại giống y cách 3. Mẹo này giúp bỏ qua nhanh một loạt bước r-- ở đầu (ví dụ 1 có các món 8, 9, 10 đều $\gt 8 - 1 = 7$ nên r nhảy thẳng tới món 6).
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(){
// freopen("quatangtt.inp", "r", stdin);
// freopen("quatangtt.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n >> x;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a, a + n);
int idx = upper_bound(a, a + n, x - a[0]) - a;
int Max = 0, l = 0, r = idx - 1;
while(l < r){
int sum = a[l] + a[r];
if(sum < x){
Max = max(Max, sum);
l++;
}
else if(sum == x){
Max = x;
break;
}
else{
r--;
}
}
cout << Max;
return 0;
}import sys
from bisect import bisect_right
def main():
data = sys.stdin.buffer.read().split()
n, x = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
a.sort()
idx = bisect_right(a, x - a[0])
Max, l, r = 0, 0, idx - 1
while l < r:
s = a[l] + a[r]
if s < x:
Max = max(Max, s)
l += 1
elif s == x:
Max = x
break
else:
r -= 1
print(Max)
main()Đánh giá độ phức tạp của cách làm này: giống cách 3: không gian $O(N)$, thời gian $O(N \log N)$ do bước sắp xếp; upper_bound chỉ tốn thêm $O(\log N)$ nhưng có thể giúp bỏ qua nhiều bước r-- vô ích.
upper_bound hehe. Hi vọng các bạn đã học được nhiều bài học kiến thức 😇.- 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