Verificar se um array é classificável via stack (pilha)
Dado um array que contém os números
1, 2, 3, ..., n numa ordem arbitrária, é necessário verificar se esse array é “stack-sortable (classificável via pilha)”. Dizemos que o array A é stack-sortable se for possível, usando uma stack (pilha) auxiliar, obter um array B de forma que, ao final da execução do algoritmo, B esteja ordenado em ordem crescente. As operações permitidas são as seguintes:- Remover o primeiro elemento de
Ae empilhá-lo na stack.
- Remover o elemento do topo da stack e adicioná-lo ao final de
B.
Se, ao final,
B estiver em ordem crescente, então A é stack-sortable.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).A linha seguinte contém
n inteiros separados por espaço (1 ≤ ≤ n).Saída
O programa deve imprimir
Yes se A for stack-sortable e No caso contrário.Exemplos
Input | Output |
4
4 1 2 3 | Yes |
3
3 2 1 | Yes |
3
1 2 3 | Yes |
4
2 4 1 3 | No |
Explicação
A = [4, 1, 2, 3], S = [], B = []
- Operação 1:
A = [1, 2, 3],S = [4],B = []
- Operação 1:
A = [2, 3],S = [4, 1],B = []
- Operação 2:
A = [2, 3],S = [4],B = [1]
- Operação 1:
A = [3],S = [4, 2],B = [1]
- Operação 2:
A = [3],S = [4],B = [1, 2]
- Operação 1:
A = [],S = [4, 3],B = [1, 2]
- Operação 2:
A = [],S = [4],B = [1, 2, 3]
- Operação 2:
A = [],S = [],B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
- Operação 1:
A = [2, 1],S = [3],B = []
- Operação 1:
A = [1],S = [3, 2],B = []
- Operação 1:
A = [],S = [3, 2, 1],B = []
- Operação 2:
A = [],S = [3, 2],B = [1]
- Operação 2:
A = [],S = [3],B = [1, 2]
- Operação 2:
A = [],S = [],B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
- Operação 1:
A = [2, 3],S = [1],B = []
- Operação 2:
A = [2, 3],S = [],B = [1]
- Operação 1:
A = [3],S = [2],B = [1]
- Operação 2:
A = [3],S = [],B = [1, 2]
- Operação 1:
A = [],S = [3],B = [1, 2]
- Operação 2:
A = [],S = [],B = [1, 2, 3]
É impossível classificar via stack o array [2, 4, 1, 3]
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB