Độ khó: Dễ (1/4 điểm)

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

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

Dữ liệu vào (stdin)

• 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, \dots, 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, \dots, a_n~ không vượt quá ~10^6~.

Kết quả (stdout)

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

Ràng buộc

• Có 80% số test ứng với 80% số điểm của bài thỏa mãn ~a_i \le 10^9~ với mọi ~i = 1, 2, \dots, n~.
• Các test còn lại không có ràng buộc bổ sung.

Sample Input

5
15
50
140
25
10

Sample Output

2

Giải thích

Chỉ có 2 số 50, 140 thoả mãn đồng thời hai điều kiện: chia hết cho 5 và tổng các chữ số cũng chia hết cho 5.

Độ khó: Trung bình (2/4 điểm)

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, \dots, 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.

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 (giai đoạn gồm ít nhất một bài kiểm tra).

Dữ liệu vào (stdin)

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

Kết quả (stdout)

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

Ràng buộc

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

Sample Input

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

Sample Output

13

Giải thích

Dãy điểm cần tìm là 1, 3, -2, 5, -1, 2, 5 có tổng 1 + 3 - 2 + 5 - 1 + 2 + 5 = 13.

Độ khó: Khá (3/4 điểm)

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

Dữ liệu vào (stdin)

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

Kết quả (stdout)

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

Ràng buộc

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

Sample Input

5 4
1 3 2 6 2

Sample Output

4

Giải thích

Các cặp ~(i, j)~ tìm được là (1, 2), (3, 4), (3, 5), (4, 5).

Độ khó: Khá (3/4 điểm)

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

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.

Dữ liệu vào (stdin)

• Dòng đầu tiên chứa hai số nguyên dương ~n, K~ (~n \le 10^6~; ~K \le 10^9~).
• Dòng thứ hai chứa ~n~ số nguyên dương lần lượt là ~a_1, a_2, \dots, a_n~ (~a_i \le 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.

Kết quả (stdout)

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

Ràng buộc

• Có 30% số test ứng với 30% số điểm của bài có ~n \le 10~.
• 20% số test tiếp theo ứng với 20% số điểm của bài có ~n \le 100~.
• 20% số test tiếp theo ứng với 20% số điểm của bài có ~n \le 5000~.
• Các test còn lại không có ràng buộc bổ sung.

Sample Input

6 5
1 2 4 7 7 13

Sample Output

5

Giải thích

Một cách để chọn 5 bông hoa cho 2 bó hoa là:

• Bó thứ nhất gồm 2 bông hoa lấy từ 2 cây hoa có "độ đẹp" 1, 4.
• Bó thứ hai gồm 3 bông hoa lấy từ 3 cây hoa có "độ đẹp" 2, 7, 7.

Không có cách nào chọn 6 bông hồng.

Độ khó: Trung bình (2/4 điểm)

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 < \dots < 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, \dots, 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 cây ~t_i~ không vượt quá ~R_i~.

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.

Dữ liệu vào (stdin)

• Dòng đầu tiên chứa hai số nguyên dương ~n, m~ (~1 \le m \le n \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, \dots, x_n~ (~0 < x_1 < x_2 < \dots < x_n \le 10^9~) lần lượt là toạ độ của các cây 1, 2, ..., ~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 \le t_i \le n~; ~R_i \le 10^9~) lần lượt là số hiệu cây lắp vòi và bán kính tưới nước của vòi nước thứ ~i~ (~i = 1, 2, \dots, m~).

Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống.

Kết quả (stdout)

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

Ràng buộc

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

Sample Input

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

Sample Output

5

Giải thích

Vòi thứ nhất (đặt tại cây 1, toạ độ 1, bán kính 5) tưới được các cây số hiệu 1, 2, 3 (toạ độ 1, 3, 5); vòi thứ hai (đặt tại cây 4, toạ độ 7, bán kính 2) tưới được các cây 3, 4, 5 (toạ độ 5, 7, 9). Như vậy chỉ các cây 1, 2, 3, 4, 5 được tưới nước.

Lưu ý: ví dụ trong đề gốc ghi ~n = 5~ nhưng có tới 6 toạ độ, đây là lỗi đánh máy; ở đây đã sửa thành ~n = 6~.