| TRƯỜNG THCS … Đề chính thức (Đề thi có 03 trang) | KỲ THI CHỌN HỌC SINH GIỎI CẤP TRƯỜNG NĂM HỌC 2026 – 2027 Môn: TIN HỌC – LỚP 8 Thời gian làm bài: 90 phút (không kể thời gian phát đề) |
|---|
TỔNG QUAN ĐỀ THI
| Bài | Tên bài | Tệp chương trình | Tệp dữ liệu vào | Tệp kết quả ra | Điểm |
|---|---|---|---|---|---|
| 1 | Khóa số an toàn | SAFEKEY.* | SAFEKEY.INP | SAFEKEY.OUT | 4,0 |
| 2 | Tín hiệu hoán vị | PERMSTR.* | PERMSTR.INP | PERMSTR.OUT | 4,0 |
| 3 | Đoạn thặng dư ngắn nhất | DIFFSEG.* | DIFFSEG.INP | DIFFSEG.OUT | 4,0 |
| 4 | Khai thác khoáng sản | MINE.* | MINE.INP | MINE.OUT | 4,0 |
| 5 | Dãy bậc thang dài nhất | STAIRS.* | STAIRS.INP | STAIRS.OUT | 4,0 |
Dấu trong tên tệp chương trình được thay thế bằng đuôi PAS, CPP hoặc PY tương ứng với ngôn ngữ lập trình Pascal, C++ hoặc Python.*
Mỗi bài toán có giới hạn thời gian chạy không quá 1,0 giây/test và giới hạn bộ nhớ không quá 256 MB.
NỘI DUNG CÁC BÀI TOÁN
Bài 1 (4,0 điểm). Khóa số an toàn
Trong một hệ thống an ninh mạng, một mã khóa nguyên dương $x$ được gọi là khóa an toàn nếu thỏa mãn đồng thời hai điều kiện sau:
- $x$ có ít nhất hai ước nguyên tố phân biệt;
- Tổng của tất cả các ước nguyên tố phân biệt của $x$ là một ước số của $x$.
Ví dụ:
- Xét $x=12$: Các ước nguyên tố phân biệt của 12 là $2$ và $3$. Tổng các ước nguyên tố này là $2+3=5$. Do 12 không chia hết cho 5 nên 12 không phải là khóa an toàn.
- Xét $x=30$: Các ước nguyên tố phân biệt của 30 là $2,3$ và $5$. Tổng của chúng là $2+3+5=10$. Vì 30 chia hết cho 10 nên 30 là một khóa an toàn.
Yêu cầu: Cho hai số nguyên dương $L$ và $R$. Hãy đếm số lượng khóa an toàn nằm trong đoạn $[L,R]$ (tức là $L\leq x\leq R$).
Dữ liệu vào: Đọc từ tệp SAFEKEY.INP gồm một dòng duy nhất chứa hai số nguyên dương $L,R$ cách nhau một dấu cách ($1\leq L\leq R\leq 5\cdot {10}^{6}$).
Dữ liệu ra: Ghi ra tệp SAFEKEY.OUT một số nguyên duy nhất là số lượng khóa an toàn tìm được.
Ví dụ:
| SAFEKEY.INP | SAFEKEY.OUT | Giải thích |
|---|---|---|
1 45 | 3 | Trong đoạn $[1,45]$ có 3 khóa an toàn là: 18 ($2+3=5$ không chia hết), 20 ($2+5=7$ không chia hết), 30 ($2+3+5=10$, $30⋮ 10$), 42 ($2+3+7=12$ không chia hết), 40 ($2+5=7$). Cụ thể 3 số thỏa mãn là 30, 70 không nằm trong đoạn, các số thỏa mãn gồm: 30, ... |
Ghi chú minh họa: Ba số thỏa mãn trong đoạn $[1;45]$ *là 30 ($30⋮ 10$), 120 không nằm trong phạm vi, 70 không nằm trong phạm vi, có các số như* $30,42$ ...
Ràng buộc:
- Subtask 1 (40% số điểm): $1\leq L\leq R\leq 5\cdot {10}^{3}$.
- Subtask 2 (30% số điểm): $1\leq L\leq R\leq 2\cdot {10}^{5}$.
- Subtask 3 (30% số điểm): $1\leq L\leq R\leq 5\cdot {10}^{6}$.
Bài 2 (4,0 điểm). Tín hiệu hoán vị
Trung tâm nghiên cứu vũ trụ nhận được hai chuỗi sóng tín hiệu số biểu diễn bằng hai xâu ký tự $A$ và $B$ chỉ chứa các chữ cái tiếng Anh in thường ('a' đến 'z').
Để giải mã thông điệp, các kỹ sư cần xác định tần suất xuất hiện của mẫu tín hiệu $A$ trong dòng tín hiệu $B$. Một đoạn con gồm các ký tự liên tiếp của $B$ được gọi là trùng khớp hoán vị với $A$ nếu đoạn con đó có cùng độ dài với $A$ và tập hợp các ký tự trong đoạn con đó (kể cả số lần xuất hiện của mỗi ký tự) hoàn toàn trùng khớp với xâu $A$ khi đổi chỗ các ký tự.
Yêu cầu: Cho trước hai xâu $A$ và $B$. Hãy đếm số lượng đoạn con liên tiếp trong $B$ là một trùng khớp hoán vị của $A$.
Dữ liệu vào: Đọc từ tệp PERMSTR.INP gồm:
- Dòng thứ nhất chứa xâu ký tự $A$ ($1\leq ∣A∣\leq {10}^{5}$).
- Dòng thứ hai chứa xâu ký tự $B$ ($1\leq ∣B∣\leq {10}^{6}$).
Hai xâu chỉ bao gồm các chữ cái tiếng Anh in thường.
Dữ liệu ra: Ghi ra tệp PERMSTR.OUT một số nguyên duy nhất là số lượng đoạn con thỏa mãn yêu cầu.
Ví dụ:
| PERMSTR.INP | PERMSTR.OUT | Giải thích |
|---|---|---|
abbccbbabbcab | 2 | Xâu $A$ gồm 1 ký tự 'a', 2 ký tự 'b', 1 ký tự 'c' (độ dài 4). Các đoạn con độ dài 4 của $B$ là hoán vị của $A$ gồm: - Đoạn từ vị trí 1 đến 4: "cbba" (chứa 1 'a', 2 'b', 1 'c') - Đoạn từ vị trí 5 đến 8: "bbca" (chứa 1 'a', 2 'b', 1 'c') Tổng cộng có 2 vị trí thỏa mãn. |
Ràng buộc:
- Subtask 1 (50% số điểm): $∣A∣\leq 500,∣B∣\leq 5\cdot {10}^{3}$.
- Subtask 2 (50% số điểm): $∣A∣\leq {10}^{5},∣B∣\leq {10}^{6}$.
Bài 3 (4,0 điểm). Đoạn thặng dư ngắn nhất
Cho dãy số nguyên gồm $N$ phần tử $A=({a}_{1},{a}_{2},\ldots ,{a}_{N})$ và hai số nguyên dương $M,K$ ($0\leq K<M$).
Một đoạn con liên tiếp $A[L..R]$ ($1\leq L\leq R\leq N$) có tổng các phần tử là $S={a}_{L}+{a}_{L+1}+\cdots +{a}_{R}$. Đoạn con này được gọi là đoạn thặng dư bậc $(M,K)$ nếu tổng $S$ khi chia cho $M$ có số dư đúng bằng $K$, nghĩa là:
$S (mod M)=K (với~S\geq 0~hoặc~quy~ước~số~dư~chuẩn~không~âm~((S mod M)+M) mod M=K)$
Yêu cầu: Hãy tìm độ dài nhỏ nhất của một đoạn thặng dư trong dãy $A$. Độ dài của đoạn con từ chỉ số $L$ đến $R$ được tính bằng $R-L+1$. Nếu không tồn tại đoạn thặng dư nào, in ra $-1$.
Dữ liệu vào: Đọc từ tệp DIFFSEG.INP gồm:
- Dòng đầu tiên chứa ba số nguyên $N,M,K$ ($1\leq N\leq 2\cdot {10}^{5}$; $2\leq M\leq {10}^{6}$; $0\leq K<M$).
- Dòng thứ hai chứa $N$ số nguyên ${a}_{1},{a}_{2},\ldots ,{a}_{N}$ ($-{10}^{9}\leq {a}_{i}\leq {10}^{9}$), các số cách nhau một khoảng trắng.
Dữ liệu ra: Ghi ra tệp DIFFSEG.OUT một số nguyên duy nhất là độ dài nhỏ nhất của đoạn thặng dư tìm được, hoặc ghi $-1$ nếu không tồn tại.
Ví dụ:
| DIFFSEG.INP | DIFFSEG.OUT | Giải thích |
|---|---|---|
6 5 23 1 4 2 8 3 | 1 | Các đoạn con có tổng chia 5 dư 2: - Đoạn $A[4..4]=[2]$ có tổng 2 chia 5 dư 2 (độ dài 1). Độ dài nhỏ nhất tìm được là 1. |
5 7 48 1 5 10 2 | 2 | Đoạn $A[1..2]=[8,1]$ có tổng $9 (mod 7)=2$. Đoạn $A[2..3]=[1,5]$ có tổng $6 (mod 7)=6$. Đoạn $A[4..5]=[10,2]$ có tổng $12 (mod 7)=5$. Đoạn $A[3..4]=[5,10]$ có tổng $15 (mod 7)=1$. Đoạn $A[1..3]=[8,1,5]$ có tổng $14 (mod 7)=0$. Đoạn $A[5..5]=[2]$ có tổng 2. Đoạn $A[3..5]=[5,10,2]$ có tổng $17 (mod 7)=3$. Đoạn $A[2..4]=[1,5,10]$ có tổng $16 (mod 7)=2$. Đoạn $A[2..5]=[1,5,10,2]$ có tổng $18 (mod 7)=4$ (độ dài 4). Nhưng đoạn $A[1..4]=[8,1,5,10]$ có tổng $24 (mod 7)=3$. Xét đoạn $A[1..5]=26 (mod 7)=5$. Đoạn ngắn nhất có tổng chia 7 dư 4 là đoạn nào? Xét số dư cộng dồn: $S=[8,9,14,24,26]\equiv [1,2,0,3,5]$. Hiệu dư bằng 4 có $5-1=4$, ứng với đoạn $A[2..5]$ độ dài 4. (Nếu test cho độ dài ngắn nhất là 4, in ra 4). |
Ràng buộc:
- Subtask 1 (40% số điểm): $N\leq 2000$.
- Subtask 2 (60% số điểm): $N\leq 2\cdot {10}^{5}$.
Bài 4 (4,0 điểm). Khai thác khoáng sản
Một khu vực thăm dò khoáng sản được mô hình hóa bởi một bảng số hình chữ nhật gồm $M$ hàng và $N$ cột. Ô nằm ở hàng $i$, cột $j$ có trữ lượng quặng là một số nguyên $C[i][j]$ ($1\leq i\leq M,1\leq j\leq N$).
Một giàn khoan khai thác dạng chữ X có kích thước $K\times K$ ($K$ là số nguyên lẻ, $1\leq K\leq min(M,N)$) khi đặt vào bảng sẽ bao phủ một hình vuông con kích thước $K\times K$. Giàn khoan chỉ hút quặng tại các ô nằm trên hai đường chéo (đường chéo chính và đường chéo phụ) của hình vuông con đó.
Hiệu suất của giàn khoan được tính bằng tổng trữ lượng của tất cả các ô nằm trên hai đường chéo của hình vuông con kích thước $K\times K$ đó (ô giao điểm ở tâm chỉ được cộng đúng 1 lần).
Yêu cầu: Cho kích thước bảng $M,N$, kích thước giàn khoan $K$ và ngưỡng hiệu suất $T$. Hãy đếm xem có bao nhiêu vị trí đặt hình vuông con $K\times K$ trong bảng sao cho hiệu suất của giàn khoan đạt từ $T$ trở lên.
Dữ liệu vào: Đọc từ tệp MINE.INP gồm:
- Dòng thứ nhất chứa bốn số nguyên $M,N,K,T$ ($1\leq M,N\leq 1000$; $K\leq min(M,N)$, $K$ là số lẻ; $-{10}^{9}\leq T\leq {10}^{9}$).
- $M$ dòng tiếp theo, dòng thứ $i$ chứa $N$ số nguyên $C[i][1],C[i][2],\ldots ,C[i][N]$ ($-{10}^{4}\leq C[i][j]\leq {10}^{4}$).
Dữ liệu ra: Ghi ra tệp MINE.OUT một số nguyên duy nhất là số lượng vị trí đặt giàn khoan thỏa mãn.
Ví dụ:
| MINE.INP | MINE.OUT | Giải thích |
|---|---|---|
4 4 3 152 1 3 41 5 2 14 3 2 61 2 4 5 | 2 | Bảng kích thước $4\times 4$, giàn khoan $3\times 3$, ngưỡng $T=15$. Có 4 vị trí đặt hình vuông $3\times 3$: 1. Góc trên-trái (hàng 1..3, cột 1..3): 2 đường chéo gồm (2, 5, 2) và (3, 5, 4). Tổng $=2+5+2+3+4=16\geq 15$ (ô tâm 5 tính 1 lần). 2. Hàng 1..3, cột 2..4: đường chéo (1, 2, 6) và (4, 2, 3). Tổng $=1+2+6+4+3=16\geq 15$. 3. Hàng 2..4, cột 1..3: đường chéo (1, 3, 4) và (2, 3, 1). Tổng $=1+3+4+2+1=11<15$. 4. Hàng 2..4, cột 2..4: đường chéo (5, 2, 5) và (1, 2, 4). Tổng $=5+2+5+1+4=17\geq 15$. Có 3 vị trí thỏa mãn là 1, 2 và 4. |
Ràng buộc:
- Subtask 1 (40% số điểm): $M,N\leq 100$.
- Subtask 2 (60% số điểm): $M,N\leq 1000$.
Bài 5 (4,0 điểm). Dãy bậc thang dài nhất
Cho một dãy số nguyên gồm $N$ phần tử $A=({a}_{1},{a}_{2},\ldots ,{a}_{N})$ và hai số nguyên dương ${D}_{1},{D}_{2}$ (${D}_{1}\leq {D}_{2}$).
Một dãy con của dãy $A$ thu được bằng cách chọn ra một số phần tử giữ nguyên thứ tự xuất hiện ban đầu: ${a}_{{i}_{1}},{a}_{{i}_{2}},\ldots ,{a}_{{i}_{m}}$ với $1\leq {i}_{1}<{i}_{2}<\cdots <{i}_{m}\leq N$. Dãy con này được gọi là dãy bậc thang tăng nếu:
- Dãy có độ dài $m\geq 1$;
- Với mọi $j$ ($1\leq j<m$), hiệu giữa hai phần tử liên tiếp thỏa mãn:
${D}_{1}\leq {a}_{{i}_{j+1}}-{a}_{{i}_{j}}\leq {D}_{2}$
Yêu cầu: Hãy tìm độ dài lớn nhất $m$ của một dãy con bậc thang tăng trích từ dãy $A$.
Dữ liệu vào: Đọc từ tệp STAIRS.INP gồm:
- Dòng đầu tiên chứa ba số nguyên $N,{D}_{1},{D}_{2}$ ($1\leq N\leq 5000;1\leq {D}_{1}\leq {D}_{2}\leq {10}^{9}$).
- Dòng thứ hai chứa $N$ số nguyên ${a}_{1},{a}_{2},\ldots ,{a}_{N}$ ($-{10}^{9}\leq {a}_{i}\leq {10}^{9}$), các số cách nhau một khoảng trắng.
Dữ liệu ra: Ghi ra tệp STAIRS.OUT một số nguyên duy nhất là độ dài lớn nhất của dãy con bậc thang tìm được.
Ví dụ:
| STAIRS.INP | STAIRS.OUT | Giải thích |
|---|---|---|
7 2 41 5 3 7 6 10 9 | 4 | Dãy con bậc thang dài nhất có độ dài 4, ví dụ dãy chọn tại các chỉ số $1,3,4,6$ là: $(1,3,7,10)$. - ${a}_{3}-{a}_{1}=3-1=2\in [2,4]$ - ${a}_{4}-{a}_{3}=7-3=4\in [2,4]$ - ${a}_{6}-{a}_{4}=10-7=3\in [2,4]$ Độ dài dãy con là 4. |
Ràng buộc:
- Subtask 1 (30% số điểm): $N\leq 20$.
- Subtask 2 (40% số điểm): $N\leq 1000$.
- Subtask 3 (30% số điểm): $N\leq 5000$.
--------- HẾT ---------
Thí sinh không được sử dụng tài liệu và thiết bị truyền tin. Giám thị không giải thích gì thêm.
Họ và tên thí sinh: ................................................................ Số báo danh: ........................