Học sinh giỏi lớp 9 thành phố Hải Phòng 2025-2026

Một số nguyên dương \(x\) được gọi là đẹp nếu như nó chia hết cho \(5\) và tổng các chữ số của nó cũng chia hết cho \(5\).

Yêu cầu: Cho dãy \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Hãy đếm xem có bao nhiêu số đẹp trong dãy trên.

Input

• Dòng đầu chứa số nguyên dương \(n\)
• Tiếp theo là \(n\) dòng, dòng thứ \(i\) (\(i = 1,2,\ldots,n\)) chứa số nguyên dương \(a_i\)
• Tổng số lượng các chữ số của \(a_1, a_2, \ldots, a_n\) không vượt quá \(10^6\)

Output

• In ra màn hình một số nguyên duy nhất là số lượng số đẹp trong dãy số đã cho.

Scoring

• Có \(80\%\) số test ứng với \(80\%\) số điểm của bài thỏa mãn \(a_i \leq 10^9\)
• Các test còn lại không có ràng buộc bổ sung

Example

5
15
50
140
25
10

2

Sau \(n\) bài kiểm tra, điểm của Dũng được ghi lại thành dãy số nguyên \(a_1, a_2, \ldots, a_n\). Điểm này có thể âm (tương ứng với điểm phạt) nếu như lần kiểm tra đó Dũng gian lận hoặc sử dụng chat GPT. Thầy giáo muốn biết "giai đoạn tiến bộ nhất" mà Dũng thực hiện được, giai đoạn này là dãy các bài kiểm tra liên tiếp của Dũng có tổng điểm lớn nhất.

Yêu cầu: Hãy xác định tổng điểm của "giai đoạn tiến bộ nhất" mà Dũng thực hiện được.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 10^6)\)
• Dòng thứ hai chứa \(n\) số nguyên lần lượt là \(a_1, a_2, \ldots, a_n\) \((|a_i| \leq 10^9\) với mọi \(i = 1,2,\ldots,n)\). Hai số liên tiếp cách nhau bằng khoảng trống (space)

Output

• In ra màn hình một số nguyên duy nhất là kết quả tìm được.

Scoring

• Có \(50\%\) số tests ứng với \(50\%\) số điểm của bài có \(n \leq 500\)
• \(30\%\) số tests tiếp theo ứng với \(30\%\) số điểm của bài có \(n \leq 5000\)
• Các tests còn lại không có ràng buộc bổ sung

Example

9
-90 1 3 -2 5 -1 2 5 -3

13

Cho dãy \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) và số nguyên dương \(M\). Hãy đếm số lượng cặp \((i, j)\) với \(1 \leq i < j \leq n\) sao cho \(a_i + a_j\) chia hết cho \(M\).

Input

• Dòng đầu chứa hai số nguyên dương \(n, M\) (\(n \leq 3 \cdot 10^5\); \(M \leq 10^{18}\))
• Dòng thứ hai chứa \(n\) số nguyên lần lượt là \(a_1, a_2, \ldots, a_n\) (\(|a_i| \leq 10^{18}\) với mọi \(i = 1,2,\ldots,n\))
• Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space)

Output

• Ghi ra màn hình một số nguyên duy nhất là số cặp tìm được.

Scoring

• \(40\%\) số test ứng với \(40\%\) số điểm của bài có \(n \leq 5000\)
• \(20\%\) số test tiếp theo ứng với \(20\%\) số điểm của bài có \(M \leq 10^6\)
• Các test còn lại không có ràng buộc bổ sung

Example

5 4
1 3 2 6 2

4

Trước cửa nhà Dũng có \(n\) cây hoa hồng trồng thành một dãy và đánh số \(1, 2, \ldots, n\) từ trái qua phải. Dũng đánh giá "độ đẹp" của những bông hoa hồng trong cây hoa hồng thứ \(i\) bằng một số nguyên dương \(a_i\). Nhân ngày Quốc tế Phụ nữ (8/3), Dũng muốn làm 2 bó hoa tặng mẹ và tặng cô giáo chủ nhiệm bằng cách chọn mỗi cây hoa hồng không quá một bông hoa. Một bó hoa được gọi là đẹp nếu như "độ đẹp" của các bông hoa hồng trong bó hoa này chênh lệch nhau không quá \(K\). Tất nhiên Dũng muốn tổng số bông hồng trong cả hai bó hoa càng lớn càng tốt.

Yêu cầu: Hãy tìm số lượng bông hồng lớn nhất có thể được chọn để làm 2 bó hoa.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, K\) (\(n \leq 10^6; K \leq 10^9\))
• Dòng thứ hai chứa \(n\) số nguyên dương lần lượt là \(a_1, a_2, \ldots, a_n\) (\(a_i \leq 10^9\))
• Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space)

Output

• Ghi ra màn hình một số nguyên duy nhất là tổng số lượng bông hoa tối đa trong hai bó hoa.

Scoring

• \(30\%\) số tests đầu tiên có \(n \leq 10\)
• \(20\%\) số tests tiếp theo có \(n \leq 100\)
• \(20\%\) số tests tiếp theo có \(n \leq 5000\)
• \(30\%\) số tests còn lại không có ràng buộc bổ sung

Example

6 5
1 2 4 7 7 13

5

Trường THCS nơi Dũng đang học có trồng một hàng cây xanh trông rất đẹp. Hàng cây gồm \(n\) cây xanh được đánh số thứ tự từ \(1\) đến \(n\) (theo hướng từ trái sang phải). Để đơn giản có thể coi hàng cây như trục toạ độ Ox và cây thứ \(i\) có toạ độ \(x_i\) (\(x_1 < x_2 < \cdots < x_n\)).

Để tưới nước cho cây, nhà trường có kế hoạch lắp đặt \(m\) vòi tưới nước tự động. Vòi nước thứ \(i\) (\(i = 1, 2, \ldots, m\)) được lắp tại vị trí cây \(t_i\), có bán kính tưới nước là \(R_i\). Điều này có ý nghĩa rằng vòi nước này tưới được cây \(t_i\) và tất cả các cây có khoảng cách đến \(t_i\) không vượt quá \(R_i\).

Yêu cầu: Cho biết vị trí lắp đặt \(m\) vòi nước và bán kính tưới nước của \(m\) vòi này. Hãy đếm xem có bao nhiêu cây được tưới nước.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) (\(1 \leq m \leq n \leq 10^6\))
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \ldots, x_n\) (\(0 < x_1 < x_2 < \cdots < x_n \leq 10^9\)) lần lượt là toạ độ của các cây \(1, 2, \ldots, n\)
• Tiếp theo là \(m\) dòng, dòng thứ \(i\) chứa hai số nguyên dương \(t_i, R_i\) (\(1 \leq t_i \leq n; R_i \leq 10^9\)) lần lượt là số hiệu và bán kính tưới nước của vòi nước thứ \(i\) (\(i = 1, 2, \ldots, m\))
• Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space)

Output

• In ra màn hình một số nguyên duy nhất là số cây được tưới nước.

Scoring

• \(30\%\) số tests ứng với \(30\%\) số điểm của bài có \(m = 1\)
• \(30\%\) số tests tiếp theo ứng với \(30\%\) số điểm của bài có \(n \leq 2000\)
• Các tests còn lại không có giới hạn bổ sung

Example

6 2
1 3 5 7 9 11
1 5
4 2

5