Генка Короткевич и студентики

[Laguna]

Доброго времени суток, господа. Столкнулся с такой задачей:
Михаил Владимирович, суровый преподаватель факультета прикладной магии и иллюзии Байтландского Государственного университета задал студентам лабораторную работу, состоящую из задач на различные темы. Общее кол-во тем равно $N$, и они пронумерованы от 1 до $N$ в некотором порядке, при этом на i-ю тему Михаил Владимирович задал $A_i$ задач. Поскольку задачи выданы всем одинаковые, студенты решили объединить усилия. Обычный студент может решить одну задачу на любую тему за один день. К счастью для студентов, среди них присутствует 10-классник Гена, посещающий занятия ради любопытства. Гена способен решить до $X$ задач включительно за день, однако задачи Михаила Владимировича настолько суровы, что даже Гена не может решать задачи на разные темы в один и тот же день. Всего у Михаила Владимировича учится $K$ студентов. Помогите студентам и школьнику Гене так распределить обязанности, чтобы решить все задачи за наименьшее кол-во дней.
Формат входных данных:
$1 \leqslant N \leqslant 10^9$, $0 \leqslant X, K \leqslant 10^9$, $1 \leqslant X + K$, $1 \leqslant A_i \leqslant 10^9$.
ограничение по времени - 2 секунды, ограничение по памяти - 256 Мб.
Я решил использовать бинарный поиск по ответу, но не понимаю, как можно быстро отвечать на вопрос: "Можно ли решить все задачи за x дней?". По факту, у нас есть как бы $x \cdot K$ квадратиков размера 1 на 1 и $x$ прямоугольников размера 1 на $X$, и надо ими покрыть все прямоугольники, соответствующие каждой теме. Дальше идей нет. Прошу помощи

[mihaild]

Laguna в сообщении #1660552 писал(а):

По факту, у нас есть как бы $x \cdot K$ квадратиков размера 1 на 1 и $x$ прямоугольников размера 1 на $X$, и надо ими покрыть все прямоугольники, соответствующие каждой теме

Так жадность же.

(Оффтоп)

Меня несколько смущают имя и отчество преподавателя, встречающиеся на https://cs.hse.ru/ai/courses/152247386.html

[waxtep]

Я бы так попробовал:

$$a_i=\lfloor{A_i/X}\rfloor, r_i=A_i-X\cdot a_i, A=\sum{a_i}, R=\sum{r_i}$$

Далее, если $A=\lceil{R/K}\rceil$, то это уже прямо ответ, если же левая часть больше, значит, Гене надо помочь и забрать у него часть задач; ответ вроде бы тоже выписывается явно. Остается третий случай, когда у Гены слишком мало полных блоков по $X$ задач; здесь уже нужно что-то немного запрограммировать, чтобы подобрать такое $\Delta A$, чтобы выполнялось

$$A+\Delta A=\left\lceil{\frac{R-\sum_{i=1}^{\Delta A}{r_i}}{K}}\right\rceil$$

(при этом подразумевается предварительная сортировка $r_i$ по убыванию; хватит ли для сортировки времени и места - не пытался прикинуть)

[mihaild]

Так, я вот это не заметил.

Laguna в сообщении #1660552 писал(а):

$1 \leqslant N \leqslant 10^9$

Тут точно всё правильно? Прочитать за 2 секунды несколько гигабайт, в принципе, возможно, но требует весьма нетривиальных усилий.

[waxtep]

mihaild в сообщении #1660559 писал(а):

Прочитать за 2 секунды несколько гигабайт, в принципе, возможно, но требует весьма нетривиальных усилий

Да, вот числа выглядят довольно астрономически, я поэтому в скобочках оставил комментарий, что не прикидывал реалистичность исполнения в рамках заданных ограничений на время и память. Можно, кстати, избежать сортировки $r_i$, а просто в рамках начальной процедуры определения $a_i,r_i$ заполнить два массива размера $X-1$: в одном количество тем для данного остатка $r_i$ (нулевые остатки не интересуют), а в другом кумулятивная сумма количества заданий, начиная от бОльших $r_i$ к меньшим. Это по идее сделает и третий случай быстро вычислимым

[Laguna]

mihaild в сообщении #1660559 писал(а):

Тут точно всё правильно? Прочитать за 2 секунды несколько гигабайт, в принципе, возможно, но требует весьма нетривиальных усилий.

Да, Вы правы, перед сном создавал тему и чуток ошибся. Правильный формат такой: $1 \leqslant N \leqslant 10^5$