2002 Canadian Computing Competition, Stage 2

Day 2, Problem 1: Duathlon

A duathlon is a race that involves running r km and cycling k km. n contestants have entered the race; each contestant has different running and cycling speeds. One of the contestants has bribed the organizers to set r and k so that he can win by the maximum margin. You are to determine if this is possible and, if so, give r and k.

Note also that if the cheater ties with another contestant, it counts as a "win".

Input

The first line of input contains an integer t, the total distance of the race, in km. That is, r + k = t. The next line contains an integer n, the number of competitors. For each contestant, a line follows with two real numbers giving the running and cycling speed for that contestant. The last line of input gives the running and cycling speed of the contestant who has bribed the organizers. You may assume t does not exceed 100 km/h and n does not exceed 20.

Output

If it is possible to fix the race as describe above, print a message giving r and k, and the amount by which the cheater will win the race, accurate to two decimal places as in the sample below. If it is not possible, print "The cheater cannot win."

Sample Input 1

Sample Output 1

The cheater can win by 612 seconds with r = 14.29km and k = 85.71km.

Sample Input 2

Sample Output 2

All Submissions
Best Solutions

Point Value: 20
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 18, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

For some cases, there are multiple correct answer. Is there a guideline on which answer I should output? 

I passed by minimizing r

In the sample test case 1, it is possible to get 612.15 seconds (achieved by r = 14.287 km and k = 85.713 km), rounded to two decimal places. But the answer is 612 seconds. So is the amount of seconds the cheater can win by rounded to 0 decimal places or two decimal places? I tried rounding it to 0 decimal places, but I got a ton of wrong answers. Thank you very much! 

Round to 0 decimal places. You are simply not outputting the correct values.

"You may assume t does not exceed 100 km/h"

I assume it means t doesn`t exceed 100 km

Is the 612s the comparison between the original winner's time with the old distances and the cheater's new time with the new distances?

No, it's simply how much he can win by - assuming optimal distances, the difference between his time and the the time of the next-fastest person.