Problem
スタックを使用して一連の数値を並べ替えられるかどうかを判断するために必要です。
電車が 1 番線から袋小路に到着しました (写真を参照)。 1 両または数両の先頭車両を一度に列車から外して行き止まりにすることは許可されています (ご希望であれば、列車全体を一度に行き止まりにすることもできます)。その後、いくつかの貨車を 2 番線の側に移動します。その後、さらに数台の貨車を行き止まりまで移動し、再び貨車の一部を 2 番線の側に移動します。以下同様に、各貨車が1 番線から行き止まりまで 1 回だけ走行し、2 番線で行き止まりから出る。2 番線から行き止まりに入る、または 1 番線の行き止まりから出ることは禁止されている。行き止まりに入らずに道 1 から道 2 に行くことはできません。
列車の車両が最初にどのような順序で進むかはわかっています。表示された操作を使用して、列車を順番に (行き止まりから離れた 2 番線に沿って走行する列車の先頭から数えて、最初に 1 台目、次に 2 台目、というように) 進行させる必要があります。プログラムを作成して、それが実行できるかどうかを判断します。
入力
数値 N を入力してください。電車の車両の数 (\(1<=N<=2000\))。次に、1番線を行き止まりに向かって走行する列車の先頭から順に号車番号を並べます。車には 1 から N までの自然数が付けられており、それぞれの番号が 1 回だけ出現します。
出力
電車が行き止まりから 2 番線に入るときに、先頭から数えて 1 から N の順に車両を進行させることはできますか? 可能であれば、メッセージ YES を表示します。 それが不可能な場合は、NO を出力します。
例
<頭>
| # |
入力 |
出力 |
メモ |
<本体>
| 1 |
3
3 2 1
| はい |
列車全体を行き止まりにしてから、完全に 2 番線に移動する必要があります |
| 2 |
4
4 1 3 2
|
はい
|
まず、2 台のワゴンを行き止まりに持っていく必要があります。そのうちの 1 台は行き止まりに残され、もう 1 台は行き止まりに残されます。 2 番線まで移動させ、さらに 2 台の車を行き止まりまで移動させ、行き止まりに立っている 3 台の車を 2 番線まで移動させます |
| 3 |
3
2 3 1
| いいえ |
|