Входные данные Первая строка входных данных содержит целое число N (3≤N≤105 ) — количество домов на улице. Следующие N строк содержат по одному целому числу ai (0<|ai|≤104 ). Если ai>0 , то в i -м доме проживает ai избирателей, голосующих за кандидата от

8 октября 2025
Политология

Условие:

Входные данные
Первая строка входных данных содержит целое число N
(3≤N≤105
) — количество домов на улице. Следующие N
строк содержат по одному целому числу ai
(0<|ai|≤104
). Если ai>0
, то в i
-м доме проживает ai
избирателей, голосующих за кандидата от партии X
. Если ai<0
, то в i
-м доме проживает |ai|
избирателей, голосующих против кандидата от партии X
.

Выходные данные
Если возможно разделить N
домов на три округа так, что минимум в двух округах выигрывает кандидат от партии X
, программа должна вывести три целых положительных числа N1
, N2
, N3
, N1+N2+N3=N
, соответствующих количеству домов в первом, втором и третьем избирательном округе от начала улицы. При таком разбиении минимум в двух округах из трёх должен выигрывать кандидат от партии X
. Если возможно несколько таких разбиений, необходимо вывести любое из них.

Если искомое разбиение не существует, программа должна вывести одно число 0.
Пример
Входные данные
7
-3
-5
3
-4
2
5
-3
Выходные данные
4 1 2

Решение:

Для решения задачи, давайте разберем ее по шагам.

Шаг 1: Понимание задачи

Нам нужно разделить N домов на три округа так, чтобы в минимум двух из них кандидат от партии X выиграл. Это значит, что в этих округах количество голосов за кандидата от партии X должно быть больше, чем против него.

Шаг 2: Ввод данных

Сначала мы считываем количество домов N и затем считываем количество избирателей в каждом доме. Если число положительное, это голоса за кандидата X, если отрицательное — против.

Шаг 3: Подсчет голосов

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

Шаг 4: Перебор возможных разделений

Мы будем перебирать возможные способы разделения домов на три округа. Для этого мы можем использовать два указателя, чтобы определить границы округов.

Шаг 5: Проверка условий выигрыша

Для каждого разделения мы будем проверять, сколько округов выигрывает кандидат X. Если два или три округа выигрывают, мы запоминаем это разделение.

Шаг 6: Вывод результата

Если мы нашли подходящее разделение, выводим количество домов в каждом округе. Если нет, выводим 0.

Реализация

Теперь давайте реализуем это в коде:

1. Считываем количество домов и их голоса. 2. Создаем префиксный массив для быстрого подсчета голосов в округах. 3. Перебираем все возможные разделения на три округа. 4. Для каждого разделения считаем количество голосов и проверяем, сколько округов выигрывает кандидат X. 5. Если нашли подходящее разделение, выводим его. Если нет, выводим 0. Для входных данных: Программа должна вывести: Это означает, что первый округ состоит из 4 домов, второй из 1 дома, а третий из 2 домов.