Register | Login

Solutions of 3

Select solution language All Tiếng Việt English Other

Write solution here.

---

minhnhatha    Created at    2 likes

Có 2 trường hợp cho cặp số $A[i], A[j]$ cần chọn: - 1 số chia 3 dư 1, số còn lại chia 3 dư 2 - 2 số chia hết cho 3 Khi đó tổng $A[i] + A[j]$ sẽ chia hết cho 3 Ta sẽ lưu số lần xuất hiện các số dư khi chia cho 3 (của các số nhập vào mảng). Khi đó: - Có $x$ số chia hết cho 3 thì sẽ có $\frac12*(x - 1) * x$ cặp số gồm 2 số chia hết cho 3 - Có $m$ số chia 3 dư 1, $n$ số chia 3 dư 2 thì có $m*n$ cặp số mà 1 số chia 3 dư 1, số còn lại chia 3 dư 2 Tổng số cặp của 2 loại trên là kết quả bài toán **Code Python** ``` n = int(input()) k = [int(i) for i in input().split()] A = [0, 0, 0] ans = 0 for i in range(n): A[k[i] % 3] += 1 print((A[0] - 1) * A[0] // 2 + A[1] * A[2]) ```