Количество пар чисел разделённых нулём

Question

Дана последовательность n целых неотрицательных чисел. Нужно сосчитать количество пар элементов последовательности, в которых:

первый элемент пары расположен в последовательности перед вторым,
оба элемента положительны,
их сумма чётна,
между ними в последовательности есть хотя бы один ноль.

Входные данные:
В первой строке записано целое неотрицательной число n – количество чисел в последовательности. В следующих n строках записаны числа, входящие в последовательность, по одному в строке.

Выходные данные:
Программа должна вывести одно число – количество найденных пар.

Пример входных данных:

Пример выходных данных:

Пример решения. Оно медленное, нужно решить быстрее:

n = int(input())
a = [int(input()) for _ in range(n)]

c = 0
for i in range(n):
    if a[i] > 0:
        for j in range(i, n):
            if a[j] > 0 and (a[i] + a[j]) % 2 == 0:
                if any(a[k] == 0 for k in range(i + 1, j)):
                    c += 1
print(c)

Answer 1

Будем запоминать количество чётных и нечётных до последнего нуля и после него.

Если встретили ноль, то счётчики "после" перебрасываем в "до".

Если чётное, то добавляем количество пар, равное количеству чётных до последнего нуля, аналогично для нечётных.

1 2 3 0 4 5 6 0 7 8 9
            ^           здесь счётчик чётных "до" равен 1, 
                    образуется одна новая пара с двойкой, четвёрка не учитывается.

При этом увеличиваем соотв. счётчик "после".

c = 0
n = int(input())
counts_after_zero = [0, 0]
counts_before_zero = [0, 0]

for _ in range(n):
    x = int(input())
    if x > 0:
        c += counts_before_zero[x%2]
        counts_after_zero[x%2] += 1
    else:
        counts_before_zero[0] += counts_after_zero[0]
        counts_before_zero[1] += counts_after_zero[1]
        counts_after_zero = [0, 0]

print(c)

БЛОГ НА HUSL

Количество пар чисел разделённых нулём

Ответы (1 шт):