Сортировка вагонов — B
К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т. д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.
Технические условия
Входные данные
Вводится число [latex]N[/latex] — количество вагонов в поезде [latex]\left(1\leq N\leq100\right)[/latex]. Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от [latex]1[/latex] до [latex]N[/latex], каждое из которых встречается ровно один раз.
Выходные данные
Если сделать так, чтобы вагоны шли в порядке от [latex]1[/latex] до [latex]N[/latex], считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> using namespace std; struct stack{ //стек int truck[100]; int length = 0; int pop (){return truck[--length];} void push (int x){truck[length++] = x;} int front () {return truck[length-1];} int size () {return length;} }car; int main() { int amount_n; cin >> amount_n; //Ввод (количество вагонов) int n; int count = 1; while (cin >> n){ //Цикл (для ввода нового вагона) car.push(n); //заводим в стек новый вагон if (n == count){count++; car.pop();} //проверяем, если вагон подходит, то выводим его на путь 2 while (car.size() > 0){ //т.к. перед подходящим вагоном может стоять следующий подходящий вагон или несколько вагонов ,то пока стек не пуст будем проверять последние вагоны в стеке if (car.front() == count){count++; car.pop();} //если вагон подходит выводим на путь 2 else break; } } if (car.size() == 0) {cout << "YES" << endl;} //если стек пуст, то все вагоны были выведены на путь 2 else cout << "NO" << endl; return 0; } |
Ссылка на код : № 4513 , ссылка на решение на e-olimp : http://www.e-olimp.com.ua/solutions/1935588