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

TỔNG QUAN ĐỀ THI

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;

2. 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ụ:

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ụ:

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ụ:

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ụ:

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$;

2. 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ụ:

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: ........................