TS10 Bắc Ninh 2026 - Cặp số đặc biệt
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Tài là học sinh giỏi toán và ham học hỏi. Tài rất thích thú với những cặp số đặc biệt. Cặp số đặc biệt là những cặp số có tổng chia hết cho ~3~.
Cho một dãy ~a~ gồm ~n~ số nguyên dương. Tài muốn biết trong dãy ~a~, có bao nhiêu cặp chỉ số ~(i, j)~ với ~(1 \le i < j \le n)~ sao cho tổng ~a_i + a_j~ chia hết cho ~3~.
Yêu cầu: Bạn hãy giúp bạn Tài đếm xem có bao nhiêu cặp số này nhé.
Input
Dòng 1: Chứa số nguyên dương ~n~ ~(1 < n \le 10^6)~.
Dòng 2: Chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^6, 1 \le i \le n)~. Các số cách nhau ít nhất một dấu cách.
Output
- Một số nguyên duy nhất là số lượng cặp số của dãy ~a~ có tổng chia hết cho ~3~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~60\%~ | ~1 < n \le 10^3~ |
| 2 | ~40\%~ | ~10^3 < n \le 10^6~ |
Sample Input 1
7
3 6 8 5 3 5 7
Sample Output 1
6
Sample Input 2
5
5 6 8 4 3
Sample Output 2
3
Notes
Sample 1: ~6~ cặp số tìm được có chỉ số là: ~(1,2), (1,5), (2,5), (3,7), (4,7), (6,7)~
Sample 2: ~3~ cặp số tìm được có chỉ số là: ~(1,4), (2,5), (3,4)~
Bình luận
ok