5315 (Задача тип 27)

На вход программе поступает последовательность натуральных чисел. Рассматриваются подпоследовательности исходной последовательности, состоящие из K элементов и содержащие в себе хотя бы один нуль. Гарантируется, что K - нечётное. Среди этих подпоследовательностей найти такие, в которых суммы элементов, расположенных по разные стороны от центра, равны. Центральное число в суммы не учитывается. Найдите количество подходящих подпоследовательностей..

Входные данные. Даны два входных файла (файл A и файл B), содержит в первой строке число N (2 ≤ N ≤ 5 000 000) – количество чисел в последовательности, а также число K. Каждая из следующих N строк содержит одно натуральное число, не превышающее 10000.

Пример входного файла:

8 5

4

2

0

2

4

1

3

0

В этой последовательности одна подходящая подпоследовательность: {4, 2, 0, 2, 4}. В ней центральный элемент - 0, сумма слева от центра 4 + 2 = 6, сумма справа 2 + 4 = 6. При этом она содержит в себе ровно один нуль. Ответ: 1.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Решение

f=open('A.txt')

n,k=map(int,f.readline().split())

a=[]

k1=k//2

for i in range(n):

    a.append(int(f.readline()))

c=0

for i in range(n-k+1):

    b=a[i:i+k]

    if b.count(0)>0 and sum(b[:k1])==sum(b[-k1:]):

        c+=1

print(c)