Cho mảng gồm n số nguyên được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Kiểm tra xem trong mảng có tồn tại hai phần tử có tổng bằng x hay không.
Dữ liệu vào: Dòng đầu chứa hai số nguyên dương n và x (2 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In YES nếu tồn tại, ngược lại in NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 9 1 2 3 4 6 |
YES | 3 + 6 = 9. |
Giới hạn:
Cho mảng gồm n số nguyên được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Đếm số cặp chỉ số (i, j) với i < j sao cho a[i] + a[j] = x.
Dữ liệu vào: Dòng đầu chứa hai số nguyên dương n và x (2 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In số cặp tìm được.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 7 1 2 3 4 5 |
2 | Hai cặp là (2,5) và (3,4). |
Giới hạn:
Cho mảng gồm n số nguyên được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Đếm số cặp chỉ số (i, j) với i < j sao cho a[i] + a[j] < x.
Dữ liệu vào: Dòng đầu chứa hai số nguyên dương n và x (2 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In số cặp tìm được.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 7 1 2 3 4 5 |
4 | Các cặp thỏa mãn là (1,2), (1,3), (1,4), (2,3). |
Giới hạn:
Cho mảng gồm n số nguyên được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Đếm số cặp chỉ số (i, j) với i < j sao cho a[i] + a[j] > x.
Dữ liệu vào: Dòng đầu chứa hai số nguyên dương n và x (2 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In số cặp tìm được.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 6 1 2 3 4 5 |
6 | Có 6 cặp có tổng lớn hơn 6. |
Giới hạn:
Cho mảng gồm n số nguyên được sắp xếp theo thứ tự không giảm và một số nguyên không âm k.
Yêu cầu: Đếm số cặp chỉ số (i, j) với i < j sao cho a[j] − a[i] < k.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và k (2 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In số cặp thỏa mãn.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 3 1 2 4 6 7 |
5 | Các cặp là (1,2), (2,4), (4,6), (4,7), (6,7). |
Giới hạn:
Cho hai mảng A và B đã được sắp xếp theo thứ tự không giảm.
Yêu cầu: Gộp hai mảng thành một mảng mới cũng được sắp xếp theo thứ tự không giảm.
Dữ liệu vào: Dòng đầu chứa hai số nguyên dương n và m (1 ≤ n, m ≤ 105). Dòng thứ hai chứa n số nguyên của mảng A. Dòng thứ ba chứa m số nguyên của mảng B.
Dữ liệu ra: In mảng sau khi gộp.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 3 4 1 3 7 2 4 5 8 |
1 2 3 4 5 7 8 | Gộp hai mảng và vẫn giữ thứ tự tăng dần. |
Giới hạn:
Cho hai mảng A và B đã được sắp xếp theo thứ tự không giảm.
Yêu cầu: In các phần tử thuộc giao của hai mảng theo thứ tự tăng dần. Mỗi giá trị chỉ in một lần.
Dữ liệu vào: Giống Bài 6.
Dữ liệu ra: In các phần tử thuộc giao của hai mảng. Nếu không có phần tử chung, in NONE.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 4 1 2 3 5 7 2 3 4 7 |
2 3 7 | Các phần tử xuất hiện trong cả hai mảng. |
Giới hạn:
Cho hai mảng A và B đã được sắp xếp theo thứ tự không giảm.
Yêu cầu: In hợp của hai mảng theo thứ tự tăng dần. Mỗi giá trị chỉ in một lần.
Dữ liệu vào: Giống Bài 6.
Dữ liệu ra: In các phần tử thuộc hợp của hai mảng.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 4 4 1 2 4 6 2 3 4 7 |
1 2 3 4 6 7 | Mỗi giá trị chỉ xuất hiện một lần. |
Giới hạn:
Cho một mảng đã được sắp xếp theo thứ tự không giảm.
Yêu cầu: Loại bỏ các phần tử trùng nhau và in ra mảng sau khi loại bỏ.
Dữ liệu vào: Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In mảng sau khi loại bỏ các phần tử trùng nhau.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 8 1 1 2 2 2 4 5 5 |
1 2 4 5 | Mỗi giá trị chỉ còn xuất hiện một lần. |
Giới hạn:
Cho một mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm.
Yêu cầu: Loại bỏ các phần tử trùng nhau và in ra mảng sau khi nén. Mỗi giá trị chỉ xuất hiện đúng một lần và vẫn giữ nguyên thứ tự tăng dần.
Dữ liệu vào: Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: Dòng đầu in số lượng phần tử sau khi nén. Dòng thứ hai in mảng sau khi nén.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 8 1 1 2 2 2 4 5 5 |
4 1 2 4 5 |
Sau khi nén, mỗi giá trị chỉ còn xuất hiện một lần. |
Giới hạn:
Gợi ý: Sử dụng hai con trỏ (slow và fast) để ghi đè các phần tử khác nhau lên đầu mảng.
Cho mảng gồm n số nguyên (chưa được sắp xếp) và một số nguyên x.
Yêu cầu: Kiểm tra xem trong mảng có tồn tại hai phần tử có tổng bằng x hay không.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (2 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên.
Dữ liệu ra: In YES nếu tồn tại, ngược lại in NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 8 5 1 4 7 3 |
YES | Sau khi sắp xếp, tồn tại cặp 1 và 7. |
Giới hạn:
Cho mảng gồm n số nguyên và một số nguyên x.
Yêu cầu: Tìm cặp phần tử có tổng gần x nhất. Nếu có nhiều đáp án, in giá trị tổng nhỏ nhất trong các đáp án đó.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (2 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên.
Dữ liệu ra: In tổng của cặp tìm được.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 10 1 3 5 8 9 |
10 | Cặp (1,9) có tổng đúng bằng 10. |
Giới hạn:
Cho mảng gồm n số nguyên và một số nguyên không âm k.
Yêu cầu: Kiểm tra xem có tồn tại hai phần tử có hiệu bằng k hay không.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và k (2 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên.
Dữ liệu ra: In YES nếu tồn tại, ngược lại in NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 3 1 8 4 6 10 |
YES | Sau khi sắp xếp, 1 và 4 có hiệu bằng 3. |
Giới hạn:
Có n người với cân nặng đã được sắp xếp theo thứ tự không giảm và một chiếc thuyền chỉ chở được tối đa hai người với tổng cân nặng không vượt quá giới hạn L.
Yêu cầu: Tìm số lượng thuyền ít nhất cần dùng để chở hết mọi người.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và L (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên biểu diễn cân nặng của các người đã được sắp xếp theo thứ tự không giảm.
Dữ liệu ra: In số lượng thuyền ít nhất cần dùng.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 4 100 40 50 70 80 |
3 | Ghép (40,50), (70), (80). |
Giới hạn:
Cho mảng gồm n số nguyên dương đã được sắp xếp theo thứ tự không giảm và một số nguyên dương x.
Yêu cầu: Kiểm tra xem có tồn tại hai phần tử có tích bằng x hay không.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (2 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên dương đã được sắp xếp.
Dữ liệu ra: In YES nếu tồn tại, ngược lại in NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 5 20 1 2 4 5 10 |
YES | 2 × 10 = 20. |
Giới hạn: