10385 - Duathlon

[Jucovschi Constantin]

How to solve 10385

[Adil]

how about brute force?

[Miguel Angel]

I was doing 10385, then i found something that i need to know
The speed of the contestants is km/h, m/s ??
Without this my algo cannot know the answer.

thanks in advance if someone can tell me

[Miguel Angel]

Km. / H
BTW, i did a mistake in my implementation which got me shock and got me confused about if it was Km/H.

[Caesum]

Any hints on how to avoid problems with rounding ? I can barely obtain the given answers and then only if I make some assumptions about rounding. If I try to be more accurate then the sample answer appears to be incorrect as it appears to be closer to 14.2839 or 14.28 and yet the answer given is 14.29.......

[Caesum]

nevermind....... was just my miscomputations........

[serur]

What's the output for this?

Code: Select all

100
1
2 3

7
2
3 4
4 3

100
9
25 20
40 12
37 23
9 49
17 19
33 5
67 3
34 11
21 30

[coze]

Hi serur.

I checked with assert that n is greater than 1.

Input:

Code: Select all

7
2
3 4
4 3

100
9
25 20
40 12
37 23
9 49
17 19
33 5
67 3
34 11
21 30

My output:

Code: Select all

The cheater can win by 2099 seconds with r = 7.00km and k = 0.00km.
The cheater can win by 1270 seconds with r = 21.53km and k = 78.47km.

Hope it helps.

[serur]

Thanks coze. This is my source code, it gets WA. What I did is a ternary search...

Code: Select all

CUT AFTER AC


[coze]

Try using "%.0lf" instead of "%d".

Code: Select all

printf("The cheater can win by %.0lf seconds with r = %.2lfkm and k = %.2lfkm.\n",
       (f(left)),left,total-left);

[serur]

Thanks coze, your suggestion was the very thing. Got it AC at last

[DeadLock]

what is the output for

Code: Select all

10
2
5 5
10 10

[DeadLock]

got accepted, it seems that no case on the judge similar to that one

[SePulTribe]

Remember to set precision to 0.001 if using ternary search! Caused me lots of headaches.

[docardoso]

Can someone the idea behind this ternary search solution?

Indeed, I really couldn't figure out how to solve this. I think something related to linear programming would do the job, but i looks like there are much simpler solutions than any using this kind of thing...

So, please, explain me your ideas.

Best regards,
Douglas