先前李老闆參加了東南亞五日三夜______遊,在抵達一個貧窮的村落時,看到了村莊內的小孩們長期缺乏營養、醫療、教育的情況之後,決定改造這個村莊,提供營養的食物、建立醫療設施、教育機構等。
首先為了能夠順利運送物資,大老闆們決定在這個地方建立鐵路運輸系統。車站及鐵路的樣子如下圖:
車廂的以$1$到$N$來編號,一開始所有的車廂都在A方向,以$1$到$N$的順序排好,編號越小的在越前面(靠近中間車站(station)的方向)。
現在需要把這些物資運往B方向,但唯一的運送方法只能藉由中間的車站來運輸,車站類似一個堆疊結構,先進入車站的車廂必須等後進入的車廂都離開車站後才能離開車站。車廂都是可以獨立移動的,一旦一個車廂往車站移動後就不能返回A方向;往B方向移動之後也不能再回到車站。車站的空間很大,可以容納所有車廂。
工人們希望車廂能夠以特定的方式排列在B方向上,以方便作業。你的任務是寫一個程式,檢測這個鐵路系統是否能使得全部的車廂以一特定的順序排列在B方向的鐵軌上。
輸入的第一行是一個正整數$T ( 1 \leq T \leq 10)$,代表共有幾組測試資料。每組測試資料的第一行是一個數$N( 1 \leq N \leq 10^5)$,代表車廂的數量。接著第二行有$N$個整數,內容為$1, 2, \cdots , N$的任意排列,為工人們所希望的排列方式。
對每一組測試資料,輸出該$1, 2, \cdots , N$的任意排列是否可能。如果可能,請輸出Yes,若不可能則輸出No。
和平真好。
UVa
NEOJ Problem 19
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~5 | $N \leq 10$ | 60 |
2 | 6~7 | $N \leq 1000$ | 20 |
3 | 8~9 | $N \leq 100000$ | 20 |