ĐỀ THI CHỌN ĐỘI TUYỂN QUỐC GIA DỰ THI HSGQG NĂM HỌC 2027 - 2028 - MÔN TIN HỌC

TỔNG QUAN ĐỀ THI

Dấu `*` trong tệp chương trình được thay thế bằng đuôi `cpp` hoặc `pas` tùy theo ngôn ngữ lập trình sử dụng (`C++` hoặc `Pascal`).

BÀI 1. ĐOẠN SỐ SIÊU CHÍNH PHƯƠNG (6,0 điểm)

Tên tệp chương trình: `SPQRT.*`
Tệp dữ liệu vào: `SPQRT.INP`
Tệp kết quả: `SPQRT.OUT`

Một số nguyên dương $x$ được gọi là số chính phương nếu $x$ là bình phương của một số nguyên ($x = k^2$ với $k \in \mathbb{Z}^+$). Trong số học, một số nguyên dương $p$ lớn hơn $1$ được gọi là số nguyên tố nếu nó chỉ có đúng hai ước nguyên dương là $1$ và chính nó.

Một số nguyên dương $x$ được gọi là số siêu chính phương nếu $x$ là bình phương của một số nguyên tố, nghĩa là tồn tại số nguyên tố $p$ sao cho:

$$x = p^2$$

Ví dụ: $4 = 2^2$, $9 = 3^2$, $25 = 5^2$, $49 = 7^2$ là các số siêu chính phương; trong khi $1$, $16 = 4^2$, $36 = 6^2$ không phải là số siêu chính phương.

Cho một dãy số nguyên $A = (a_1, a_2, \dots, a_n)$ gồm $n$ phần tử ($a_i$ có thể âm, dương hoặc bằng $0$). Một đoạn con liên tiếp $A[l..r] = (a_l, a_{l+1}, \dots, a_r)$ ($1 \le l \le r \le n$) được gọi là đoạn siêu chính phương nếu tích của tất cả các phần tử trong đoạn:

$$P(l, r) = \prod_{i=l}^r a_i = a_l \times a_{l+1} \times \dots \times a_r$$

là một số siêu chính phương.

Yêu cầu

1. Tìm độ dài lớn nhất của một đoạn con siêu chính phương trong dãy $A$.
2. Đếm số lượng đoạn con có độ dài lớn nhất đó.
(Nếu trong dãy không tồn tại bất kỳ đoạn con siêu chính phương nào, quy ước cả hai giá trị cần tìm đều bằng $0$).

Dữ liệu vào

- Dòng đầu tiên chứa số nguyên dương $n$ ($1 \le n \le 2 \times 10^5$) — số lượng phần tử của dãy số.
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($-10^6 \le a_i \le 10^6$), mỗi số cách nhau một khoảng trắng.

Kết quả ra

- Gồm hai số nguyên ghi trên một dòng (hoặc hai dòng):
- Giá trị thứ nhất là độ dài lớn nhất của đoạn con siêu chính phương tìm được.
- Giá trị thứ hai là số lượng đoạn con đạt độ dài lớn nhất đó.

Ví dụ

Ràng buộc và Subtasks

- Subtask 1 (20% số điểm): $n \le 200$; $-100 \le a_i \le 100$.
- Subtask 2 (30% số điểm): $n \le 3000$; $|a_i| \le 10^4$.
- Subtask 3 (25% số điểm): $n \le 10^5$; $a_i \ge 1$ với mọi $i$.
- Subtask 4 (25% số điểm): $n \le 2 \times 10^5$; $-10^6 \le a_i \le 10^6$.

BÀI 2. VIRUS MÁY TÍNH (7,0 điểm)

Tên tệp chương trình: `VIRUS.*`
Tệp dữ liệu vào: `VIRUS.INP`
Tệp kết quả: `VIRUS.OUT`

Hệ thống mạng máy tính của Sở Giáo dục và Đào tạo gồm $n$ máy tính được đánh số từ $1$ đến $n$. Toàn bộ hệ thống liên kết theo cấu trúc đồ thị dạng cây có gốc tại máy chủ trung tâm quản trị là máy $1$. Mỗi máy tính $i$ ($2 \le i \le n$) được kết nối trực tiếp với máy tính quản lý cấp trên (máy cha) là $p_i$.

Duy Khánh muốn tìm lại bài thi của mình đang được lưu trữ tại một máy tính nào đó trong hệ thống. Để làm điều này, Duy Khánh phát tán một mã độc (virus) có khả năng tự động lây nhiễm. Tuy nhiên, Sở GD&ĐT đã chủ động thiết lập các biện pháp an ninh mạng để ngăn chặn:
- Ban đầu, Sở đã kích hoạt chương trình phòng thủ tại một tập gồm $k$ máy tính $D = \{d_1, d_2, \dots, d_k\}$. Khi một máy tính đang được bảo vệ, virus hoàn toàn không thể xâm nhập vào máy tính đó và cũng không thể lan truyền qua máy tính đó.
- Virus của Duy Khánh lây lan âm thầm theo các máy con hoặc lan tỏa cục bộ.

Hệ thống liên tục ghi nhận $q$ sự kiện/truy vấn diễn ra theo thứ tự thời gian, thuộc một trong bốn loại sau:
- Loại 1 (`1 v`): Duy Khánh tấn công vào máy $v$.
- Nếu máy $v$ chưa có chương trình bảo vệ và chưa bị nhiễm virus: máy $v$ lập tức bị nhiễm virus.
- Nếu máy $v$ đã bị nhiễm virus từ trước: virus sẽ lập tức lan truyền xuống tất cả các máy con trực tiếp của $v$ (ngoại trừ các máy con đang có chương trình bảo vệ).
- Loại 2 (`2 u`): Sở GD&ĐT tăng cường an ninh, kích hoạt chương trình bảo vệ tại máy $u$. Kể từ thời điểm này, máy $u$ được bảo vệ (nếu máy $u$ đã bị nhiễm virus trước đó thì virus tại $u$ bị phong tỏa, không thể phát tán đi tiếp).
- Loại 3 (`3 u`): Hệ thống cảnh báo tự động: chương trình bảo vệ tại máy $u$ được đẩy ngược lên máy cha trực tiếp của $u$ (tức máy $p_u$). Máy $p_u$ lập tức được kích hoạt bảo vệ.
- Loại 4 (`4 u`): Kiểm tra tình trạng dữ liệu: Giả sử bài thi của Duy Khánh đang nằm tại máy $u$, hãy xác định xem máy $u$ hiện tại có đang bị virus xâm nhập hay không? In ra `YES` nếu máy $u$ đã bị nhiễm virus, ngược lại in ra `NO`.

Yêu cầu

Hãy viết chương trình mô phỏng quá trình lây lan của virus và phản hồi kết quả cho tất cả các truy vấn loại 4.

Dữ liệu vào

- Dòng đầu tiên chứa ba số nguyên dương $n, q, k$ ($1 \le k \le n \le 10^5; 1 \le q \le 10^5$) — số lượng máy tính, số lượng truy vấn và số lượng máy tính ban đầu có bảo vệ.
- Dòng thứ hai chứa $n - 1$ số nguyên $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$) mô tả máy cha của từng máy từ $2$ đến $n$.
- Dòng thứ ba chứa $k$ số nguyên phân biệt $d_1, d_2, \dots, d_k$ ($1 \le d_i \le n$) — danh sách các máy ban đầu được cài đặt chương trình bảo vệ.
- Trong $q$ dòng tiếp theo, mỗi dòng mô tả một sự kiện theo một trong các định dạng:
- `1 v`: Duy Khánh tấn công máy $v$ ($1 \le v \le n$).
- `2 u`: Cài đặt bảo vệ tại máy $u$ ($1 \le u \le n$).
- `3 u`: Đẩy tín hiệu bảo vệ lên máy cha của $u$ ($2 \le u \le n$).
- `4 u`: Kiểm tra trạng thái máy $u$ ($1 \le u \le n$).

Kết quả ra

- Với mỗi truy vấn loại 4, in ra trên một dòng xâu `YES` nếu máy tính đang bị virus xâm nhập, hoặc `NO` nếu máy tính an toàn.

Ví dụ

Ràng buộc và Subtasks

- Subtask 1 (15% số điểm): $n, q \le 1000$; cây có dạng đường thẳng ($p_i = i - 1$).
- Subtask 2 (20% số điểm): $n, q \le 2000$; không có truy vấn loại 2 và loại 3.
- Subtask 3 (25% số điểm): $n, q \le 10^5$; cây có độ cao không quá $20$.
- Subtask 4 (40% số điểm): $n, q \le 10^5$; không có ràng buộc gì thêm.

BÀI 3. THAO TÁC DÃY SỐ (7,0 điểm)

Tên tệp chương trình: `THAOTAC.*`
Tệp dữ liệu vào: `THAOTAC.INP`
Tệp kết quả: `THAOTAC.OUT`

Cho một dãy số nguyên dương $A = (a_1, a_2, \dots, a_n)$ gồm $n$ phần tử. Bạn Minh cần thực hiện $q$ truy vấn, mỗi truy vấn được cho bởi một đoạn chỉ số $[l, r]$ ($1 \le l \le r \le n$).

Với mỗi đoạn $[l, r]$, Minh cần tính tổng của tất cả các giá trị $a_i \bmod a_j$ (phần dư khi chia $a_i$ cho $a_j$) với mọi cặp chỉ số $(i, j)$ thỏa mãn $l \le i, j \le r$. Nói cách khác, giá trị cần tính trong mỗi truy vấn là:

$$F(l, r) = \sum_{i=l}^r \sum_{j=l}^r (a_i \bmod a_j)$$

Lưu ý: Với các cặp mà $i = j$, ta có $a_i \bmod a_i = 0$.

Yêu cầu

Hãy viết chương trình tính giá trị $F(l, r)$ cho mỗi truy vấn của bạn Minh. Vì kết quả có thể rất lớn, hãy in ra giá trị chính xác theo định dạng số nguyên 64-bit (`long long` trong C++).

Dữ liệu vào

- Dòng đầu tiên chứa hai số nguyên dương $n$ và $q$ ($1 \le n \le 10^5; 1 \le q \le 10^5$) — số phần tử của dãy số và số lượng truy vấn.
- Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \times 10^5$), các số cách nhau một khoảng trắng.
- Trong $q$ dòng tiếp theo, mỗi dòng chứa một cặp số nguyên $l, r$ ($1 \le l \le r \le n$) mô tả một truy vấn.

Kết quả ra

- Ghi ra tệp `THAOTAC.OUT` gồm $q$ dòng, mỗi dòng chứa một số nguyên duy nhất là kết quả $F(l, r)$ của truy vấn tương ứng.

Ví dụ

Ràng buộc và Subtasks

- Subtask 1 (15% số điểm): $n, q \le 300$.
- Subtask 2 (20% số điểm): $n, q \le 3000$.
- Subtask 3 (25% số điểm): $n, q \le 5 \times 10^4$; $a_i \le 1000$ với mọi $i$.
- Subtask 4 (40% số điểm): $n \le 10^5; q \le 10^5; a_i \le 2 \times 10^5$.

--------- HẾT ---------

Họ và tên thí sinh: ................................................................ Số báo danh: ........................

Cán bộ coi thi không giải thích gì thêm.