Ideia em como fazer o programa

Question

Há uma famosa estação de trem na cidade PopPush. Esta cidade fica em um país incrivelmente acidentado e a estação foi criada no último século. Infelizmente os fundos eram extremamente limitados naquela época. Foi possível construir somente uma pista. Além disso, devido a problemas de espaço, foi feita uma pista apenas até a estação (veja figura abaixo).
 

A tradição local é que todos os comboios que chegam vindo da direção A continuam na direção B com os vagões  reorganizados, de alguma forma. Suponha que o trem que está chegando da direção A tem N <= 1000 vagões numerados sempre em ordem crescente 1,2, ..., N. O primeiro que chega é o 1 e o último que chega é o N. Existe um chefe de reorganizações de trens que quer saber se é possível reorganizar os vagões para que os mesmos saiam na direção B na ordem a1, a2, an..

O  chefe pode utilizar qualquer estratégia para obter a saída desejada. No caso do desenho ilustrado acima, por exemplo, basta o chefe deixar todos os vagões entrarem na estação (do 1 ao 5) e depois retirar um a um: retira o 5, retira o 4, retira o 3, retira o 2 e por último retira o 1.  Desta forma, se o chefe quer saber se a saída 5,4,3,2,1 é possível em B, a resposta seria Yes. Vagão que entra na estação só pode sair para a direção B e é possível incluir quantos forem necessários para retirar o primeiro vagão desejado.

Entrada

O arquivo de entrada consiste de um bloco de linhas, cada bloco, com exceção do último, descreve um trem e possivelmente mais do que uma requisição de reorganização. Na primeira linha de cada bloco há um inteiro N que é a quantidade de vagões. Em cada uma das próximas linhas de entrada haverá uma permutação dos valores 1,2, …, N. A última linha de cada bloco contém apenas 0. Um bloco iniciando com zero (0) indica o final da entrada.

Saída

O arquivo de saída contém a quantidade de linhas correspondente às linhas com permutações no arquivo de entrada. Cada linha de saída deve ser Yes se for possível organizar os vagões da forma solicitada e No, caso contrário. Há também uma linha em branco após cada bloco de entrada. No exemplo abaixo,  O primeiro caso de teste tem 3 permutações para 5 vagões. O ultimo zero dos testes de entrada não devem ser processados.

Exemplo de Entrada	Exemplo de Saída
5 5 4 3 2 1 1 2 3 4 5 5 4 1 2 3 0 6 1 3 2 5 4 6 0 0	Yes Yes No Yes

Answer 1

Interesting problem. :)

BUT

This seems like an exam of some sort.

To me the instructions seem incomplete or wrong.

For instance, output "54123" is marked as NO, while I can easily make this arrangement:

Organizing the trains for order 54123

coming from A	station	going to B
54321
5432	1
543	12
54	123
54	12	3
54	1	23
54		123
5	4	123
5		4123
	5	4123
		54123

So, I'd advise getting the instructions cleaned up. Also, if this is an exam, maybe you should do it first and post your code if you get stuck.

Update

If we think the input line 5 4 1 2 3 means that the trains leaving toward B should be 5, 4, 1, 2, 3 (that is, 3 leaves first, then 2, then 1, then 4 and 5 last) then it is a possible combination as showed above.

On the other hand, if we interpret this as the trains should leave and 3 2 1 4 5 (i.e. 5 leaves first, then 4, then 1, then 2 and 3 last), then it is indeed an unsolvable problem with the given rules (A --> Station --> B is the only direction cars can move)

Answer 2

Preciso de uma ajuda nesse algoritmo.

Comments

Share what you have done so far and I'm happy to show what is wrong (if any).

This particular problem has 2 parts.

1. Coming up with an algorithm to solve the problem.
2. Implementing this in a given programming language.

So think about the data structures you should have that represent A, S(tation) and B.

Make sure the rules are clear (in which direction can the cars move).

After this, you should try to come up with some sort of algorithm to attempt to find if a permutation is possible or not.

As for coding, at least the reading the input should be fairly straight-forward to do.