Đề thi Chọn Học sinh giỏi lớp 9 môn Tin học

TỔNG QUAN ĐỀ THI

Ghi chú: Thí sinh nộp tệp chương trình có phần mở rộng `.cpp` hoặc `.py` hoặc `.pas` tương ứng với ngôn ngữ dự thi.

BÀI 1. NĂNG LƯỢNG DI TÍCH (5,0 điểm)

Trong một cuộc khảo sát cổ vật, các nhà khảo cổ phát hiện một tấm bia đá chứa một dãy số nguyên dương gồm $N$ phiến đá xếp thành hàng ngang, phiến đá thứ $i$ mang chỉ số năng lượng $A_i$ ($1 \le i \le N$).

Người ta định nghĩa một cặp phiến đá $(i, j)$ với $1 \le i < j \le N$ tạo thành một "Cặp cộng hưởng hài hoà" nếu thỏa mãn đồng thời hai điều kiện sau:
- Tổng năng lượng của hai phiến đá là một số chẵn: $(A_i + A_j) \bmod 2 = 0$.
- Tích năng lượng của hai phiến đá chia hết cho $3$: $(A_i \times A_j) \bmod 3 = 0$.

Yêu cầu: Hãy đếm số lượng cặp $(i, j)$ ($1 \le i < j \le N$) tạo thành một cặp cộng hưởng hài hoà.

Dữ liệu vào (ENERGY.INP):
- Dòng đầu tiên chứa số nguyên dương $N$.
- Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \ldots, A_N$ được ngăn cách nhau bởi dấu cách.

Dữ liệu ra (ENERGY.OUT):
- Ghi ra một số nguyên duy nhất là số lượng cặp cộng hưởng hài hoà tìm được.

Ràng buộc:
- Subtask 1 (40% số điểm): $N \le 2\,000$; $A_i \le 10^6$.
- Subtask 2 (60% số điểm): $N \le 2 \times 10^5$; $A_i \le 10^9$.

Ví dụ:

BÀI 2. TÍN HIỆU CỘNG HƯỞNG (5,0 điểm)

Một đài thiên văn thu được một dãy tín hiệu liên tục gồm $N$ xung sóng, mỗi xung sóng được biểu diễn bởi một số nguyên $B_i$ ($1 \le i \le N$).

Các nhà khoa học quan tâm đến các đoạn tín hiệu liên tiếp $B[L \dots R] = (B_L, B_{L+1}, \ldots, B_R)$ ($1 \le L \le R \le N$) có tổng các phần tử đúng bằng một số nguyên $K$ cho trước. Trong số tất cả các đoạn liên tiếp có tổng bằng $K$, đoạn tín hiệu có độ dài ngắn nhất được gọi là "tín hiệu cô đọng".

Yêu cầu: Tìm độ dài của đoạn tín hiệu liên tiếp ngắn nhất có tổng các phần tử bằng $K$. Nếu không tồn tại đoạn tín hiệu nào có tổng bằng $K$, in ra $-1$.

Dữ liệu vào (RESON.INP):
- Dòng đầu chứa hai số nguyên $N$ và $K$.
- Dòng thứ hai chứa $N$ số nguyên $B_1, B_2, \ldots, B_N$ cách nhau bởi dấu cách.

Dữ liệu ra (RESON.OUT):
- Ghi ra một số nguyên duy nhất là độ dài nhỏ nhất của đoạn tín hiệu tìm được, hoặc $-1$ nếu không tồn tại.

Ràng buộc:
- Subtask 1 (30% số điểm): $1 \le N \le 500$; $|B_i|, |K| \le 10^4$.
- Subtask 2 (30% số điểm): $1 \le N \le 5\,000$; $|B_i|, |K| \le 10^9$.
- Subtask 3 (40% số điểm): $1 \le N \le 2 \times 10^5$; $|B_i| \le 10^9$; $|K| \le 10^{14}$.

Ví dụ:

BÀI 3. TRẠM TRUNG CHUYỂN (5,0 điểm)

Dọc theo một tuyến đường cao tốc thẳng tắp dài vô tận, có $N$ nhà máy sản xuất linh kiện đặt tại các tọa độ $X_1, X_2, \ldots, X_N$ (các tọa độ là số nguyên đôi một phân biệt).

Để giảm thiểu chi phí phát thải khí nhà kính, công ty logistics cần đặt đúng $K$ trạm tiếp vận năng lượng sạch tại $K$ vị trí trên tuyến cao tốc này (tọa độ các trạm tiếp vận phải là các số nguyên, không nhất thiết trùng với vị trí các nhà máy, nhưng có thể trùng nhau nếu cần).

Mỗi nhà máy sẽ tự động kết nối với trạm tiếp vận gần nó nhất. Khoảng cách kết nối của nhà máy thứ $i$ được tính bằng $|X_i - P_j|$, trong đó $P_j$ là tọa độ trạm tiếp vận gần nhà máy đó nhất. Gọi khoảng cách kết nối tối đa của hệ thống là giá trị lớn nhất trong số các khoảng cách kết nối của $N$ nhà máy tới trạm tiếp vận gần nhất của chúng.

Yêu cầu: Hãy xác định vị trí đặt $K$ trạm tiếp vận sao cho khoảng cách kết nối tối đa là nhỏ nhất có thể, và in ra giá trị nhỏ nhất đó.

Dữ liệu vào (RELAY.INP):
- Dòng đầu chứa hai số nguyên dương $N$ và $K$ ($1 \le K \le N$).
- Dòng thứ hai chứa $N$ số nguyên $X_1, X_2, \ldots, X_N$ ($|X_i| \le 10^9$).

Dữ liệu ra (RELAY.OUT):
- Ghi ra một số nguyên duy nhất là khoảng cách kết nối tối đa nhỏ nhất đạt được.

Ràng buộc:
- Subtask 1 (30% số điểm): $K = 1$; $N \le 1\,000$.
- Subtask 2 (40% số điểm): $1 \le K \le N \le 2\,000$; $|X_i| \le 10^6$.
- Subtask 3 (30% số điểm): $1 \le K \le N \le 2 \times 10^5$; $|X_i| \le 10^9$.

Ví dụ:

BÀI 4. THÁM HIỂM MÊ CUNG SỐ (5,0 điểm)

Một nhà du hành được đưa vào một ma trận số nguyên kích thước $M \times N$ gồm $M$ hàng (đánh số từ 1 đến $M$ từ trên xuống dưới) và $N$ cột (đánh số từ 1 đến $N$ từ trái sang phải). Ô ở hàng $i$, cột $j$ có giá trị điểm số là $C_{i, j}$ ($C_{i, j}$ có thể mang giá trị âm, dương hoặc bằng 0).

Nhà du hành xuất phát từ ô $(1, 1)$ và cần di chuyển đến ô đích $(M, N)$. Tại mỗi ô $(i, j)$, nhà du hành chỉ được phép di chuyển sang một trong hai ô kề cạnh:
- Đi sang phải đến ô $(i, j + 1)$ (nếu $j < N$).
- Đi xuống dưới đến ô $(i + 1, j)$ (nếu $i < M$).

Tuy nhiên, mê cung có một quy tắc cân bằng năng lượng: Trong suốt toàn bộ lộ trình từ $(1, 1)$ đến $(M, N)$, nhà du hành được kích hoạt một "Lá chắn đảo chiều" không quá một lần. Khi kích hoạt lá chắn tại một ô bất kỳ trên đường đi (có thể là ô $(1, 1)$ hoặc ô $(M, N)$ hoặc bất kỳ ô trung gian nào), toàn bộ điểm số của các ô mà nhà du hành bước vào kể từ thời điểm kích hoạt lá chắn trở về sau (tính cả ô được kích hoạt) sẽ được nhân với $-1$ khi cộng vào tổng điểm.

Yêu cầu: Hãy tìm lộ trình hợp lệ từ ô $(1, 1)$ đến ô $(M, N)$ sao cho tổng điểm thu được là lớn nhất có thể.

Dữ liệu vào (LABYR.INP):
- Dòng đầu chứa hai số nguyên dương $M$ và $N$.
- $M$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên mô tả bảng điểm $C_{i, j}$ ($-10^6 \le C_{i, j} \le 10^6$).

Dữ liệu ra (LABYR.OUT):
- Ghi ra một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Ràng buộc:
- Subtask 1 (30% số điểm): $1 \le M, N \le 15$.
- Subtask 2 (30% số điểm): $1 \le M, N \le 200$; $C_{i, j} \ge 0$.
- Subtask 3 (40% số điểm): $1 \le M, N \le 1\,000$; $-10^6 \le C_{i, j} \le 10^6$.

Ví dụ:

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