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

Задача

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

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

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

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

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

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

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

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

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

Задача на e-olimp

#include <cstdlib>
#include <iostream>
#include <sstream>
#include <vector>
 using namespace std;
 
int main(){
	int n;
	cin >> n;
 
	int a[n];
	vector<int> stalemate;
 
	int last_num = 1;									
	int len;											
	int last_n = 0;					
 
	stringstream stre;							
	for( int i=0 ; i<n ; i++ ){
		cin >> a[i];
		stalemate.push_back(a[i]);						
		if(a[i] == last_num){
			stre << 1 << ' ' << (i-last_n)+1 << endl;
 
			len = 0;
			while(stalemate.back() == last_num && last_num != n+1)
			{					
				stalemate.pop_back();								
				last_num++;											
				len++;												
			}
			last_n = i+1;						
			stre << 2 << ' ' << len << endl;			
		}
	}
	if(last_num != n+1)
	{							
		cout << 0 << endl;
	}
	else
	{
		cout << stre.str() << endl;
	}
}

#include <cstdlib>

#include <iostream>

#include <sstream>

#include <vector>

using namespace std;

int main(){

int n;

cin >> n;

int a[n];

vector<int> stalemate;

int last_num = 1;

int len;

int last_n = 0;

stringstream stre;

for( int i=0 ; i<n ; i++ ){

cin >> a[i];

stalemate.push_back(a[i]);

if(a[i] == last_num){

stre << 1 << ' ' << (i-last_n)+1 << endl;

len = 0;

while(stalemate.back() == last_num && last_num != n+1)

{

stalemate.pop_back();

last_num++;

len++;

}

last_n = i+1;

stre << 2 << ' ' << len << endl;

}

if(last_num != n+1)

{

cout << 0 << endl;

}

else

{

cout << stre.str() << endl;

}

Тесты

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

Решение

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

int last_num = 1;

15	int last_num = 1;

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

int last_n = 0;

16	int last_n = 0;

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

Related Images:

Похожее

3 thoughts on “e-olymp 4514. Сортировка вагонов — А”

Мазурок Игорь Евгеньевич says: 28/06/2015 at 16:23

— Что в этом слове не так «порядкуРешение»?
— Описание решения похоже на шутку. Сначала с цитатами объясняете как описать целую переменную, потом резко меняете курс и выдаёте слабо согласованный поток сознания. Нужно превратить это в осмысленный текст.
— Почему нет картинки?

Войдите, чтобы ответить
- Сіренко Валерія Сергіївна says: 29/06/2015 at 15:57
  
  Исправила все замечания
Мазурок Игорь Евгеньевич says: 30/06/2015 at 07:47

Самое существенное замечание по описанию алгоритма не исправлено. Например, «номера вагонов и кидаем их всех в тупик». Что «кидаем в тупик»? Вагоны? Но программы не может оперировать вагонами. Номера? Тогда тупик это переменная stalemate в Вашей программе? Так бы и написали. Используете vector как stack и не пишите об этом.
Проверил на живых людях. Ваше описание не понял никто.

Кстати, пробел ставится перед открывающей скобкой, а не после.

Войдите, чтобы ответить