|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1921. Разбиение массива
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
Пете подарили на день рождения массив из N целых чисел. Петя – мальчик не жадный, и он хочет поделиться массивом с двумя своими друзьями. Для этого Петя хочет разбить массив на три непустые части (левую, среднюю и правую) так, чтобы суммы элементов в каждом подмассиве получились одинаковыми. Определите, сколькими способами он может это сделать. Входные данные В первой строке входных данных записано натуральное число N – размер массива. Во второй строке через пробел записаны целые числа a1, a2, ..., aN – элементы массива. Выходные данные Выведите одно целое число – количество способов разбить входной массив на три непустых подмассива с одинаковой суммой. Система оценки Подзадача 1 (30 баллов): 3 ≤ N ≤ 100, - 106 ≤ ai ≤ 106. Подзадача 2 (30 баллов): 3 ≤ N ≤ 10000, - 109 ≤ ai ≤ 109. Подзадача 3 (40 баллов): 3 ≤ N ≤ 2·105, - 109 ≤ ai ≤ 109. Во всех подзадачах каждый тест оценивается независимо. Примеры Входные данные 6 5 -2 3 0 2 1 Выходные данные 2 Входные данные 5 1 2 3 4 5 Выходные данные 0 Примечание В первом примере массив можно разбить двумя способами: [5 -2 | 3 | 0 2 1] и [5 -2 | 3 0 | 2 1]. Набор тестов несколько расширен по сравнению с тем, что был на олимпиаде. |
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| 1920. 3 - Игра | 1921. | 1922. 5 - Поворот фотографии |
| время генерации 0.125 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |