TopCoder

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

70.0% (7/10)

Tags

Description

派大星收集了一堆上好美盤,他希望把這些盤子按照另一個方式排好,但因為他家實在太小了,只有一張餐桌可以放上好美盤,因此他只能用以下的方式整理這些盤子:

原本的盤子從上到下按照了編號 1,2,3,4,5,...,m 堆成一疊在餐桌的起始區上,你可以做以下兩種操作

  • 從餐桌的起始區那一疊盤子最上面拿盤子,你可以選擇把這個盤子堆到暫放區目標區的最上面。
  • 暫放區最上面的盤子放到目標區的最上面。

除此之外的操作(譬如說將盤子放到地上或從目標區的盤子拿去別的地方)都因為空間太小所以沒辦法做。換句話說,你只能做以上的兩種操作。

接下來給你一些 1m 的目標排列,求是否可能在有限多的操作內把目標區的盤子排列跟目標排列一樣(給的盤子的順序是由下到上)。此外,必須要回答 n 個這樣的問題才會算 OK。你可以假設每一個問題都是獨立的,也就是說回答每一個目標排列之前,所有的盤子都會再次依照編號回到起始區)。

Input Format

輸入第一行為兩個數字 m,n,代表接下來有 m 個上好美盤以及 n 目標排列。
接下來 n 行,每行是一個 1m 的目標排列。

  • 0<n10
  • 0<m200000

Output Format

對每行輸入,若可以達成目標排列則輸出 Y,不可則輸出 N

Sample Input 1

5 2
1 2 3 4 5
5 4 1 2 3

Sample Output 1

Y
N

Sample Input 2

6 3
6 5 4 3 2 1
1 2 3 4 5 6
1 2 3 6 4 5

Sample Output 2

Y
Y
N

Hints

Problem Source

UVA 514

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2