TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

85.2% (23/27)

Submission's AC Ratio

21.6% (37/171)

Description

阿華很喜歡玩益智遊戲,昨天他拿到一個遊戲,規則是這樣的:在一個 N×M 的棋盤上有一個水晶球,給定它的起始位置和目標位置,阿華必須將水晶球從起始位置移動到目標位置。移動的次數和移動的距離也是給定的,阿華只能決定移動的方向:上、下、左或右。舉個例子:下圖是一個 4×6 的棋盤,水晶球的起始位置是 (1, 1),目標位置是 (3, 5)。

如果指定水晶球必須移動三次,每次移動的距離依序是 1, 2, 3,則阿華可以將水晶球向「上」移動1 格、向「左」移動2 格,再向「下」移動3 格,即可抵達目標位置。(或是「右」、「下」、「右」也可以。)移動過程中,如果超出棋盤邊界,則會從另一頭繼續移動,例如上面的第一種解法,水晶球從 (0, 1) 向左移動2 格,會移動至 (0, 5) 這個位置。
一開始的關卡很簡單,阿華一下子就完成了。但是有一個關卡阿華想了很久,他認為這個關卡是不可能達成的。現在請你寫一個程式,幫阿華確認一個關卡是不是有可能達成。(阿華自尊心很強,你不需要告訴他該如何移動水晶球,只要告訴他這個關卡是否可能達成。)

Input Format

輸入的第一行有兩個數字 N 和 M (1 ≤ N, M ≤ 100),代表棋盤大小。第二行有四個數字 X1, Y1, X2, Y2,代表水晶球的開始位置 (X1, Y1) 和目標位置 (X2, Y2)。第三行的第一個數字 K (1 ≤ K ≤ 10,000) 為正整數,代表可移動幾次,接下去有 K 個正整數 d1, d2, …, dK(≤ 100),代表移動的距離。兩個整數之間都以一個空格隔開。

Output Format

請輸出是否可能將水晶球移至目標位置。若可以,印出 YES,否則印出 NO。

Sample Input

輸入檔範例1
4 6
1 1 3 5
3 1 2 3

輸入檔範例2
2 2
0 0 1 1
2 2 2

輸入檔範例3
2 2
0 0 1 1
2 1 1

Sample Output

輸出檔範例1
YES

輸出檔範例2
NO

輸出檔範例3
YES

Hints

本題共有四組測試資料。
第一組測試資料 1 ≤ N, M ≤ 5,K = 2,共 10 分。
第二組測試資料 1 ≤ N, M ≤ 50,1 ≤ K ≤ 5,共 30 分。
第三組測試資料 1 ≤ N, M ≤ 100,1 ≤ K ≤ 20,共 30 分。
第四組測試資料 1 ≤ N, M ≤ 100,1 ≤ K ≤ 10,000,共 30 分。

Problem Source

臺北市103學年度高級中學資訊學科能力競賽程式設計試題第一題
Set by Paupière
若測資有誤請儘快聯絡管管(?

Subtasks

For Testdata: 0 ~ 4, Score: 10
For Testdata: 5 ~ 9, Score: 30
For Testdata: 10 ~ 14, Score: 30
For Testdata: 15 ~ 19, Score: 30
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 524288 65536
1 5000 524288 65536
2 5000 524288 65536
3 5000 524288 65536
4 5000 524288 65536
5 5000 524288 65536
6 5000 524288 65536
7 5000 524288 65536
8 5000 524288 65536
9 5000 524288 65536
10 5000 524288 65536
11 5000 524288 65536
12 5000 524288 65536
13 5000 524288 65536
14 5000 524288 65536
15 5000 524288 65536
16 5000 524288 65536
17 5000 524288 65536
18 5000 524288 65536
19 5000 524288 65536