HSG THPT - Bắc Ninh 2026
Điểm: 5
Anna là một học sinh yêu thích toán học, đặc biệt là các bài toán liên quan đến dãy số và phần dư của phép chia hai số nguyên. Theo quan điểm của Anna thì độ lệch của hai số nguyên ~x~ và ~y~ là phần dư của phép chia số lớn cho số bé.
Ví dụ: Với ~x = 7; y = 4~ thì độ lệch của hai số ~x~ và ~y~ là 3.
Độ lệch của một dãy số nguyên là độ lệch lớn nhất của hai phần tử bất kì trong dãy đó.
Ví dụ: Với dãy số ~A = (2, 9, 5)~ thì độ lệch của dãy số ~A~ là 4.
Yêu cầu: Cho dãy số ~A~ gồm ~N~ phần tử nguyên không âm ~A_1, A_2, \ldots, A_N~. Tìm độ lệch của dãy số ~A~.
Dữ liệu vào
Dữ liệu vào từ thiết bị vào chuẩn gồm hai dòng:
- Dòng 1: Ghi số nguyên ~N~ là số lượng phần tử của dãy số ~A (1 < N \le 2 \times 10^5)~;
- Dòng 2: Ghi ~N~ số nguyên ~A_1, A_2, \ldots, A_N (0 \le A_i \le 10^6)~.
Kết quả
Ghi ra thiết bị ra chuẩn một số nguyên là kết quả của bài toán.
Ví dụ
Input 1
3
4 2 7
Output 1
3
Giải thích:
4 chia 2 dư 0 → độ lệch của 4 và 2 là 0;
7 chia 2 dư 1 → độ lệch của 7 và 2 là 1;
7 chia 4 dư 3 → độ lệch của 7 và 4 là 3.
→ Kết quả cần tìm là 3
Ràng buộc
- Subtask 1: Có 80% số test ứng với 80% số điểm có ~N \le 5 \times 10^3~;
- Subtask 2: Có 20% số test ứng với 20% số điểm có ~N \le 2 \times 10^5~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout). Vẫn có thể giữ đoạn freopen("DOLECH.INP", ...) nếu đặt trong điều kiện if (fopen("DOLECH.INP", "r")).
Điểm: 7
Cho dãy ~A~ gồm ~N~ phần tử nguyên ~A_1, A_2, \ldots, A_N~ và số nguyên dương ~K~. Khi thực hiện thao tác xóa ~K~ phần tử bất kì khỏi dãy ~A~ ta thu được dãy ~B~ gồm các phần tử còn lại của dãy ~A~. Gọi ~M~ là hiệu lớn nhất giữa hai số bất kỳ trong dãy ~B, m~ là hiệu không âm nhỏ nhất giữa hai số bất kỳ trong dãy ~B~.
Yêu cầu: Tìm giá trị nhỏ nhất của ~|M| + |m|~.
Dữ liệu vào
Dữ liệu vào từ thiết bị vào chuẩn gồm hai dòng:
- Dòng 1: Ghi hai số nguyên dương ~N~ và ~K (3 \le N \le 10^6, 1 \le K \le N - 2)~;
- Dòng 2: Ghi ~N~ số nguyên ~A_1, A_2, \ldots, A_N (|A_i| \le 5 \times 10^6; i = 1, 2, \ldots, N)~.
Kết quả
Ghi ra thiết bị ra chuẩn một giá trị duy nhất là kết quả của bài toán.
Ví dụ
Input 1
5 2
-3 -2 3 8 6
Output 1
7
Giải thích:
Có thể xóa hai số −3, −2 → dãy ~B = (3, 8, 6)~
→ ~M = 5; m = 2~ → kết quả bằng ~5 + 2 = 7~
Input 2
6 2
-5 8 10 1 13 -1
Output 2
13
Giải thích:
Có thể xóa hai số −5, 13 → dãy ~B = (8, 10, 1, -1)~
→ ~M = 11; m = 2~ → kết quả bằng ~11 + 2 = 13~
Ràng buộc
- Subtask 1: Có 30% số test ứng với 30% số điểm có ~N \le 20~;
- Subtask 2: Có 40% số test ứng với 40% số điểm có ~N \le 10^3~;
- Subtask 3: Có 30% số test ứng với 30% số điểm có ~N \le 10^6~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout). Vẫn có thể giữ đoạn freopen("XOASO.INP", ...) nếu đặt trong điều kiện if (fopen("XOASO.INP", "r")).
Điểm: 5
Điệp viên Smith có gói tin quan trọng cần bảo mật nên anh đặt mật khẩu. Smith ghi vào sổ dãy ~A~ có ~N~ số nguyên ~A_1, A_2, A_3, \ldots, A_N (1 \le A_i \le 10^6)~. Dãy ~A~ có ít nhất ~M~ giá trị khác nhau. Mật khẩu của Smith là một đoạn con liên tiếp ~A_L, A_{L+1}, \ldots, A_R (1 \le L \le R \le N)~ ngắn nhất chứa đủ ~M~ giá trị khác nhau. Khi đó, giá trị ~R - L + 1~ là độ dài của mật khẩu.
Do Smith được giao quá nhiều nhiệm vụ quan trọng và đột xuất nên tạm thời anh ấy bị quên mất mật khẩu. Smith muốn dò lại mật khẩu từ dãy số ~A~ nhưng để việc tìm kiếm thuận lợi anh cần tìm chính xác độ dài của mật khẩu đó.
Yêu cầu: Bạn hãy giúp Smith tìm độ dài của mật khẩu.
Dữ liệu vào
Dữ liệu vào từ thiết bị vào chuẩn gồm hai dòng:
- Dòng 1: Ghi 2 số nguyên dương ~N, M (N \le 5 \times 10^6, M \le N)~;
- Dòng 2: Ghi ~N~ số nguyên dương ~A_1, A_2, A_3, \ldots, A_N (1 \le A_i \le 10^6)~.
Kết quả
Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là kết quả của bài toán.
Ví dụ
Input 1
10 4
5 2 1 1 3 2 1 3 2 1
Output 1
5
Đoạn con (5, 2, 1, 1, 3) có đủ 4 giá trị khác nhau {5, 2, 1, 3} và không có đoạn nào ngắn hơn thoả mãn.
Ràng buộc
- Subtask 1: Có 60% số test ứng với 60% số điểm có ~1 \le N \le 10^2~;
- Subtask 2: Có 40% số test ứng với 40% số điểm có ~10^2 < N \le 5 \times 10^6~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout). Vẫn có thể giữ đoạn freopen("MATKHAU.INP", ...) nếu đặt trong điều kiện if (fopen("MATKHAU.INP", "r")).
Điểm: 3
Tom rất yêu thích việc liệt kê các dãy con (đặc biệt là các dãy con tăng) của một dãy số nguyên. Ta gọi ~A'~ là một dãy con tăng của dãy ~A~ nếu ~A'~ thu được bằng cách bỏ đi một số phần tử của ~A~, giữ nguyên thứ tự các phần tử còn lại và các phần tử trong ~A'~ được sắp xếp theo thứ tự tăng nghiêm ngặt.
Ví dụ: Cho dãy ~A = [6, 1, 9, 5, 8, 5]~. Các dãy [1, 5, 8] và [1, 8] là dãy con tăng của ~A~ nhưng [1, 5, 5] và [6, 1, 5] thì không phải.
Với niềm đam mê tìm hiểu các con số, Tom định nghĩa độ khó của một số nguyên là tích các chữ số của nó.
Ví dụ: Hai số 1234 và 813 đều có độ khó bằng 24, còn số 8 có độ khó bằng chính nó.
Tom viết ra một dãy số ~A~ nguyên ngẫu nhiên, không có phần tử âm và đố Been tìm ra độ khó lớn nhất của dãy con tăng nghiêm ngặt trong dãy ~A~. Biết rằng độ khó của một dãy số được quy ước là tổng độ khó của tất cả các phần tử trong dãy đó.
Yêu cầu: Cho dãy ~A~ gồm ~N~ số nguyên không âm ~A_1, A_2, \ldots, A_N~. Tìm độ khó lớn nhất của dãy con tăng trong dãy ~A~.
Dữ liệu vào
Dữ liệu vào từ thiết bị vào chuẩn gồm hai dòng:
- Dòng 1: Ghi số nguyên dương ~N (1 \le N \le 2 \times 10^5)~;
- Dòng 2: Ghi ~N~ số nguyên không âm ~A_1, A_2, A_3, \ldots, A_N (0 \le A_i \le 10^9; i = 1, 2, \ldots, N)~.
Kết quả
Ghi ra thiết bị ra chuẩn một số nguyên là kết quả cần tìm.
Ví dụ
Input 1
5
5 101 54 123 56
Output 1
55
Giải thích:
Dãy [5, 54, 56] có độ khó lớn nhất trong số các dãy con tăng. Độ khó của nó là ~5 + 20 + 30 = 55~
Ràng buộc
- Subtask 1: Có 20% số test ứng với 20% số điểm có ~N \le 20~;
- Subtask 2: Có 20% số test ứng với 20% số điểm có ~N \le 2000~;
- Subtask 3: Có 60% số test ứng với 60% số điểm có ~N \le 2 \times 10^5~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout). Vẫn có thể giữ đoạn freopen("DAYCON.INP", ...) nếu đặt trong điều kiện if (fopen("DAYCON.INP", "r")).