Prüfe, ob ein Array stack-sortierbar ist
Gegeben sind die Zahlen 1, 2, 3, ..., n in einem Array in beliebiger Reihenfolge. Die Aufgabe besteht darin zu ermitteln, ob das gegebene Array stack-sortierbar ist. Ein Array A ist dann stack-sortierbar, wenn es mithilfe eines Hilfsstapels möglich ist, ein Array B zu erzeugen, das am Ende des Ablaufs in aufsteigender Reihenfolge sortiert ist. Die erlaubten Operationen sind:
Den ersten Wert aus
Aentnehmen und oben auf den Stapel legen.Das oberste Element vom Stapel nehmen und hinten an
Banhängen.
Wenn B am Ende in aufsteigender Reihenfolge sortiert ist, gilt A als stack-sortierbar.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ ).
In der nächsten Zeile stehen n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ n).
Ausgabe
Das Programm soll Yes ausgeben, wenn A stack-sortierbar ist, andernfalls No.
Beispiele
Eingabe | Ausgabe |
|---|---|
4 | Yes |
3 | Yes |
3 | Yes |
4 | No |
Erklärung
A = [4, 1, 2, 3], S = [], B = []
Operation 1:
A = [1, 2, 3],S = [4],B = []Operation 1:
A = [2, 3],S = [4, 1],B = []Operation 2:
A = [2, 3],S = [4],B = [1]Operation 1:
A = [3],S = [4, 2],B = [1]Operation 2:
A = [3],S = [4],B = [1, 2]Operation 1:
A = [],S = [4, 3],B = [1, 2]Operation 2:
A = [],S = [4],B = [1, 2, 3]Operation 2:
A = [],S = [],B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
Operation 1:
A = [2, 1],S = [3],B = []Operation 1:
A = [1],S = [3, 2],B = []Operation 1:
A = [],S = [3, 2, 1],B = []Operation 2:
A = [],S = [3, 2],B = [1]Operation 2:
A = [],S = [3],B = [1, 2]Operation 2:
A = [],S = [],B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
Operation 1:
A = [2, 3],S = [1],B = []Operation 2:
A = [2, 3],S = [],B = [1]Operation 1:
A = [3],S = [2],B = [1]Operation 2:
A = [3],S = [],B = [1, 2]Operation 1:
A = [],S = [3],B = [1, 2]Operation 2:
A = [],S = [],B = [1, 2, 3]
Es ist unmöglich, das Array [2, 4, 1, 3] zu stack-sortieren
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB