Ստուգել, թե արդյոք զանգվածը stack-sort-ի ենթակա է
Տրված են
1, 2, 3, ..., n թվերը, որոնք ներկայացված են կամայական հերթականությամբ զանգվածում։ Պետք է ստուգել, թե արդյոք տվյալ զանգվածը stack-sort-ի ենթակա է: Զանգվածը A stack-sort-ի ենթակա է, եթե հնարավոր է ստանալ վերջնական զանգված B՝ օգտագործելով օժանդակ stack (պահունակ) այնպես, որ B-ն արդյունքում դասավորված լինի աճող կարգով: Թույլատրելի գործողություններն են.- Հեռացնել առաջին էլեմենտը
A-ից ու դնել այն stack-ի վրա:
- Հեռացնել stack-ի վերևի էլեմենտը և ավելացնել այն
B-ի վերջում:
Եթե արդյունքում
B-ն դասավորված է աճող կարգով, ուրեմն A-ն stack-sort-ի ենթակա է։Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ )։Հաջորդ տողում տրված են
n ամբողջ թվեր (1 ≤ ≤ n)՝ բաժանված բացատներով։Ելք
Ծրագիրը պետք է տպի
Yes, եթե A stack-sort-ի ենթակա է, իսկ հակառակ դեպքում տպի No:Օրինակներ
Մուտք | Ելք |
4
4 1 2 3 | Yes |
3
3 2 1 | Yes |
3
1 2 3 | Yes |
4
2 4 1 3 | No |
Շարադրվածի բացատրությունը
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]
Անհնար է stack-sort անել [2, 4, 1, 3] զանգվածը
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB