На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).
Дано расписание движения электричек, в котором для каждой электрички указано время ее прибытия, а также время отправления в следующий рейс. Электрички в расписании упорядочены по времени прибытия. Поскольку вокзал — конечная станция, то электричка может стоять на нем довольно долго, в частности, электричка, которая прибывает раньше другой, отправляться обратно может значительно позднее.
Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно.
Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.
Сначала вводятся число K — количество тупиков и число N — количество электропоездов (1≤K≤100000, 1≤N≤100000). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 109. Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.
Все электрички упорядочены по времени прибытия. Считается, что в нулевой момент времени все тупики на вокзале свободны.
Выведите Nчисел — по одному для каждой электрички: номер тупика, куда прибудет соответствующая электричка. Если тупиков не достаточно для того, чтобы организовать движение электричек согласно расписанию, выведите два числа: первое должно равняться 0 (нулю), а второе содержать номер первой из электричек, которая не сможет прибыть на вокзал.
1 1 2 5
1
1 2 2 5 5 6
0 2
2 3 1 3 2 6 4 5
1 2 1
В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью – 1, за поражение – 0 очков.
Известно, сколько очков в итоге получила каждая команда, однако результаты конкретных матчей были утеряны. Требуется восстановить одну из возможных турнирных таблиц.
В первой строке входных данных содержится одно натурально число K, не превосходящее 100 – количество команд. Во второй строке задаются через пробел K целых неотрицательных чисел, не превосходящих 2(K–1), – количество очков, набранных командами, занявшими первое, второе, …, K-е места соответственно (то есть каждое следующее число не больше предыдущего).
Выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, …, последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел – количество очков, набранных в игре данной команды с первой, второй, … командами соответственно. Количество очков – это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули.
Гарантируется, что входные данные соответствуют реальному турниру, то есть хотя бы одна таблица, соответствующая входным данным, может быть построена. Если таких таблиц несколько, выведите любую из них.
4 6 4 2 0
0 2 2 2 0 0 2 2 0 0 0 2 0 0 0 0
4 3 3 3 3
0 2 0 1 0 0 2 1 2 0 0 1 1 1 1 0
Как и в обычном тетрисе, поле в игре Strategy Tetris представляет собой "стакан" шириной в W клеток (1W109) и бесконечной высоты. В этот стакан падают сверху N фигурок (1N100000). i-я фигурка представляет собой прямоугольник шириной в Wi клеток и высотой в одну клетку; самая левая клетка фигурки имеет абсциссу ai (1aiW–Wi+1). Фигурки падают по обычным правилам: если при падении фигурка хотя бы одной своей клеткой ложится на какую-либо уже упавшую фигурку, то ее движение прекращается.
В отличие от обычного тетриса, игрок не имеет возможности вращать фигурки или смещать их по горизонтали в процессе падения — еще бы, это пришлось бы делать быстро и не было бы времени серьёзно подумать над стратегией. Единственное, что он может — это выбрать порядок, в котором эти N фигурок упадут в стакан (каждая по одному разу). Ваша задача — помочь ему выбрать такой порядок, при котором высота образовавшейся в результате падения конструкции была бы как можно меньше. (В отличие от обычного тетриса, полностью заполненная фигурками горизонталь никуда не исчезает).
На рисунке ниже приведен пример заполнения стакана фигурками из примера входных данных (порядок заполнения соответствует выходному файлу, приведенному в примере).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 2 |
| |
| 1 | 3 | ||
В первой строке входного файла записаны числа N и W, а в последующих N строках — пары чисел ai и Wi.
Выведите в выходной файл минимальную возможную высоту конструкции, а затем последовательность номеров фигурок, к этой высоте приводящую. Фигурки нумеруются натуральными числами от 1 до N в том порядке, в котором они указаны во входных данных. Если возможных вариантов несколько, выведите любой из них.
3 4 1 2 2 2 3 2
2 3 1 2