Задание 27 (Е. Джобс) Дана последовательность N целых неотрицательных чисел. Необходимо определить количество пар положительных элементов этой последовательности, сумма которых четна, при этом между элементами пары есть хотя бы один ноль.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке натуральное число N (1 < N < 10000) – количество чисел в последовательности. В следующих N строках записаны числа, входящие в последовательность, по одному в каждой строке.
Выходные данные: Программа должна вывести одно число – количество найденных пар.
Пример входного файла:
6
2
1
4
0
3
4
Для указанных входных данных искомое количество пар равно 3.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
, не знаю как решить
even, odd = [0], [0]
pointer = 0
prev_0 = True
answer = 0
n = int(input())
for i in range(n):
num = int(input())
if num == 0 and not(prev_0):
even.append(0)
odd.append(0)
pointer += 1
prev_0 = True
elif num == 0 and prev_0:
continue
else:
prev_0 = False
if num % 2 == 0:
even[pointer] += 1
else:
odd[pointer] += 1
for i in range(len(even)):
for j in range(i+1, len(even)):
answer += even[i] * even[j]
for i in range(len(odd)):
for j in range(i+1, len(odd)):
answer += odd[i] * odd[j]
print(answer)
Объяснение:
Разделим последовательность на своеобразные блоки, где разделители — это один или несколько подряд идущих нулей. В каждом блоке посчитаем количество чётных и нечётных чисел. Сумма чётна, если оба числа в паре либо чётны, либо нечётны. Значит, число нужных пар в некоторых двух блоках — это произведение количества чётных в первом блоке и во втором блоке + произведение количества нечётных в первом блоке и во втором блоке. Тогда ответом будет сумма всех возможных таких попарных произведений среди всех блоков.
При реализации программы алгоритм будет выглядеть так: создадим два массива, где будем сохранять количество чётных и нечётных чисел в каждом блоке. Блоком будет элемент массива. Также создадим указатель, чтобы чётные и нечётные числа считались в нужный блок. Если встречается 0 и до этого нулей не было, нужно создать новый блок, то есть добавить к массивам новую ячейку и переместить указатель на неё. Если же нули до этого нуля были, то просто пропустим данный шаг, чтобы не захламлять массив (поэтому стоит объявить флаг prev_0 именно как True, чтобы пропустить нули в начале, если они есть). Как только встречается положительное число, увеличиваем число в нужном блоке на один. После окончания ввода считаем все возможные попарные произведения в массиве чётных и нечётных чисел.
Программа эффективна по памяти, так как размеры массивов ограничены числом N ≤ 10000, а также эффективна по времени, так как все данные считываются в один проход, а каждый из последних циклов сделает меньше 10000² операций, что для компьютера довольно немного.