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

Задача 7. Блины

Условие:

За столом сидят \( N \) гостей, и перед каждым стоит тарелка с блинами. На тарелке \( i \)-го гостя лежит \( a_i \) блинов. Каждый гость съедает один блин за одну минуту. Неожиданно присоединился ещё один человек. Необходимо переложить блины так, чтобы гости съели все блины за минимальное время. Минимальное время определяется наибольшим числом блинов на тарелках у всех гостей (включая нового). Найти это минимальное время.

Входные данные:

• \( N \) — натуральное число, не превосходящее 100 000 (количество гостей).
• Следующие \( N \) строк содержат натуральные числа \( a_i \) — количество блинов на тарелке \( i \)-го гостя. \( a_i \) не превосходят \( 2 \times 10^9 \).

Выходные данные:

Одно целое число — минимальное время.

Пример входных и выходных данных:

Решение:

Минимальное время, за которое все гости съедят блины, равно наибольшему количеству блинов на одной тарелке после перекладывания. Чтобы минимизировать это время, нужно равномерно распределить блины. Идеальный вариант — чтобы у каждого гостя было примерно одинаковое количество блинов. Однако, мы можем только перекладывать блины, а не создавать их. Новый гость также нуждается в блинах.

Пусть \( S \) — общее количество блинов у всех \( N \) гостей. Новый гость получает \( S \) блинов (по условию, он присоединяется, и гости могут переложить блины новому гостю). Затем мы должны распределить эти \( S \) блинов между \( N+1 \) человеком ( \( N \) изначальных гостей + 1 новый) так, чтобы максимальное количество блинов на одной тарелке было минимальным. Это достигается, если блины распределены максимально равномерно.

Если \( S \) — общее количество блинов, то после присоединения нового гостя, который может получить блины от других, общее количество блинов, которые нужно съесть, остается \( S \). Эти блины будут съедены \( N+1 \) гостями (включая нового). Каждый гость съедает 1 блин в минуту. Таким образом, время, которое потребуется, чтобы съесть все блины, если они будут распределены равномерно, будет \( \lceil S / (N+1) \rceil \).

Однако, в условии задачи сказано: "Необходимо переложить блины таким образом, чтобы после перекладывания гости съели все блины за минимальное время (которое равно наибольшему числу блинов на тарелках у всех гостей, включая нового гостя)." Это означает, что мы должны найти такую конфигурацию блинов на тарелках, чтобы максимальное количество блинов на одной тарелке было минимальным. Это число и будет ответом.

В приведенном примере: \( N=3 \), блины: \( a_1=1, a_2=4, a_3=2 \). Общее количество блинов \( S = 1+4+2 = 7 \). Новый гость присоединяется.

Если гость с 4 блинами отдаст 2 блина новому гостю, то на тарелках будет: 1, 2, 2 (у первого гостя, который отдал блины), 2 (у нового гостя). Максимальное количество блинов на одной тарелке = 2. Время = 2 минуты.

Алгоритм:

1. Прочитать \( N \).
2. Прочитать \( N \) чисел \( a_i \) и вычислить их сумму \( S \).
3. Рассчитать минимальное время как \( \lceil S / (N+1) \rceil \).
4. Вывести результат.

Вычисление для примера:

\( N=3 \), \( a = [1, 4, 2] \).

\( S = 1 + 4 + 2 = 7 \).

Количество гостей после присоединения нового: \( N+1 = 3+1 = 4 \).

Минимальное время = \( \lceil S / (N+1) \rceil = \lceil 7 / 4 \rceil = \lceil 1.75 \rceil = 2 \).

Ответ: 2