Задача: Бизнесмен Василий

Запись от eaa размещена 13.06.2021 в 08:35

Показов 4710 Комментарии 0

Задача: Бизнесмен Василий
Бизнесмен Василий готовится к уплате налогов за квартал (три месяца). Действующая налоговая система в государстве, в котором Василий ведет свой бизнес, устроена таким образом, что величина налога зависит от прибыли в конце каждого месяца. Чистая прибыль бизнесмена определяется как разница между доходом и расходом. Разумеется, если бизнес идет не очень удачно, прибыль бизнесмена может быть отрицательной —в этом случае речь идет об убытке.

Все доходы и расходы Василий записывал в журнал в виде целых чисел. Теперь Василий должен подать налоговую декларацию с суммой доходов на конец каждого месяца, другими словами ему необходимо поделить последовательность записей в журнале на три непустые части.

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

По имеющимся данным определите количество способов выполнить такое разбиение.

Входные данные
В первой строке входных данных содержится единственное целое число N — количество записей в журнале Василия (3 ≤ N ≤ 10⁵).
В следующих N строках записаны целые числа ai, соответствующие записям в журнале (−10⁸ ≤ ai ≤ 10⁸).

Выходные данные
Программа должна вывести единственное целое число — количество способов выполнить необходимое разбиение.

Ввод:
6
4
3
-3
5
-1
4
Вывод:
2
В журнале записано 6 чисел: 4, 3, −3, 5, −1, 4 Из них можно получить два разбиения: [4], [3, −3, 5, −1], [4] и [4, 3, −3], [5, −1], [4].

Ввод:
3
0
0
0
Вывод:
1
В журнале записаны три нуля — имеется единственное возможное разбиение [0], [0], [0], потому что в каждой записи должно быть хотя бы одно число.

Ввод:
4
3
-2
3
1
Вывод:
0
Выполнить подходящее разбиение невозможно.

вывод разбиений перебором:

Python
1
2
3
4
5
6
n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n-2):
    for j in range(i+1, n-1):
        if sum(a[:i+1]) == sum(a[i+1:j+1]) == sum(a[j+1:]):
            print(a[:i+1], a[i+1:j+1], a[j+1:])

Решения
O(n^3) перебор:

Python
1
2
3
4
5
6
7
n = int(input())
a = [int(input()) for _ in range(n)]
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        count += sum(a[:i+1]) == sum(a[i+1:j+1]) == sum(a[j+1:])
print(count)

O(n^2) перебор + префикс-суммы:

Python
1
2
3
4
5
6
7
8
9
from itertools import accumulate
n = int(input())
a = [int(input()) for _ in range(n)]
*pref, = accumulate(a)
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        count += pref[i] == pref[j]-pref[i] == pref[n-1]-pref[j]
print(count)

O(n*log(n)) префикс-суммы + суффикс-суммы + бинпоиск:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from itertools import accumulate
from bisect import bisect_right as bs
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
if s%3:
    print(0)
    exit()
*pref, = accumulate(a)
*suff, = accumulate(a[::-1])
pos_pref = [i for i, x in enumerate(pref) if x == s//3]
pos_suff = [n-i-1 for i, x in enumerate(suff) if x == s//3][::-1] # переворачивает т.к. это суффиксы
len_pos_suff = len(pos_suff)
count = 0
for i in pos_pref:
    j = bs(pos_suff, i+1)
    if j < n:
        count += len_pos_suff - j
print(count)

O(n) префикс-суммы + суффикс-суммы + подсчёт:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from itertools import accumulate
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
if s % 3:
    print(0)
    exit()
*pref, = accumulate(a)
*suff, = accumulate(a[::-1])
pos_pref = [int(x == s//3) for i, x in enumerate(pref)]
pos_suff = [int(x == s//3) for i, x in enumerate(suff)]
*count_pos_suff, = accumulate(pos_suff)
count_pos_suff.reverse() # переворачивает т.к. это суффиксы
count = 0
for i, p in enumerate(pos_pref[:-2]):
    if p == 1:
        count += count_pos_suff[i+2]
print(count)

Размещено в Без категории

Главная страница Решение вступительных заданий schol.hh.ru 2022 »

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

Всего комментариев 0

Комментарии

eaa

Регистрация 26.11.2017
Сообщений 5,262
Записей в блоге 3

Новые блоги и статьи Все статьи Все блоги /
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .	Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .

Наверх

Сообщение форума

Отменить изменения