eolymp
bolt
Try our new interface for solving problems
Məsələlər

Дороги России

Дороги России

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Россия - самая большая страна в мире. И чтобы проехать на машине через всю страну от Петербурга до Владивостока, потребуется много дней. В дороге может всякое случиться, поэтому недавно была принята государственная программа создания системы бесперебойной связи вдоль всей этой длинной и сложной трассы. Да и не только связь нужна. Нужно следить за техническим состоянием дороги, обеспечивать при необходимости экстренную медицинскую помощь, и еще многое другое нужно обеспечить! Программа эта - очень нужная и важная, и для ее выполнения необходимо найти фирмы - подрядчики. Причем, необходимо, чтобы все фирмы, которые будут обслуживать эту трассу, получили на обслуживание участки равной длины.

Вдоль всей этой трассы стоят города и села, и, конечно, самое разумное решение для равного распределения работ - каждая фирма получит участок вдоль трассы от одного населенного пункта до другого, причем внутри такого участка могут находиться и другие населенные пункты. Расстояния между населенными пунктами известны. Тогда для решения задачи необходимо найти такое разбиение последовательности расстояний между населенными пунктами, чтобы суммы расстояний между городами для каждого участках совпадали. На рисунке приведен пример такого разбиения трассы.

Чтобы каждая фирма получила выполнимый объем работ, правительство хочет так распределить трассу, чтобы полученные участки имели минимальную длину. Ваша задача - найти такое решение.

Giriş verilənləri

Входной файл в первой строке содержит одно целое число N - количество участков между населенными пунктами на трассе Петербург - Владивосток. Далее следуют N целых чисел - расстояния между населенными пунктами. Числа разделены пробелами и/или переводами строки (1N10000).

Çıxış verilənləri

Вывести одно число - минимальную длину фрагмента трассы, обслуживание которого следует поручить одной фирме.

Nümunə

Giriş verilənləri #1
8
4 3 3 2 2 6 1 7
Çıxış verilənləri #1
7
Mənbə Задачи отборочного тура Всероссийской командной олимпиады школьников 2011/2012 учебный год