Задача №44. Машинки
По двум однополосным дорогам едут машины. На перекрестке эти дороги сливаются в одну однополосную (машины едут как раз в ее сторону). На этом самом перекрестке стоит постовой милиционер, который регулирует движение, а именно, выбирает, с какой из двух дорог в данный момент машины будут заезжать.
В каждый момент времени либо одна из дорог является "активной", т.е. перекресток проезжают машины с этой дороги, либо регулировщик производит переключение потока на другую дорогу (в этот момент никакие машины через перекресток не едут). На то, чтобы "переключить" поток, тратится время Т.
В некоторый момент образовалась пробка. На 1-й дороге скопилось N машин, а на 2-й — M. Для каждой машины известно время, которое ей потребуется для проезда развилки, если она первая в очереди и ее дорога "активна".
Требуется разработать план действий для постового по переключению потоков, при котором среднее время ожидания машины минимально (временем ожидания машины называется время с момента образования пробки до того момента, когда данная машина заканчивает проезжать перекресток; для вычисления среднего времени суммируются времена ожидания всех машин и полученная сумма делится на общее количество машин). В начальный момент активна первая дорога.
Сначала вводятся числа T, N и M, затем N чисел — времена проезда перекрестка машинами с первой дороги (в порядке удаления от перекрестка), а затем M чисел — времена проезда перекрестка машинами со второй дороги.
<>Все числа целые неотрицательные, все времена не превосходят 100, T ≤ 100, N, M ≤ 1000, N+M > 0.В первой строке выведите одно число — минимальное среднее время ожидания c точностью 10–3. Далее выводите информацию о машинах в порядке их проезда перекрестка и о переключении потока следующим образом.
-
Для каждой машины выведите информацию в формате:
Car k from road i
где k — номер машины на своей дороге (ближайшая к перекрестку в момент образования пробки машина имеет номер 1, следующая на той же дороге — 2 и т.д.), i — номер дороги: 1 или 2.
-
Для каждого переключения потока выведите информацию:
Switch road from 1 to 2
для переключения потока с первой дороги на вторую или
Switch road from 2 to 1
для переключения потока со второй дороги на первую.
Информация обо всех событиях (переключениях и проездах через перекресток) должна выводиться именно в том порядке, в котором они происходят.
Если решений несколько, выведите любое из них.
Оценка задачи
1 балл будет набирать решение, верно работающее при N, M ≤ 10.
1 2 2 5 6 1 7
11.500 Switch road from 1 to 2 Car 1 from road 2 Switch road from 2 to 1 Car 1 from road 1 Car 2 from road 1 Switch road from 1 to 2 Car 2 from road 2