Bỏ qua đến nội dung

de-thi-hoc-sinh-gioi-mon-tin-hoc-8-nam-hoc-2026-2027

Chia sẻ bởi Cộng đồng Edubox · 0 lượt sử dụng

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àiTên bàiTệp chương trìnhTệp dữ liệu vàoTệp kết quả raĐiểm
1Khóa số an toànSAFEKEY.*SAFEKEY.INPSAFEKEY.OUT4,0
2Tín hiệu hoán vịPERMSTR.*PERMSTR.INPPERMSTR.OUT4,0
3Đoạn thặng dư ngắn nhấtDIFFSEG.*DIFFSEG.INPDIFFSEG.OUT4,0
4Khai thác khoáng sảnMINE.*MINE.INPMINE.OUT4,0
5Dãy bậc thang dài nhấtSTAIRS.*STAIRS.INPSTAIRS.OUT4,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:

  1. $x$ có ít nhất hai ước nguyên tố phân biệt;
  1. 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.INPSAFEKEY.OUTGiải thích
1 453Trong đ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.INPPERMSTR.OUTGiải thích
abbc
cbbabbcab
2Xâ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.INPDIFFSEG.OUTGiải thích
6 5 2
3 1 4 2 8 3
1Cá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 4
8 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.INPMINE.OUTGiải thích
4 4 3 15
2 1 3 4
1 5 2 1
4 3 2 6
1 2 4 5
2Bả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:

  1. Dãy có độ dài $m\geq 1$;
  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.INPSTAIRS.OUTGiải thích
7 2 4
1 5 3 7 6 10 9
4Dã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: ........................