回分類題庫
d044: 鐵路堆疊
出處:ACMOJ 514

Difficulity : 1
Accepted : 87 Times | Submit :271 Times | Clicks : 5616
Accepted : 71 Users | Submit : 85 Users | Accepted rate : 84%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2008-10-16 09:36

Content :

在一個叫「堆疊市」的城市中有一個有名的火車站。由於地形限制以及經費的關係,火車站及唯一的鐵路的樣子如下圖:

現在火車從A方向來,預定從B方向離開。火車共有N節車廂(N ≤ 1000),並且各車廂依次以 1 到 N 來編號。你可以假設各車廂在進站之前可以單獨與其他車廂分離,也可以單獨離開車站到往 B 方向的鐵軌上。你也可以假設在任何時間火車站都可以容納所有的車廂。但是一旦一節車廂進站後,就不能再回到 A 方向的鐵軌上了,並且一旦離開車站往 B 方向後,也不能再回到車站。

現在你的任務是寫一個程式,判斷火車能否以一特定的排列方式在 B 方向的鐵軌上。

(translated by LuckyCat)

Input :

輸入含有多組測試資料。每組測試資料的第一列,有 1 個整數 N ,其意義如上所述。對於此組測試資料接下來有 0 到多個不等的測試,每個測試一列,每列有N個整數,內容為 1 ,2, ......, N 的任意排列。當遇到僅含有一個 0 的一列,代表該組測試資料結束。

N = 0 代表輸入結束,請參考 Sample Input。

Output :

對每一組測試資料的每個測試,輸出該 1, 2, ......, N 的任意排列是否可能。如果可能,請輸出 Yes,若不可能則輸出 No。

每組測試資料後亦請空一列。請參考 Sample Output。

Sample Input :

5
1 2 3 4 5
5 4 3 2 1
5 4 1 2 3
0
7
4 5 3 7 6 2 1
0
0

Sample Output :

Yes
Yes
No

Yes

Hint :

Stack

Author :

ACMOJ 514 (管理員:MrWrongAnswer)

  Solve it!   Status Forum (5)

C++
C
JAVA
19177. pcsh710742 (15 ms , 364KB)
7150. derching (51 ms , 208KB)
6641. asas (54 ms , 218KB)
40301. staycalm (66 ms , 220KB)
84897. avengertree (67 ms , 418KB)
2029. taop (19 ms , 652KB)
5008. henryokc (50 ms , 224KB)
1140. mark00lui (51 ms , 221KB)
8306. erdfcv0521 (52 ms , 218KB)
7149. derching (52 ms , 210KB)
75727. ag100j (285 ms , 5980KB)
56075. nwgs524513cja (442 ms , 21529KB)
53112. nwgs524513cja (528 ms , 24657KB)
49529. nwgs524513cja (588 ms , 16800KB)

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡