Algoritmi e Strutture Dati

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:
  1. Rimuovere il primo elemento da A e spingerlo (push) nello stack.
  1. 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 4 1 2 3
Yes
3 3 2 1
Yes
3 1 2 3
Yes
4 2 4 1 3
No

Spiegazione

A = [4, 1, 2, 3], S = [], B = []
  1. Operazione 1: A = [1, 2, 3], S = [4], B = []
  1. Operazione 1: A = [2, 3], S = [4, 1], B = []
  1. Operazione 2: A = [2, 3], S = [4], B = [1]
  1. Operazione 1: A = [3], S = [4, 2], B = [1]
  1. Operazione 2: A = [3], S = [4], B = [1, 2]
  1. Operazione 1: A = [], S = [4, 3], B = [1, 2]
  1. Operazione 2: A = [], S = [4], B = [1, 2, 3]
  1. Operazione 2: A = [], S = [], B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
  1. Operazione 1: A = [2, 1], S = [3], B = []
  1. Operazione 1: A = [1], S = [3, 2], B = []
  1. Operazione 1: A = [], S = [3, 2, 1], B = []
  1. Operazione 2: A = [], S = [3, 2], B = [1]
  1. Operazione 2: A = [], S = [3], B = [1, 2]
  1. Operazione 2: A = [], S = [], B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
  1. Operazione 1: A = [2, 3], S = [1], B = []
  1. Operazione 2: A = [2, 3], S = [], B = [1]
  1. Operazione 1: A = [3], S = [2], B = [1]
  1. Operazione 2: A = [3], S = [], B = [1, 2]
  1. Operazione 1: A = [], S = [3], B = [1, 2]
  1. 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

To check your solution you need to sign in
Sign in to continue