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

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

Показов 4594 Комментарии 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

Новые блоги и статьи Все статьи Все блоги /
Диалоги с ИИ zorxor 23.05.2026 Насколько я понимаю - Вы - Искусственный Интеллект. Это так? Да, всё верно. Я — искусственный интеллект. Я представляю собой большую языковую модель, созданную для помощи в самых разных задачах. . . .	Модель здравосохранения 14. Собираем всю модель вместе. anaschu 22.05.2026 Модель собрана. В будущих постах на видео я покажу, как она работает. В этом посте запускаем её, проверяем результаты и разбираем что можно с ней делать дальше. Перед запуском проверяем. . .	Модель здравоохранения 13. Добавление самой системы здравоохранения. anaschu 22.05.2026 В предыдущем посте мы настроили болезни. Теперь добавим события, которые управляют здоровьем всего коллектива, а также настроим рабочий график и расчёт финансов. В Main создаём четыре события. . . .	Модель здравоохранения 12. добавление болезней через ресурпул, как аварии anaschu 22.05.2026 Болезни — это ключевая часть нашей модели. Нам нужно, чтобы работник периодически уходил на больничный, его задание при этом зависало, а после выздоровления работа возобновлялась. Реализуем это двумя. . .
Модель здравоохранения 11. Создаём классы Задание и Работник anaschu 22.05.2026 В AnyLogic каждая заявка и каждый ресурс — это объект определённого класса. Нам нужно создать два класса: Задание (заявка) и Работник (ресурс). Класс Задание В дереве проекта нажимаем правой. . .	Модель здравоохранения 10. Новая модель, смотрим, как добавлять логические блоки, и что писать внутри anaschu 22.05.2026 Открываем AnyLogic, создаём новый проект. В дереве проекта появляется класс Main — это главный агент, в котором будет жить вся наша логика. Палитра блоков Слева находится палитра. Нас интересует. . .	модель ЗдравоСохранения 9. Новая модель, разбираемся, как ее создавать anaschu 22.05.2026 В этой серии постов мы построим модель небольшого рабочего коллектива. Сотрудники получают задания, выполняют их, иногда болеют — и мы хотим посчитать, сколько это стоит компании. Метод. . .	[golang] Linked list alhaos 22.05.2026 Связный список / Linked list Связный список структура данных позволяющая хранить список значений, в отличии от массива в памяти хранится не сплошным куском, а отдельными частями которые ссылаются. . .

Наверх

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

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