(№ 2710) (Е. Джобс) Дана последовательность N целых неотрицательных чисел. Необходимо определить количество пар положительных элементов этой последовательности, сумма которых четна, при этом между элементами пары есть хотя бы один ноль.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке натуральное число N (1 < N < 10000) – количество чисел в последовательности. В следующих N строках записаны числа, входящие в последовательность, по одному в каждой строке.
Выходные данные: Программа должна вывести одно число – количество найденных пар.
Пример входного файла:
6
2
1
4
0
3
4
Для указанных входных данных искомое количество пар равно 3.
В условии не сказано, что ноль не может входить в пару слагаемых, между которыми есть другие нули, но указанный к заданию ответ подразумевает это.
Мое решение:
n = int(input())
pairs = 0
fragms = [[0,0]]
zeros = 0
for i in range(n):
x = int(input())
if x == 0 and i!= 0:
zeros += 1
fragms.append([0,0])
else:
if x%2 == 0:
fragms[zeros][0] += 1
else:
fragms[zeros][1] += 1
for i in range(len(fragms)):
below = 0
for k in range(i+1,len(fragms)):
below += fragms[k][0]
pairs += fragms[ i ][0]*below
#for i in range(zeros-2):
# pairs += fragms[zeros-i ][0]*(zeros-1-i)
#for i in range(len(fragms)-2):
# pairs += fragms[ i ][0]*(zeros-1-i)
#for i in range(zeros-2):
# pairs += i+1
for i in range(len(fragms)):
below = 0
for k in range(i+1,len(fragms)):
below += fragms[k][1]
pairs += fragms[ i ][1]*below
print(pairs)
Мой код сначала разбивает входные данные на фрагменты, подсчитывая количество четных и нечетных чисел в каждом фрагменте (фрагмент - часть последовательности, отделенная нулем). Потом подсчитывается количество сумм четное+четное. Дальше в закомментированных фрагментах идет подсчет удовлетворяющих условию сумм: четное из фрагмента + один из последующих нулей, ноль + четное из следующих за ним фрагментов, сумма нулей. И в последнем цикле идет подсчет сумм нечетное+нечетное. Таким образом, если не использовать закомментированный код, ответ сходится, но ведь суммы пар четных чисел и нулей или нулей с нулями тоже четные, то есть, их тоже надо учитывать.
Ответ, указанный на сайте, который также получается, если не использовать закомментированную часть: 51, 24019058
Ответ, который получается, если учитывать описанные выше пары чисел: 56, 24565497