HSG THPT Bắc Ninh 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠOBẮC NINH(Đề thi có 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THPT Năm học 2025 - 2026
Môn thi: Tin học

Chú ý: Dấu * được thay thế bởi py hoặc cpp của ngôn ngữ lập trình được sử dụng tương ứng là Python hoặc C++.

Bài 1 (5,0 điểm). Độ lệch

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₁, A₂, …, A_N. Tìm độ lệch của dãy số A.

Dữ liệu: Đọc từ tệp văn bản DOLECH.INP 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 ≤ 2 × 10⁵);
Dòng 2: Ghi N số nguyên A₁, A₂, …, A_N (0 ≤ Aᵢ ≤ 10⁶).

Kết quả: Ghi ra tệp văn bản DOLECH.OUT một số nguyên là kết quả của bài toán.

Ví dụ:

DOLECH.INP	DOLECH.OUT	Giải thích
`3` `4 2 7`	`3`	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 ≤ 5 × 10³;
Subtask 2: Có 20% số test ứng với 20% số điểm có N ≤ 2 × 10⁵.

Bài 2 (7,0 điểm). Xóa số

Cho dãy A gồm N phần tử nguyên A₁, A₂, …, 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: Đọc từ tệp văn bản XOASO.INP gồm hai dòng:

Dòng 1: Ghi hai số nguyên dương N và K (3 ≤ N ≤ 10⁶, 1 ≤ K ≤ N − 2);
Dòng 2: Ghi N số nguyên A₁, A₂, …, A_N (|Aᵢ| ≤ 5 × 10⁶; i = 1, 2, …, N).

Kết quả: Ghi ra tệp văn bản XOASO.OUT một giá trị duy nhất là kết quả của bài toán.

Ví dụ:

XOASO.INP	XOASO.OUT	Giải thích
`5 2` `-3 -2 3 8 6`	`7`	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
`6 2` `-5 8 10 1 13 -1`	`13`	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 ≤ 20;
Subtask 2: Có 40% số test ứng với 40% số điểm có N ≤ 10³;
Subtask 3: Có 30% số test ứng với 30% số điểm có N ≤ 10⁶.

Bài 3 (5,0 điểm). Mật khẩu

Đ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₁, A₂, A₃, …, A_N (1 ≤ Aᵢ ≤ 10⁶). 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), …, A_R (1 ≤ L ≤ R ≤ 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: Đọc từ tệp văn bản MATKHAU.INP gồm hai dòng:

Dòng 1: Ghi 2 số nguyên dương N, M (N ≤ 5 × 10⁶, M ≤ N);
Dòng 2: Ghi N số nguyên dương A₁, A₂, A₃, …, A_N (1 ≤ Aᵢ ≤ 10⁶).

Kết quả: Ghi ra tệp văn bản MATKHAU.OUT một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

MATKHAU.INP	MATKHAU.OUT
`10 4` `5 2 1 1 3 2 1 3 2 1`	`5`

Ràng buộc:

Subtask 1: Có 60% số test ứng với 60% số điểm có 1 ≤ N ≤ 10²;
Subtask 2: Có 40% số test ứng với 40% số điểm có 10² < N ≤ 5 × 10⁶.

Bài 4 (3,0 điểm). Dãy con tăng

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 là dãy con tăng của A.

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 đó. Các bạn hãy lập trình giúp Been nhé!

Yêu cầu: Cho dãy A gồm N số nguyên không âm A₁, A₂, …, A_N. Tìm độ khó lớn nhất của dãy con tăng trong dãy A.

Dữ liệu: Đọc từ tệp văn bản DAYCON.INP gồm hai dòng:

Dòng 1: Ghi số nguyên dương N (1 ≤ N ≤ 2 × 10⁵);
Dòng 2: Ghi N số nguyên không âm A₁, A₂, A₃, …, A_N (0 ≤ Aᵢ ≤ 10⁹; i = 1, 2, …, N).

Kết quả: Ghi ra tệp văn bản DAYCON.OUT một số nguyên là kết quả cần tìm.

Ví dụ:

DAYCON.INP	DAYCON.OUT	Giải thích
`5` `5 101 54 123 56`	`55`	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 ≤ 20;
Subtask 2: Có 20% số test ứng với 20% số điểm có N ≤ 2000;
Subtask 3: Có 60% số test ứng với 60% số điểm có N ≤ 2 × 10⁵.

Thí sinh không được sử dụng tài liệu.
Giám thị không giải thích gì thêm.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English