0248. Топливо

Input file name:	fuel.in
Output file name:	fuel.out
Time limit:	2 s
Memory limit:	256 megabytes

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

Пилл Баучер, председатель Ассоциации СуперМотоциклистов (далее – АСМ), стремясь прояснить ситуацию, немедленно обзвонил своих знакомых и выяснил числа f_i – имеющиеся количества топлива на каждой из n городских заправочных станций супермотоциклов (1 ≤ i ≤ n). Числа f_i измеряются в количествах полных баков. Расположение станций позволило Пиллу установить c_i – количество участников АСМ, которые с утра, ещё до открытия, займут очередь за топливом у станции с номером 1 ≤ i ≤ n.

В городе П. все станции открываются одновременно, в условный момент 0, после чего каждому покупателю начнут отпускать в руки ровно по одному баку топлива. Раздача всем участникам из очереди по одному баку топлива занимает ровно одну единицу времени. Конечно, азартные участники АСМ не ограничатся одной покупкой, все они снова и снова будут занимать очередь, пока станция не закроется. Станция закрывается в тот момент, когда имеющегося на ней топлива становится недостаточно, чтобы раздать его всем участникам из очереди в очередную единицу времени. В момент закрытия станции все её утренние покупатели немедленно разделяются на группы людей, которые, чтобы продолжить закупки, отправляются к соседним заправкам. Список соседних заправок, упорядоченный по расстоянию от текущей, вывешен на каждой заправке.

Формирование групп происходит по следующим правилам:

1. Все участники очереди разбиваются на группы для тех и только тех соседних заправок, которые еще открыты и при этом не закрываются в тот же момент, что и данная. Если таких заправок нет, участники очереди расходятся по домам.
2. Численность групп формируется как можно более равномерно, так, чтобы наибольшее количество участников группы минимально отклонялось от наименьшего количества.
3. Группы с наибольшим количеством участников, отправляются в первые (ближайшие) пункты вывешенного на заправке списка.
4. Новые участники добавляются в очереди на соседних заправках и помогают тем, кто там уже есть, раскупать топливо.
5. Каждая группа участников добирается до соседней заправки в течение одной единицы времени. Таким образом, если заправка закрылась в момент времени t, участники, покупавшие на ней топливо, займут очереди на соседних заправках в момент времени t + 1.

Помогите Пиллу Баучеру для каждой заправки узнать момент времени, в который она закроется.

Формат входного файла

Во входном файле в первой строке содержится одно целое число n – количество заправок (1 ≤ n ≤ 10⁵). Во второй строке содержится n чисел f_i, которые указывают начальные количества баков топлива на каждой заправке (1 ≤ f_i ≤ 10⁹). В третьей строке содержится n чисел c_i – первоначальное количество человек в очереди к каждой заправке (1 ≤ c_i ≤ 10⁹).

Информация о списках ближайших заправок занимает n строк, каждая из которых содержит целое число – количество ближайших заправок, за которым следуют номера ближайших заправок в порядке возрастания расстояния. Гарантируется, что суммарное количество заправок во всех списках не превосходит 10⁵.

Формат выходного файла

Выходной файл должен содержать n строк. В i–той из них должно быть записано единственное целое число – момент закрытия заправки с номером i.

Пример:

fuel.in	fuel.out
5 7 10 7 8 6 4 6 6 1 5 1 2 2 5 4 0 2 2 3 2 2 3	1 1 1 2 1
4 1 1 1 1 1 1 1 1 1 2 3 1 3 4 1 2 1 2	1 1 1 1
4 1 4 1 1 1 1 1 1 1 2 3 1 3 4 1 2 1 2	1 2 1 1
4 1 5 1 1 1 1 1 1 1 2 3 1 3 4 1 2 1 2	1 2 1 1
4 1 20 1 1 2 3 2 2 1 2 3 1 3 4 1 2 1 2	0 2 0 0

Source: XXIII Городская олимпиада школьников г. Петрозаводска по информатике
Author: Денис Денисов

Discuss       Submit a solution



Printable version