Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Arnold Drita.
Hurdle Jumping
Epoka University is organizing a new Olympics club,
which includes all famous Olympics sports. Andi,
who is a student in CEN department, wants to take
part in Hurdle Jumping. This sport consists of a
series of obstacles, which must be passed over in
order to finish the race. Now, because they want
the most number of participants (most of which cannot
jump the obstacles) it is allowed for them to change
tracks in order to skip the obstacles. Andi wants to
beat Ardit, who is in CE department. He is his N.1
rival, so a tie is not accepted!
Question:
Andi cannot jump through the hurdles. He has to skip
them, by changing tracks left or right.
Ardit is fit. And, he obeys the rules.
He jumps over the obstacles. He does so with
half the speed he runs (jumping over an obstacle
takes twice the time that he runs on an empty field).
Anyone can start from any track they want.
Tell if there is any chance of Andi beating Ardit.
Input specification
First you are given a number 'n' (2 ≤ n ≤8) which
is the size of the track (nXn) and an integer
's' (the seconds/unit speed of Andi) and 'z'
(the seconds per unit speed of Ardit) (1≤ (s,z) ≤1000).
Then you are given a number h (0≤ h ≤64) which is
the number of hurdles. And then, you are given 2*h
numbers, the x and y coordinates of the hurdles
(0,0 being the upper left corner, and (n-1, n-1)
being the lower right corner).
Output specification
Output "Yes" if there is a way for Andi to
beat Ardit, and "No" if there's no way for
Andi to finish faster than Ardit.
Sample Input
5 1 1
12
0 1
0 3
0 4
1 0
1 2
2 1
2 3
2 4
3 3
3 4
4 0
4 1
|
Sample Output
Yes
|
Explanation:
There is a way: The best way for Ardit would
be that he starts at the cell (1,0) and goes
in a straight line up to cell (1, 4). This would
cost him 7 seconds(3 empty squares each for
1sec, and 2 obstacles each with 2sec=>3*1+2*2=7sec)
For Andi, he would start at (3, 0) and go until
(3, 2) then turn right at (4,2) and then straight
to (4, 4). There are 6 empty squares, each with
1sec time, which means 6sec. So he can beat Ardit.
Для отправки решений необходимо выполнить вход.
|