Vérifier si un tableau est triable par pile
Étant donné les nombres
1, 2, 3, ..., n dans un tableau d'ordre arbitraire, vous devez déterminer si ce tableau est triable par une pile. On dit que le tableau A est triable par pile s’il est possible, en utilisant une pile auxiliaire, d’obtenir un tableau B qui soit trié en ordre croissant lorsque l’algorithme se termine. Les opérations autorisées sont :- Retirer le premier élément de
Aet le pousser dans la pile.
- Retirer l’élément au sommet de la pile et l’ajouter à la fin de
B.
Si
B se retrouve trié en ordre croissant, alors A est triable par pile.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ).La ligne suivante contient
n entiers séparés par des espaces (1 ≤ ≤ n).Sortie
Le programme doit afficher
Yes si A est triable par pile et No sinon.Exemples
Entrée | Sortie |
4
4 1 2 3 | Yes |
3
3 2 1 | Yes |
3
1 2 3 | Yes |
4
2 4 1 3 | No |
Explication
A = [4, 1, 2, 3], S = [], B = []
- Opération 1:
A = [1, 2, 3],S = [4],B = []
- Opération 1:
A = [2, 3],S = [4, 1],B = []
- Opération 2:
A = [2, 3],S = [4],B = [1]
- Opération 1:
A = [3],S = [4, 2],B = [1]
- Opération 2:
A = [3],S = [4],B = [1, 2]
- Opération 1:
A = [],S = [4, 3],B = [1, 2]
- Opération 2:
A = [],S = [4],B = [1, 2, 3]
- Opération 2:
A = [],S = [],B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
- Opération 1:
A = [2, 1],S = [3],B = []
- Opération 1:
A = [1],S = [3, 2],B = []
- Opération 1:
A = [],S = [3, 2, 1],B = []
- Opération 2:
A = [],S = [3, 2],B = [1]
- Opération 2:
A = [],S = [3],B = [1, 2]
- Opération 2:
A = [],S = [],B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
- Opération 1:
A = [2, 3],S = [1],B = []
- Opération 2:
A = [2, 3],S = [],B = [1]
- Opération 1:
A = [3],S = [2],B = [1]
- Opération 2:
A = [3],S = [],B = [1, 2]
- Opération 1:
A = [],S = [3],B = [1, 2]
- Opération 2:
A = [],S = [],B = [1, 2, 3]
Il est impossible de trier [2, 4, 1, 3] par pile
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB