Вы хотите натренировать модель нейронной сети для вашей выпускной работы. В датасете находятся \(n\) изображений, размер \(i\)-го изображения равен \(a_i\) байт.
В вашем распоряжении нет мощных удаленных серверов для того, чтобы натренировать модель, поэтому вам необходимо сделать это на вашем собственном компьютере. Но есть небольшая проблема: общий размер датасета слишком большой для вашего компьютера, поэтому вы решили удалить некоторые изображения... С другой стороны, вы не хотите делать датасет слишком некачественным, поэтому вы можете удалить из него не более чем \(k\) изображений. Заметьте, что вы можете только удалять изображения, вы не можете менять их порядок.
Вы хотите удалить эти изображения оптимальным образом, поэтому вы придумали метрику (вы же все-таки data scientist), которая позволяет оценить результат удалений. Рассмотрим массив \(b_1, b_2, \ldots, b_m\) после удаления не более \(k\) изображений (\(n - k \le m \le n\)). Данные из этого массива будут загружены в компьютер блоками по \(x\) последовательных элементов каждый. Более точно:
- элементы с индексами от \(1\) до \(x\) (\(b_1, b_2, \ldots, b_x\)) принадлежат первому блоку;
- элементы с индексами от \(x + 1\) до \(2x\) (\(b_{x + 1}, b_{x + 2}, \ldots, b_{2x}\)) принадлежат второму блоку;
- элементы с индексами от \(2x + 1\) до \(3x\) (\(b_{2x + 1}, b_{2x + 2}, \ldots, b_{3x}\)) принадлежат третьему блоку;
- и так далее.
Всего блоков будет \(cnt = \left\lceil\frac{m}{x}\right\rceil\). Заметьте, что если \(m\) не делится на \(x\), то последний блок содержит меньше \(x\) элементов, и это нормально.
Пусть \(w(i)\) равно общему размеру \(i\)-го блока, то есть сумме размеров изображений внутри этого блока. Например, размер первого блока \(w(1)\) равен \(b_1 + b_2 + \ldots + b_x\), размер второго блока \(w(2)\) равен \(b_{x + 1} + b_{x + 2} + \ldots + b_{2x}\).
Значением метрики, которую вы придумали, является максимальный размер блока по всем блокам результирующего датасета. Другими словами, значение метрики равно \(\max\limits_{i=1}^{cnt} w(i)\).
Вы не хотите слишком перегружать ваш компьютер, поэтому вы хотите удалить не более \(k\) изображений таким образом, чтобы минимизировать значение метрики, описанной выше.
Выходные данные
Выведите одно число: минимальное значение метрики, описанной в условии задачи, которое возможно получить после удаления не более \(k\) изображений из датасета.
Примечание
В первом тестовом примере вы можете удалить весь массив, поэтому ответ равен \(0\).
Во втором тестовом примере вы можете удалить первый и последний элементы \(a\) и получить \(b = [1, 5, 5]\). Размер первого (и единственного) блока равен \(11\). Таким образом, ответ равен \(11\).
В третьем тестовом примере вы можете удалить второй элемент \(a\) и получить \(b = [3, 1, 3, 1, 2]\). Размер первого блока равен \(8\), а размер второго блока равен \(2\). Таким образом, ответ равен \(8\).
В четвертом тестовом примере вы можете оставить массив \(a\) без изменений и получить \(b = [2, 2, 1, 2, 2, 1]\). Размер первого блока равен \(5\), как и размер второго. Таким образом, ответ равен \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5 4
1 1 5 4 5
|
0
|
|
2
|
5 2 4
6 1 5 5 6
|
11
|
|
3
|
6 1 4
3 3 1 3 1 2
|
8
|
|
4
|
6 1 3
2 2 1 2 2 1
|
5
|