1037 . 水晶球 (Crystal Ball)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

86.4% (121/140)

Submission's AC Ratio

17.9% (183/1025)

Tags

北市賽 2014-北市賽 DP

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

Sample Output 1

YES

Sample Input 2

2 2
0 0 1 1
2 2 2

Sample Output 2

NO

Sample Input 3

2 2
0 0 1 1
2 1 1

Sample Output 3

YES

Hints

Problem Source

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

Subtasks

No. Testdata Range Constraints Score
1 0~4 1 ≤ N, M ≤ 5，K = 2 10
2 5~9 1 ≤ N, M ≤ 50，1 ≤ K ≤ 5 30
3 10~14 1 ≤ N, M ≤ 100，1 ≤ K ≤ 20 30
4 15~19 1 ≤ N, M ≤ 100，1 ≤ K ≤ 10,000 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 262144 1
1 5000 524288 262144 1
2 5000 524288 262144 1
3 5000 524288 262144 1
4 5000 524288 262144 1
5 5000 524288 262144 2
6 5000 524288 262144 2
7 5000 524288 262144 2
8 5000 524288 262144 2
9 5000 524288 262144 2
10 5000 524288 262144 3
11 5000 524288 262144 3
12 5000 524288 262144 3
13 5000 524288 262144 3
14 5000 524288 262144 3
15 5000 524288 262144 4
16 5000 524288 262144 4
17 5000 524288 262144 4
18 5000 524288 262144 4
19 5000 524288 262144 4
Submit
Back to Top