ĐỀ THI HỌC SINH GIỎI CẤP TỈNH MÔN TIN HỌC LỚP 9

Cán bộ coi thi không giải thích gì thêm. Thí sinh làm bài bằng ngôn ngữ C++, Pascal hoặc Python.
Tên file mã nguồn được đặt theo quy định: `BAI1.`, `BAI2.`, `BAI3.`, `BAI4.` (với `` là `cpp`, `pas` hoặc `py`).*

TỔNG QUAN ĐỀ THI

Bài 1. Khôi phục cổ vật (5,0 điểm)

Trong một cuộc khai quật khảo cổ học tại thung lũng cổ, các nhà khoa học đã tìm thấy một phiến đá khắc một dãy gồm $N$ số nguyên dương $A = (a_1, a_2, \ldots, a_N)$.

Theo văn tự cổ, hai phiến số tại vị trí $i$ và $j$ ($1 \le i < j \le N$) có thể kết hợp với nhau để kích hoạt một cổ vật phong ấn nếu thỏa mãn đồng thời hai điều kiện sau:
1. Tích của hai số là một số chính phương (nghĩa là $a_i \times a_j = k^2$ với $k$ là một số nguyên dương).
2. Tổng của hai số chia hết cho $3$ (nghĩa là $(a_i + a_j) \ \vdots \ 3$).

Yêu cầu: Hãy đếm số lượng cặp chỉ số $(i, j)$ với $1 \le i < j \le N$ thỏa mãn cả hai điều kiện trên.

Dữ liệu vào

- Dòng thứ nhất ghi số nguyên dương $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai ghi $N$ số nguyên dương $a_1, a_2, \ldots, a_N$ ($1 \le a_i \le 10^6$) cách nhau bởi dấu cách.

Kết quả ra

Ghi ra một số nguyên duy nhất là số lượng cặp cổ vật ghép nối thành công.

Giới hạn

- Có $40\%$ số test tương ứng với $40\%$ số điểm: $N \le 1000$ và $a_i \le 10^4$.
- Có $30\%$ số test tương ứng với $30\%$ số điểm: $N \le 10^5$ và $a_i \le 1000$.
- Có $30\%$ số test còn lại tương ứng với $30\%$ số điểm: $N \le 10^5$ và $a_i \le 10^6$.

Ví dụ

Bài 2. Mật ngữ rừng sâu (5,0 điểm)

Một đoàn thám hiểm lạc vào một khu rừng nguyên sinh và tìm thấy một cuộn giấy da cổ ghi lại một chuỗi ký tự $S$ chỉ gồm các chữ cái tiếng Anh in thường (`'a'` đến `'z'`).

Để tìm được lối ra, đoàn thám hiểm phải giải mã được "chỉ dẫn dẫn đường". Một đoạn con liên tiếp của chuỗi $S$ được gọi là một chỉ dẫn hợp lệ nếu thỏa mãn:
- Số lượng chữ cái nguyên âm bằng đúng số lượng chữ cái phụ âm trong đoạn đó (các chữ cái nguyên âm gồm năm ký tự: `'a'`, `'e'`, `'i'`, `'o'`, `'u'`; các chữ cái còn lại trong bảng chữ cái tiếng Anh đều là phụ âm).
- Độ dài của đoạn con đó phải đạt tối thiểu là $K$.

Yêu cầu: Hãy tìm độ dài lớn nhất của một chỉ dẫn hợp lệ trong chuỗi $S$. Nếu không tồn tại chỉ dẫn hợp lệ nào, hãy in ra $0$.

Dữ liệu vào

- Dòng thứ nhất ghi số nguyên dương $K$ ($1 \le K \le |S|$).
- Dòng thứ hai chứa xâu ký tự $S$ ($1 \le |S| \le 10^5$) chỉ gồm các chữ cái tiếng Anh in thường.

Kết quả ra

Ghi ra một số nguyên duy nhất là độ dài của đoạn con thỏa mãn dài nhất, hoặc ghi $0$ nếu không có đoạn con nào thỏa mãn.

Giới hạn

- Có $40\%$ số test tương ứng với $40\%$ số điểm: $|S| \le 1000$.
- Có $30\%$ số test tương ứng với $30\%$ số điểm: $|S| \le 10^5$ và $K = 2$.
- Có $30\%$ số test còn lại tương ứng với $30\%$ số điểm: $|S| \le 10^5$ và $1 \le K \le |S|$.

Ví dụ

Bài 3. Trạm năng lượng xanh (5,0 điểm)

Dọc theo một tuyến đường cao tốc thông minh dài xuyên tỉnh, có $N$ khu đô thị sinh thái được đánh số từ $1$ đến $N$. Khu đô thị thứ $i$ nằm tại tọa độ $x_i$ km tính từ điểm đầu của tuyến đường ($0 \le x_1 < x_2 < \ldots < x_N$).

Chính quyền tỉnh quyết định đầu tư hệ thống trạm sạc điện siêu nhanh cho các phương tiện giao thông. Do ngân sách dự án, tỉnh sẽ chọn đúng $K$ khu đô thị trong số $N$ khu đô thị trên để xây dựng trạm sạc ($2 \le K \le N$). Để phục vụ người dân ở hai đầu tuyến đường, khu đô thị đầu tiên ($x_1$) và khu đô thị cuối cùng ($x_N$) bắt buộc phải được chọn.

Để phân bổ mạng lưới năng lượng đồng đều và hạn chế hiện tượng các trạm sạc đặt quá sát nhau gây lãng phí hạ tầng, ban quản lý dự án muốn lựa chọn vị trí cho $K$ trạm sạc sao cho khoảng cách ngắn nhất giữa hai trạm sạc liên tiếp bất kỳ là lớn nhất có thể.

Yêu cầu: Hãy xác định khoảng cách ngắn nhất lớn nhất đó.

Dữ liệu vào

- Dòng thứ nhất ghi hai số nguyên dương $N$ và $K$ ($2 \le K \le N \le 10^5$).
- Dòng thứ hai ghi $N$ số nguyên không âm $x_1, x_2, \ldots, x_N$ ($0 \le x_i \le 10^9$, $x_1 < x_2 < \ldots < x_N$) cách nhau bởi dấu cách.

Kết quả ra

Ghi ra một số nguyên duy nhất là giá trị khoảng cách ngắn nhất lớn nhất tìm được.

Giới hạn

- Có $40\%$ số test tương ứng với $40\%$ số điểm: $N \le 1000$ và $x_N \le 10^5$.
- Có $30\%$ số test tương ứng với $30\%$ số điểm: $N \le 10^5$ và $K = 3$.
- Có $30\%$ số test còn lại tương ứng với $30\%$ số điểm: $N \le 10^5$, $K \le N$ và $x_i \le 10^9$.

Ví dụ

Bài 4. Liên minh vương quốc (5,0 điểm)

Trong một lục địa giả tưởng, có $N$ vương quốc nằm liên tiếp nhau trên một dải đất ven biển được đánh số thứ tự từ $1$ đến $N$. Vương quốc thứ $i$ có chỉ số sức mạnh kinh tế là $A_i$.

Để ký kết hiệp ước hòa bình và tránh xung đột vũ trang, các vị vua quyết định chia toàn bộ $N$ vương quốc này thành một số liên minh độc lập. Việc phân chia phải thỏa mãn các nguyên tắc nghiêm ngặt:
- Mỗi liên minh là một đoạn các vương quốc nằm liên tiếp nhau từ vị trí $i$ đến vị trí $j$ ($1 \le i \le j \le N$).
- Mỗi vương quốc thuộc về đúng một liên minh.
- Trong mỗi liên minh, để tránh việc vương quốc quá giàu áp bức vương quốc quá nghèo, chênh lệch giữa vương quốc có sức mạnh lớn nhất và vương quốc có sức mạnh nhỏ nhất không được vượt quá ngưỡng cân bằng $D$, nghĩa là:

$$\max_{i \le k \le j} (A_k) - \min_{i \le k \le j} (A_k) \le D$$

Để cấu trúc liên minh không bị phân mảnh, hội đồng muốn chia thành số lượng liên minh ít nhất có thể.

Yêu cầu: Hãy xác định:
1. Số lượng liên minh ít nhất cần chia.
2. Số cách chia thỏa mãn đạt được số lượng liên minh ít nhất đó (vì số cách có thể rất lớn, hãy in kết quả theo modulo $10^9 + 7$).

Dữ liệu vào

- Dòng thứ nhất ghi hai số nguyên dương $N$ và $D$ ($1 \le N \le 10^5$, $0 \le D \le 10^9$).
- Dòng thứ hai ghi $N$ số nguyên không âm $A_1, A_2, \ldots, A_N$ ($0 \le A_i \le 10^9$) cách nhau bởi dấu cách.

Kết quả ra

Ghi ra trên một dòng hai số nguyên cách nhau một dấu cách lần lượt là số lượng liên minh ít nhất và số cách chia đạt số liên minh ít nhất đó (chia lấy dư cho $10^9 + 7$).

Giới hạn

- Có $40\%$ số test tương ứng với $40\%$ số điểm: $N \le 1000$ và $D \le 10^6$.
- Có $30\%$ số test tương ứng với $30\%$ số điểm: $N \le 10^5$ và chỉ yêu cầu đưa ra số lượng liên minh ít nhất (thí sinh in số cách tùy ý vẫn được trọn điểm phần này).
- Có $30\%$ số test còn lại tương ứng với $30\%$ số điểm: $N \le 10^5$, $0 \le D \le 10^9$ và $0 \le A_i \le 10^9$.

Ví dụ

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

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