e-olymp 4514. Сортировка вагонов — А

Задача

2015-06-28 18-54-20 Скриншот экрана

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать вагонам в тупик с пути 2 или выезжать из тупика на путь запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика).

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

Вводится число N — количество вагонов в поезде (1N2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

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

Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:

  • если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число K (K1),
  • если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число K (K1).

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

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

Задача на e-olimp

Тесты

input output
33 2 1 1 32 3
44 1 3 2 1 22 11 22 3
32 3 1 0

Решение

Мы вводим переменную, которая начинается с единицы и отвечает за то чтобы вагоны выходящие из тупика шли только по порядку

затем вводим переменную, которая запоминает какой вагон заехал в тупик последним

Мы это делаем, для вычисления количества вагонов которое заехало в тупик и которое выехало из тупика. Потом мы поочередно считываем в цикле [latex]for[/latex] все номера вагонов и кидаем их всех в тупик. Но если во время этой операции мы нашли вагон с номером [latex]last\_num[/latex], то сразу пишем (в строковой поток, так как есть вероятность того, что так завести вагоны нельзя) сколько вагонов мы завели в тупик. Далее мы видим, что в тупике есть вагоны идущие по порядку, мы выводим вагоны из тупика и считаем их количество. После мы выводим это количество в строковой поток( с цифрой 2 вначале) и запоминаем сколько вагонов было завезено в тупик. Далее если мы вывели из тупика все вагоны, то выводим строковой поток, иначе выводим 0.

 

Related Images: