Verificare se un array è stack-sortable
Dati i numeri 1, 2, 3, ..., n come array in un ordine qualsiasi, il compito è stabilire se l’array in questione sia stack-sortable (cioè ordinabile con l’ausilio di uno stack). L’array A si considera stack-sortable se è possibile ottenere un array B (ordinato in ordine crescente) impiegando uno stack ausiliario, al termine dell’esecuzione dell’algoritmo. Le operazioni consentite sono:
Rimuovere il primo elemento da
Ae spingerlo (push) nello stack.Rimuovere l’elemento in cima allo stack e aggiungerlo (append) in coda a
B.
Se B alla fine risulta ordinato in ordine crescente, allora A è stack-sortable.
Ingresso
La prima riga dell’ingresso contiene un singolo intero n (1 ≤ n ≤ ).
La riga successiva contiene n interi separati da spazi (1 ≤ ≤ n).
Uscita
Il programma deve stampare Yes se A è stack-sortable, altrimenti deve stampare No.
Esempi
Ingresso | Uscita |
|---|---|
4 | Yes |
3 | Yes |
3 | Yes |
4 | No |
Spiegazione
A = [4, 1, 2, 3], S = [], B = []
Operazione 1:
A = [1, 2, 3],S = [4],B = []Operazione 1:
A = [2, 3],S = [4, 1],B = []Operazione 2:
A = [2, 3],S = [4],B = [1]Operazione 1:
A = [3],S = [4, 2],B = [1]Operazione 2:
A = [3],S = [4],B = [1, 2]Operazione 1:
A = [],S = [4, 3],B = [1, 2]Operazione 2:
A = [],S = [4],B = [1, 2, 3]Operazione 2:
A = [],S = [],B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
Operazione 1:
A = [2, 1],S = [3],B = []Operazione 1:
A = [1],S = [3, 2],B = []Operazione 1:
A = [],S = [3, 2, 1],B = []Operazione 2:
A = [],S = [3, 2],B = [1]Operazione 2:
A = [],S = [3],B = [1, 2]Operazione 2:
A = [],S = [],B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
Operazione 1:
A = [2, 3],S = [1],B = []Operazione 2:
A = [2, 3],S = [],B = [1]Operazione 1:
A = [3],S = [2],B = [1]Operazione 2:
A = [3],S = [],B = [1, 2]Operazione 1:
A = [],S = [3],B = [1, 2]Operazione 2:
A = [],S = [],B = [1, 2, 3]
È impossibile effettuare l’ordinamento tramite stack per l’array [2, 4, 1, 3]
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB