На вход подаётся последовательность из 
натуральных чисел, каждое из которых не больше 1000. Напишите программу, находящую количество пар чисел, сумма которых кратна 3.
Входные данные
В первой строке дано количество чисел 
, в каждой из последующих 
строк записано одно натуральное число, не превышающее 1000.
Выходные данные
Количество пар.
Примечание: двумя элементами последовательности считаются любые два элемента, в том числе не стоящие рядом. Брать сумму элемента самого с собой запрещается, но можно брать сумму двух элементов, равных по значению.
Пример входных и выходных данных:
|
|
|
| Входные данные | Выходные данные |
|
|
|
| 4 | 2 |
| 12 | |
| 3 | |
| 10 | |
| 5 | |
|
|
|
Идея статического решения:
Сумма пары кратна 3 в том случае, когда сумма остатков при делении на 3 пары чисел кратна 3. Идея заключается в том, что мы сначала совершим проход по файлу, в котором посчитаем количество чисел под каждым остатком. Затем, используя знания комбинаторики, нужно записать выражение, которое посчитает итоговое количество пар.
Идея динамического решения:
Идея решения заключается в том, чтобы под каждым остатком при делении на 3 собирать количество число с одинаковым остатком при делении на 3 с той целью, чтобы в итоге мы могли на каждой итерации получать итоговое количество пар на данный момент. Сумма пары кратна 3 в том случае, когда сумма остатков при делении на 3 пары чисел кратна 3. Считывая одно число с определенным остатком при делении на 3 мы должны подобрать в пару ему такое число, чтобы в итоге их пара была кратна 3. Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D — x % D) % D , где D — это 3, а x — первое число пары.
#переборный алгоритм:
f = open(’1_A.txt’) #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
a = [] #cписок, в котором у нас будут находиться все числа файла.
for i in range(n): #проход по файлу.
a.append(int(f.readline())) #добавление текущего числа в список.
counter = 0 #итоговый счётчик пар.
for i in range(0,len(a)-1): #перебор для первого числа пары.
for j in range(i+1,len(a)): #перебор для второго числа пары.
if (a[i]+a[j]) % 3 == 0: #проверка по условию.
counter += 1 #увеличиваем итоговый счётчик
print(counter) #вывод ответа.
#Статическое решение
file = open(’4__t7qm.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 3 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
x = int(file.readline()) #считываем текущее число
k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 3
for i in range(len(k)//2 + 1): #делаем проход до половины всевозможных остатков при делении на 3
if i == 0: #если остаток 0
count += k[0] * (k[0] - 1) // 2 #то мы можем составить пару из двух чисел кратных 3
else: # в ином случае
count += k[i] * k[len(k)-i] #составляем пару из двух разных остатков при делении на 3
print(count) #вывод ответа.
#Динамическое решение
file = open(’4__t7qm.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 3 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
x = int(file.readline()) #считываем текущее число
need_ost = (div - x % div) % div #определяем необходимый остаток второго числа при делении на 3 для того чтобы сумма пары делилась нацело
count += k[need_ost] #увеличиваем count на количество чисел с необходимым остатком для первого числа для получения суммы пары кратной 3
k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 3
print(count) # вывод ответа