Разделим последовательность на своеобразные блоки, где разделители — это один или несколько подряд идущих нулей. В каждом блоке посчитаем количество чётных и нечётных чисел. Сумма чётна, если оба числа в паре либо чётны, либо нечётны. Значит, число нужных пар в некоторых двух блоках — это произведение количества чётных в первом блоке и во втором блоке + произведение количества нечётных в первом блоке и во втором блоке. Тогда ответом будет сумма всех возможных таких попарных произведений среди всех блоков.
При реализации программы алгоритм будет выглядеть так: создадим два массива, где будем сохранять количество чётных и нечётных чисел в каждом блоке. Блоком будет элемент массива. Также создадим указатель, чтобы чётные и нечётные числа считались в нужный блок. Если встречается 0 и до этого нулей не было, нужно создать новый блок, то есть добавить к массивам новую ячейку и переместить указатель на неё. Если же нули до этого нуля были, то просто пропустим данный шаг, чтобы не захламлять массив (поэтому стоит объявить флаг prev_0 именно как True, чтобы пропустить нули в начале, если они есть). Как только встречается положительное число, увеличиваем число в нужном блоке на один. После окончания ввода считаем все возможные попарные произведения в массиве чётных и нечётных чисел.
Программа эффективна по памяти, так как размеры массивов ограничены числом N ≤ 10000, а также эффективна по времени, так как все данные считываются в один проход, а каждый из последних циклов сделает меньше 10000² операций, что для компьютера довольно немного.
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² операций, что для компьютера довольно немного.
Відповідь:
Пояснення:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n, i, j,p, s;
float sr;
cin>>n;
int arra[n];
for(i=0; i<n; i++)
cin>>arra[i];
for (int i = 1; i<n; i++)
{
if (arra[i] > 0){
s = s + arra[i];
p = p + 1;
}
}
sr = s/p;
printf("%.2f",sr);
cout<<endl;
cout<<"[ ";
for(int i = n - 1; i >=0; i--)
cout<<arra[i]<<" ";
cout<<"]"<<endl;
return 0;
}