HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC - 2013-2014 > problem:


14-03-90. 50717 - Hurdle Jumping

IMPC - 2013-2014

Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 14-03-10. 50412 - K numbers
• 14-03-20. 50398 - Sum of kth Anti-d...
• 14-03-30. 50377 - kth Permutation
• 14-03-40. 50773 - Balanced Sum Tree
• 14-03-60. 50382 - Parkside's Other ...
• 14-03-70. 50468 - Draw Matrix - 2
• 14-03-70. 50468 - Draw Matrix - 2
• 14-03-80. 50675 - Kruja Boys
• 14-03-90. 50717 - Hurdle Jumping
• 14-04-20. 50493 - n-digit kth Prime ...
• 14-04-30. 50669 - Area of an Irregu...
• 14-04-40. 50712 - Moon algebra
• 14-04-50. 50697 - Base Stations
• 14-05-10. 50723 - Tribonacci
• 14-05-20. 50677 - The Cottage
• 14-05-20. 50413 - Valid Permutations
• 14-05-30. 50688 - Epoka Furgon

Feedback

If you notice incorrect translations in Contester, please let author know.

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.


Для отправки решений необходимо выполнить вход.

www.contester.ru