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 <functional>
#include <string>
#include <vector>
struct converter
{
std::function<double(double)> function;
std::string to;
};
int main()
{
std::vector<converter> table =
{
{[](double d) { return d; }, "kg"},
{[](double d) { return d / 1000 / 1000; }, "mg"},
{[](double d) { return d / 1000; }, "g"},
{[](double d) { return d * 100; }, "cnt" },
{[](double d) { return d * 1000; }, "tones" }
};
int ind = 0;
std::cin >> ind;
ind -= 1;
if (ind >= 0 && ind < table.size())
{
int m = 0;
std::cin >> m;
const converter& current = table[ind];
std::cout << "Result of converting " << m << " " << current.to << " is " << current.function(m) << " kg" << std::endl;
}
}
Пример работы: