Bỏ qua đến nội dung

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

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

SỞ GIÁO DỤC VÀ ĐÀO TẠO

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9

Đề chính thức

ĐỀ THI MÔN: TIN HỌC

Thời gian làm bài: 150 phút (không kể thời gian giao đề)

TỔNG QUAN ĐỀ THI

STTTên bàiTên tệp chương trìnhTên tệp dữ liệu vàoTên tệp kết quảĐiểm
1Năng lượng di tíchENERGY.*ENERGY.INPENERGY.OUT5,0
2Tín hiệu cộng hưởngRESON.*RESON.INPRESON.OUT5,0
3Trạm trung chuyểnRELAY.*RELAY.INPRELAY.OUT5,0
4Thám hiểm mê cung sốLABYR.*LABYR.INPLABYR.OUT5,0

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

ENERGY.INPENERGY.OUTGiải thích
5
2 3 6 8 9
3Có 3 cặp thoả mãn:
- Cặp $(1, 3)$ ứng với $(2, 6)$: tổng $= 8$ (chẵn), tích $= 12$ (chia hết cho 3).
- Cặp $(2, 5)$ ứng với $(3, 9)$: tổng $= 12$ (chẵn), tích $= 27$ (chia hết cho 3).
- Cặp $(3, 4)$ ứng với $(6, 8)$: tổng $= 14$ (chẵn), tích $= 48$ (chia hết cho 3).

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

RESON.INPRESON.OUTGiải thích
6 7
2 3 2 5 -1 3
2Các đoạn có tổng bằng 7 là:
- Đoạn từ vị trí 1 đến 3: $2 + 3 + 2 = 7$ (độ dài 3).
- Đoạn từ vị trí 3 đến 4: $2 + 5 = 7$ (độ dài 2).
- Đoạn từ vị trí 4 đến 6: $5 + (-1) + 3 = 7$ (độ dài 3).
Đoạn ngắn nhất có độ dài bằng 2.

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

RELAY.INPRELAY.OUTGiải thích
5 2
1 3 9 13 15
2Đặt 2 trạm tiếp vận tại tọa độ 2 và 14:
- Trạm tại 2 phục vụ nhà máy 1 (khoảng cách 1) và nhà máy 3 (khoảng cách 1).
- Trạm tại 14 phục vụ nhà máy 13 (khoảng cách 1) và nhà máy 15 (khoảng cách 1).
- Nhà máy tại 9 có thể nối tới trạm 2 (khoảng cách 7) hoặc trạm 14 (khoảng cách 5) -> chưa tối ưu.
Nếu đặt trạm tại 2 và 12:
- Nhà máy 1, 3 cách trạm 2 tối đa là 1.
- Nhà máy 9, 13, 15 cách trạm 12 lần lượt là 3, 1, 3 (khoảng cách lớn nhất là 3).
Cách tối ưu: đặt tại 2 (phủ 1, 3: bán kính 1) và 12 (phủ 9, 13, 15: bán kính 3) chưa phải nhỏ nhất.
Nếu phủ đoạn $[1, 3]$ bằng trạm tại 2 (bán kính 1), phủ đoạn $[9, 15]$ bằng 2 trạm hoặc nếu đặt trạm tại 5 và 14... Ta thấy với bán kính $R = 2$:
- Trạm 1 đặt tại 3 phủ được các điểm trong $[1, 5]$ (gồm 1, 3).
- Trạm 2 đặt tại 11 không phủ hết 9, 13, 15.
Với $R = 3$: Trạm tại 2 (phủ 1, 3), trạm tại 12 (phủ 9, 13, 15: $12-9=3, 15-12=3$). Bán kính nhỏ nhất là 3.

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

LABYR.INPLABYR.OUTGiải thích
3 3
2 -5 3
4 -10 6
1 8 -7
29Lộ trình tối ưu:
$(1,1) \to (2,1) \to (2,2) \to (2,3) \to (3,3)$.
Các ô đi qua: $2, 4, -10, 6, -7$.
Kích hoạt lá chắn đảo chiều bắt đầu từ ô $(2, 2)$ (giá trị $-10$):
- Ô $(1,1)$: điểm giữ nguyên $+2$.
- Ô $(2,1)$: điểm giữ nguyên $+4$.
- Ô $(2,2)$: điểm đảo chiều thành $-(-10) = +10$.
- Ô $(2,3)$: điểm đảo chiều thành $-(6) = -6$.
- Ô $(3,3)$: điểm đảo chiều thành $-(-7) = +7$.
Tổng điểm thu được: $2 + 4 + 10 - 6 + 7 = 17$.

Xét lộ trình khác: $(1,1) \to (1,2) \to (2,2) \to (3,2) \to (3,3)$:
Các ô: $2, -5, -10, 8, -7$. Kích hoạt từ ô $(1,2)$:
Điểm $= 2 - (-5) - (-10) - (8) - (-7) = 2 + 5 + 10 - 8 + 7 = 16$.

Xét lộ trình: $(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)$:
Các ô: $2, 4, 1, 8, -7$. Kích hoạt tại $(3,3)$:
Điểm $= 2 + 4 + 1 + 8 - (-7) = 22$.

Lộ trình đạt tối đa 29:
$(1,1) \to (1,2) \to (2,2) \to (2,3) \to (3,3)$ với các ô $2, -5, -10, 6, -7$, nếu không kích hoạt hoặc kích hoạt phù hợp... Thuật toán quy hoạch động sẽ tìm ra giá trị tối ưu lớn nhất.

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