Tuyển sinh 10 chuyên Tin Quảng Ninh 2025
Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan
Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.
Câu 1. Ước nguyên dương thực sự lớn nhất
Số nguyên dương a được gọi là ước nguyên dương thực sự của số nguyên n nếu a là ước của n và a < n. Ví dụ số 24 có 7 ước nguyên dương thực sự là: 1, 2, 3, 4, 6, 8, 12.
Yêu cầu : Hãy xác định ước nguyên dương thực sự lớn nhất của n.
INPUT
Gồm một dòng chứa số nguyên dương n (2 ≤ n ≤ 105).
OUTPUT
Ước nguyên dương thực sự lớn nhất của n.
SAMPLE INPUT 1
4SAMPLE OUTPUT 1
2SAMPLE INPUT 2
7SAMPLE OUTPUT 2
1SAMPLE INPUT 3
24SAMPLE OUTPUT 3
12---
Ghi chú về bản chuyển thể
Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.
Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.
Câu 2. Đếm đoạn con có tổng chẵn và độ dài ít nhất hai
Cho một dãy gồm n số nguyên dương a1, a2, ..., an.
Yêu cầu: Đếm số cặp (i, j) đồng thời thỏa mãn:
- 1 ≤ i < j ≤ n;
- ai + ai+1 + ... + aj là một số chẵn.
INPUT
Dòng đầu chứa số nguyên dương n (2 ≤ n ≤ 105);
Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an (1 ≤ ai ≤ 109; i = 1, 2, ..., n).
OUTPUT
Số lượng cặp (i, j) thỏa mãn yêu cầu của bài.
SAMPLE INPUT 1
5
1 2 3 4 5SAMPLE OUTPUT 1
4Giải thích: Số cặp thỏa mãn là (1, 3), (1, 4), (2, 5), (3, 5).
SAMPLE INPUT 2
4
2 5 6 4SAMPLE OUTPUT 2
1SUBTASKS
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 40% | n ≤ 102. |
| 2 | 40% | 102 < n ≤ 5 × 103. |
| 3 | 20% | Không có ràng buộc gì thêm. |
---
Ghi chú về bản chuyển thể
Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.
Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.
Câu 3. Trung vị thấp hơn lớn nhất trên đoạn dài ít nhất k
Dãy A gồm n số nguyên a1, a2, ..., an được gọi là dãy không giảm nếu thỏa mãn: a1 ≤ a2 ≤ ... ≤ an.
Trung vị của dãy các số nguyên a1, a2, ..., an là phần tử xuất hiện ở vị trí [n+12] sau khi dãy đó được sắp xếp lại thành dãy không giảm.
Ví dụ: Cho dãy A = (2, 3, 4, 2, 8) sau khi sắp xếp lại thành dãy không giảm ta được dãy (2, 2, 3, 4, 8), trung vị của dãy là phần tử 3; dãy B = (3, 5, 7, 6) sau khi sắp xếp lại thành dãy không giảm ta được dãy (3, 5, 6, 7), trung vị của dãy là phần tử 5. Trung vị của dãy chỉ có một phần tử là chính phần tử đó.
Yêu cầu: Cho dãy A gồm n số nguyên a1, a2, ..., an và số nguyên k. Hãy xác định trung vị lớn nhất của mọi dãy con gồm ít nhất k phần tử liên tiếp trong dãy đã cho.
INPUT
Dòng đầu chứa hai số nguyên n, k (1 ≤ k ≤ n ≤ 105);
Dòng thứ hai chứa n số nguyên a1, a2, ..., an (1 ≤ ai ≤ n; i = 1, 2, ..., n).
OUTPUT
In ra kết quả bài toán.
SAMPLE INPUT 1
4 2
1 3 2 4SAMPLE OUTPUT 1
3Giải thích:
SAMPLE INPUT 2
4 1
1 2 2 4SAMPLE OUTPUT 2
4SAMPLE INPUT 3
11 2
3 2 3 2 11 5 2 3 9 10 11SAMPLE OUTPUT 3
10SAMPLE INPUT 4
11 6
3 2 3 2 11 5 2 3 9 10 11SAMPLE OUTPUT 4
9SUBTASKS
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 20% | k = 2, n = 3. |
| 2 | 20% | k = 1 |
| 3 | 30% | n ≤ 100 |
| 4 | 30% | Không có ràng buộc gì thêm. |
---
Ghi chú về bản chuyển thể
Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.
Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.
Câu 4. Dãy con chung không giảm dài nhất của hai dãy nhị phân
Cho dãy a gồm n số nguyên a1, a2, ..., an.
Giá trị n được gọi là độ dài của dãy a.
Dãy con của a là chính a hoặc là dãy nhận được từ dãy ban đầu bằng cách bỏ đi một số phần tử.
Dãy a được gọi là dãy không giảm nếu thỏa mãn: a1 ≤ a2 ≤ ... ≤ an.
Ví dụ dãy: [2, 2, 4, 9, 3, 10] ta có một số dãy con như sau: [2, 2, 4, 10]; [2, 9]; [3, 2, 9, 10].
Trong đó, các dãy con [2, 2, 4, 10] và [2, 9, 10] được gọi là các dãy con không giảm.
Cho dãy a gồm n số nguyên, dãy b gồm m số nguyên. Dãy c được gọi là dãy con chung của hai dãy a và b nếu c vừa là dãy con của a, vừa là dãy con của b.
Ví dụ: Cho dãy a = (1, 2, 4, 9, 3) và dãy b = (0, 2, 15, 9). Dãy c = (2, 9) là một dãy con chung của hai dãy a và b.
Yêu cầu: Cho hai dãy a và b chỉ chứa các số 0 và 1, dãy a có n phần tử, dãy b có m phần tử. Hãy xác định độ dài lớn nhất của dãy con chung không giảm của a và b.
INPUT
Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 2 × 105) là số phần tử của dãy a.
Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an (0 ≤ ai ≤ 1) là các phần tử của dãy a.
Dòng thứ ba chứa số nguyên dương m (1 ≤ m ≤ 2 × 105) là số phần tử của dãy b.
Dòng thứ tư chứa m số nguyên dương b1, b2, ..., bm (0 ≤ bi ≤ 1) là các phần tử của dãy b.
Dữ liệu đảm bảo luôn tồn tại dãy con chung.
OUTPUT
Độ dài lớn nhất của dãy con chung không giảm của hai dãy a và b.
SAMPLE INPUT 1
7
0 0 0 1 0 1 1
6
0 0 1 1 0 1SAMPLE OUTPUT 1
5Dãy con chung không giảm dài nhất là 0, 0, 1, 1, 1.
SAMPLE INPUT 2
10
0 0 0 1 1 1 0 1 0 0
10
1 1 0 0 0 1 0 1 1 1SAMPLE OUTPUT 2
7SAMPLE INPUT 3
3
1 1 1
5
1 0 1 0 0SAMPLE OUTPUT 3
2SUBTASKS
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 25 | ai = 1, m, n ≤ 3000. |
| 2 | 25 | m = n, ai = bi |
| 3 | 25 | m, n ≤ 3000 |
| 4 | 25 | Không có ràng buộc gì thêm. |
---
Ghi chú về bản chuyển thể
Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.
Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.
