e-olymp 1776. Рельсы

Ссылка на условие задачи: http://www.e-olymp.com/ru/problems/1776.

Ссылка на засчитанное решение.

В городе PopPush находится известная железнодорожная станция. Страна, в котором находится город, невероятно холмистая. Станция была построена в прошлом веке. К сожалению, в то время средства для постройки были крайне ограничены, поэтому удалось построить только одну железнодорожную колею. Более того, выяснилось, что станция может быть только тупиковой (см. рисунок), и из-за отсутствия свободного места может иметь только одну колею.

Иллюстрация

Местная традиция гласит, что каждый поезд приходящий со стороны A продолжает свое движение в направлении B, при этом его вагоны перестанавливаются в некотором порядке. Предположим, что каждый поезд, приходящий из направления A, имеет n1000 вагонов, пронумерованных в возрастающем порядке 1, 2, …, n. Ответственный за реорганизацию вагонов должен знать, возможно ли перевезти их в направлении B в порядке a1, a2, …, an. Помогите ему написать программу, которая определит возможна ли такая перестановка вагонов. Вагоны можно отсоединять от поезда до того как они попадут на станцию и можно их отдельно передвигать пока все они не буду находиться в направлении B. На станции в любой момент времени может находиться любое количество вагонов. Но если вагон зашел на станцию, он уже не может вернуться на колею в направлении A, а также если он уже выехал в направлении B, то уже не может вернуться на станцию.

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

Состоит из нескольких тестов. Каждый тест кроме последнего описывает один поезд и возможно несколько требований для его реорганизации. Первая строка теста содержит целое число n. Каждая из следующих строк теста содержит перестановку 1, 2, …, n. Последняя строка блока содержит 0.
Последний тест состоит из единственной строки, содержащей 0.

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

Для каждой входной строки, содержащей перестановку чисел, следует вывести Yes, если можно совершить указанную перестановку вагонов, и No иначе. После вывода ответов на все перестановки каждого теста следует вывести пустую строку. Для последнего нулевого теста ничего выводить не следует.

Решение

Для решения данной задачи нам нужна переменная number, которая будет реализовывать нумерацию вагонов, иными словами, он будет считывать из потока ввода номер который нам нужно вывезти из тупика первым.
Пока введенное число не равняется нулю (что указывает на конец ввода) мы считываем количество вагонов в следующих поездах.
Мы сразу считываем последовательность поездов которую нужно получить в строку, если данная строка не является нулевой (обратное указывает на что количество поездов с таким количеством вагонов закончилась), то мы помещаем эту строку в строковой поток и считываем первый вагон что мы должны найти и вывезти из тупика.
Логично, что все вагоны отличные от данного помещаются в тупик (у нас это вектор, который используется как стек), если мы нашли вагон с нужным нам номером, то пока вагоны в тупике идут так как нам нужно (для того чтобы это определить, мы после каждого выведенного вагона считываем новый number), мы выводим их из тупика.
Если случается так, что мы поместили все вагоны в тупик, и при этом не нашли следующий number, то это означает, что следующий number был введен перед предшествующим ему вагоном, что и указывает на невозможность выполнения данной перестановки, по средством тупиковой станции.

Код программы: http://ideone.com/2p9seU.

Куленюк Денис Віталійович
Куленюк Денис Віталійович

Latest posts by Куленюк Денис Віталійович (see all)

One thought on “e-olymp 1776. Рельсы

  1. — «переменная number, которая будет реализовывать» скалярная переменная может использоваться, но не реализовывать.
    — «он будет» — кто он.

    Такое ощущение, что Вы с Серенко увлекаетесь одинаковыми… а, впрочем, ладно.

    Напишите осмысленный текст в описании.

Добавить комментарий