На вход программы поступает число N, а затем последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности. Необходимо определить количество пар чисел, разность которых кратна 98.
В ответе укажите два числа: сначала значение для файла А, затем через пробел значение для файла B.
Идея статического решения:
Разность пары кратна 98 в том случае, когда разность остатков при делении на 98 пары чисел кратна 98. Это выполняется только в одном случае, когда остатки при делении на 98 двух чисел равны. Идея заключается в том, что мы сначала совершим проход по файлу, в котором посчитаем количество чисел под каждым остатком. Затем, используя знания комбинаторики, нужно записать выражение, которое посчитает итоговое количество пар.
Идея динамического решения:
Разность пары кратна 98 в том случае, когда разность остатков при делении на 98 пары чисел кратна 98. Это выполняется только в одном случае, когда остатки при делении на 98 двух чисел равны. Идея решения заключается в том, чтобы под каждым остатком при делении на 98 собирать количество число с одинаковым остатком при делении на 98 с той целью, чтобы в итоге мы могли на каждой итерации получать итоговое количество пар на данный момент. Разность пары кратна 98 в том случае, когда разность остатков при делении на 98 пары чисел кратна 98. Это выполняется только в одном случае, когда остатки при делении на 98 двух чисел равны.
#переборный алгоритм:
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]) % 98 == 0: #проверка по условию.
counter += 1 # увеличение счётчика пар.
print(counter)#вывод ответа.
#Статическое решение
f = open("1.txt") #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
k=[0]*98 #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
for i in range(n): #проход по всему файлу
x=int(f.readline()) #считываем текущее число
k[x%98]+=1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 98
count = 0 #итоговое количество пар
for i in range(98): #проход по всем остаткам при делении на 98
count+=k[i]*(k[i]-1)//2 #составляем пару из двух чисел с одинаковым остатком при делении на 98
print(count) #вывод ответа.
#Динамическое решение
file = open(’7_B__2rcti.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 98 #число, на которое нацело должна делиться разность пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
x = int(file.readline()) #считываем текущее число
count += k[x % div] #увеличиваем count на количество чисел с необходимым остатком для первого числа для получения разности пары кратной 98
k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 98
print(count) # вывод ответа