Дана последовательность натуральных чисел. Расстояние между элементами последовательности — это разность их порядковых номеров. Например, если два элемента стоят в последовательности рядом, расстояние между ними равно 1, если два элемента стоят через один — расстояние равно 2 и так далее.
Назовём парой любые два числа из последовательности, расстояние между которыми не меньше 18. Необходимо определить количество пар, в которых сумма чисел в паре делится без остатка на 8, а их произведение — на 2187.
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 100 000. Гарантируется, что число в ответе не превышает 2 · 109.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала искомое значение для файла A, затем — для файла B.
Ответ:
Решение. Приведём решение пункта А на языке Python.
N = 1086
count = 0
f = open('27-A.txt')
s = f.readlines()
for i in range(1, len(s)):
for j in range(i, len(s)):
if j - i + 1 >= 18:
if (int(s[i]) + int(s[j])) % 8 == 0 and (int(s[i]) * int(s[j])) % 2187 == 0:
count += 1
print(count)
Ответ: 350 507749149.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
Заметим, что 2187 = 3**7. Произведение двух чисел делится на 3**7, если совокупное количество троек (при разложении на простые множители) в этих числах больше семи. А сумма чисел делится на 8, если сумма остатков от деления этих чисел на 8 сама делится на 8. Поэтому, для решения задачи распределим данные числа в двумерный массив, первый индекс которого является остатком от деления на 8, а второй — количество троек. В ячейках этого массива будут массивы индексов таких чисел. Переберём все возможные комбинации остатков от 8 и количества троек, а в подходящих комбинациях переберём пары индексов. Заметим, что каждая подходящая пара будет посчитана ровно по два раза, поэтому результат подсчёта делим на 2.
o=open("27.txt")
N = int(o.readline())
raw_arr = [int(i) for i in o]
arr = [ [ [] for j in range(11) ] for i in range(8) ]
def count3(n):
count = 0
while n % 3 == 0:
count += 1
n //= 3
return count
for i in range(N):
arr[raw_arr[i]%8][count3(raw_arr[i])].append(i)
count = 0
for i8 in range(8):
for j8 in range(8):
for i3 in range(11):
for j3 in range(11):
if (i8 + j8) % 8 == 0 and (i3 + j3) >= 7:
for a in arr[i8][i3]:
for b in arr[j8][j3]:
if abs(a - b) >= 18:
count += 1
print(count // 2)
Приведём решение Сергея Фефелова на языке Python.
f = list(map(int, open('27-B.txt').readlines()))
li = [[0]*9 for i in range(8)]
def count3(n):
count = 0
while n % 3 == 0 and count < 8:
count += 1; n //= 3
return count
count = 0
for i, p in enumerate(f[18:]):
j3 = count3(p)
for l3 in range(max(0,7-j3),9):
count += li[(-p)%8][l3]
li[f[i+1]%8][count3(f[i+1])] += 1
print(count)
Приведём решение Юрия Красильникова на языке Python.
PDF-версии: 