#421

Изображение таблицы

Темы: [Задачи на моделирование] [Строки]

Источники: [ Командные олимпиады, ВКОШП, 2005, Задача I ]

Задана таблица в виде количества строк. Для каждой строки задано количество ячеек в ней и ширина каждой из ячеек. Необходимо нарисовать таблицу псевдографикой (знаками -, +, |).

Максимальное время работы на одном тесте: 2 секунды

При разработке программ для просмотра веб-страниц одной из наиболее сложных задач является корректное отображение таблиц. Компания «Kozilla», в которой вы работаете, планирует разработать новую версию браузера «Waterrat» для работы в терминальном режиме и просит вас написать фрагмент ядра отображения веб-страниц, ответственный за формирование структуры таблиц.

Фрагмент, который вы должны написать, получает на вход информацию о количестве строк таблицы и ячейках этих строк и должен сгенерировать структуру таблицы и передать ее модулю, который занимается отображением таблицы на экране.

Таблица состоит из строк, каждая строка состоит из одной или нескольких ячеек, j-я ячейка i-й строки имеет ширину a_{i, j}.

По заданным параметрам таблицы постройте символическое изображение ее структуры.

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

В первой строке вводится число n – количество строк в таблице ( 1 $le$ n $le$ 100). Каждая из следующих n строк входных данных описывает одну строку таблицы.

Описание строки включает число m_i – количество ячеек в этой строке, и m_i целых чисел a_{i, 1}, a_{i, 2},..., a_{i, m_i} – ширину каждой из ячеек строки ( 1 $le$ m_i $le$ 10, 1 $le$ a_{i, j} $le$ 20).

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

Выведите символическое изображение структуры таблицы.

Изображение i-й строки таблицы должно начинаться горизонтальной линией, составленной из символов «+» (плюс) и «-» (минус). Затем должна следовать строка, содержащая пробелы и символы «|» (вертикальная черта). Первым символом строки должна быть вертикальная черта, затем a_{i, 1} пробелов, затем вертикальная черта, затем a_{i, 2} пробелов, и так далее, всего m_i блоков пробелов. После последнего блока должна следовать вертикальная черта.

После последней строки таблицы также должна следовать горизонтальная линия.

В изображении горизонтальной линии используйте символ «+», если сверху или снизу от этой позиции находится вертикальная черта, и «-» в противном случае. Горизонтальная черта должна иметь минимальную возможную длину, чтобы над каждым символом вертикальной черты следующей строки и под каждым символом вертикальной черты предыдущей строки были символы «+».

Примеры

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

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

+---+-----+-+
|   |     | |
+--++-----+-+
|  |
+--+
|  |
+--+--+-+
|     | |
+-----+-+

#429

На лифтах через пропасть

Темы: [Задачи на моделирование]

Источники: [ Командные олимпиады, ВКОШП, 2004, Задача G ]

Необходимо перебраться через пропасть по платформам. Платформы расположены в вдоль прямой OX и для каждой из них задана верхняя и нижняя точка, которых они достигают и направление движение. Требуется определить минимальное время, за которое можно достичь противоположного края пропасти.

Сережа очень любит старые игры. Недавно он нашел у себя на компьютере одну старую приключенческую игру. Управляя героем, надо перемещаться по карте и собирать различные предметы.

На определенном этапе игры Сережа столкнулся с неожиданной проблемой. Для продолжения приключений герою надо перебраться через пропасть. Для этого можно использовать последовательно расположенные лифты, которые имеют вид горизонтальных платформ. Каждый лифт вертикально перемещается туда-сюда между некоторыми уровнями. Герой может переходить между соседними платформами, однако это можно сделать только в тот момент, когда они находятся на одном уровне. Аналогично, с края пропасти на лифт и обратно можно перейти лишь в тот момент, когда лифт окажется на уровне края.

Каждый лифт имеет ширину, равную четырем метрам. В начале герой находится на расстоянии два метра от края пропасти. Он должен закончить свое путешествие в двух метрах от противоположного края пропасти. Герой перемещается со скоростью два метра в секунду. Таким образом, если герой находится в начальном положении или в центре лифта и хочет перейти на соседний лифт (или сойти с последнего лифта на противоположный край пропасти), он должен начать движение ровно за одну секунду до того момента, когда они окажутся на одном уровне. Через две секунды герой оказывается в центре соседнего лифта (или в конечном положении).

Края пропасти находятся на одном уровне. Для каждого лифта задан диапазон высот, между которыми он перемещается, начальное положение и направление движения в начальный момент. Все лифты перемещаются со скоростью один метр в секундy. Выясните, сможет ли герой перебраться на противоположный край пропасти, и если да, то какое минимальное время ему для этого понадобится.

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

В первой строке вводится целое число n – количество лифтов ( 1 $le$ n $le$ 100). Следующие n строк содержат описания лифтов.

Каждое описание состоит из четырех целых чисел: l, u, s – самое нижнее, самое верхнее и начальное положение лифта относительно края пропасти в метрах ( -100 $le$ l $le$ s $le$ u $le$ 100, l < u), и d – направление движения лифта в начальный момент (d = 1 означает, что лифт двигается вверх, d = - 1 – вниз).

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

Выведите минимальное время в секундах, необходимое для того, чтобы перебраться на противоположный край пропасти. Если перебраться на противоположный край пропасти невозможно, выведите число -1.

Примеры

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

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

#489

Тупики

Темы: [Сканирующая прямая] [Куча] [Задачи на моделирование]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2006, 2 день, Задача D ]

Есть K тупиков и расписание (время приезда и отъезда) электричек. Необходимо каждую электричку поставить в свободный тупик с минимальным номером.

На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).

Дано расписание движения электричек, в котором для каждой электрички указано время ее прибытия, а также время отправления в следующий рейс. Электрички в расписании упорядочены по времени прибытия. Поскольку вокзал — конечная станция, то электричка может стоять на нем довольно долго, в частности, электричка, которая прибывает раньше другой, отправляться обратно может значительно позднее.

Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

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

Сначала вводятся число K — количество тупиков и число N — количество электропоездов (1≤K≤100000, 1≤N≤100000). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 10⁹. Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.

Все электрички упорядочены по времени прибытия. Считается, что в нулевой момент времени все тупики на вокзале свободны.

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

Выведите Nчисел — по одному для каждой электрички: номер тупика, куда прибудет соответствующая электричка. Если тупиков не достаточно для того, чтобы организовать движение электричек согласно расписанию, выведите два числа: первое должно равняться 0 (нулю), а второе содержать номер первой из электричек, которая не сможет прибыть на вокзал.

Примеры

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

1 1
2 5

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

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

1 2
2 5
5 6

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

0 2

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

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

1
2
1

#500

Парикмахерская

Темы: [Задачи на моделирование]

Источники: [ Командные олимпиады, Московская командная олимпиада, 8 класс, 2007, Задача F ]

В парикмахерской работают три мастера. Каждый тратит на одного клиента ровно полчаса, а затем сразу переходит к следующему, если в очереди кто-то есть, либо ожидает, когда придет следующий клиент.

Даны времена прихода клиентов в парикмахерскую (в том порядке, в котором они приходили). Требуется для каждого клиента указать время, когда он выйдет из парикмахерской.

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

В первой строке вводится натуральное число N, не превышающее 100 – количество клиентов.

N строках вводятся времена прихода клиентов – по два числа, обозначающие часы и минуты (часы – от 0 до 23, минуты – от 0 до 59). Времена указаны в порядке возрастания (все времена различны).

Гарантируется, что всех клиентов успеют обслужить до полуночи.

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

Требуется вывести N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-го клиента (часы и минуты).

Примеры

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

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

10 30
10 31
10 32

#514

Кассы

Темы: [Задачи на моделирование] [Дата и время]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2007, Задача D ]

На одном из московских вокзалов билеты продают $N$ касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.

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

Сначала вводится одно целое число $N$ (0 < $N$ ≤ 1000).

В каждой из следующих $N$ строк через пробел расположены 4 целых числа, первые два из которых обозначают время открытия кассы в часах и минутах (часы — целое число от 0 до 23, минуты — целое число от 0 до 59), оставшиеся два — время закрытия в том же формате. Числа разделены пробелами.

Время открытия означает, что в соответствующую ему минуту касса уже работает, а время закрытия — что в соответствующую минуту касса уже не работает. Например, касса, открытая с 10 ч. 30 мин. до 18 ч. 30 мин., ежесуточно работает 480 минут.

Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает — на следующий день.

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

Требуется вывести одно число — суммарное время за сутки (в минутах), на протяжении которого работают все N касс.

Пояснения к примерам

1) Первая касса работает с часу до 23 часов, вторая – круглосуточно, третья – с 22 часов до 2 часов ночи следующего дня. Таким образом, все три кассы одновременно работают с 22 до 23 часов и с часу до двух часов, то есть 120 минут.

2) Первая касса работает до 14 часов, а вторая начинает работать в 14 часов 15 минут, то есть одновременно кассы не работают.

3) Вместе кассы работают лишь одну минуту – с 14:00 до 14:01 (в 14:01 вторая касса уже не работает).

Примеры

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

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

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

2
9 30 14 0
14 15 21 0

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

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

2
14 00 18 00
10 00 14 01

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