10385 - Duathlon

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Jucovschi Constantin
New poster
Posts: 9
Joined: Sat Oct 26, 2002 6:30 pm

10385 - Duathlon

Post by Jucovschi Constantin » Sun Oct 27, 2002 8:52 pm

How to solve 10385

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Sun Oct 27, 2002 9:03 pm

how about brute force?

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

10385: POOR description

Post by Miguel Angel » Sun Jan 19, 2003 5:18 am

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 :)
:D Miguel & Marina :D

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

I can answer my question..

Post by Miguel Angel » Sun Jan 19, 2003 6:07 am

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

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Tue Jan 28, 2003 12:48 am

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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Tue Jan 28, 2003 12:57 am

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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 10385 - Duathlon

Post by serur » Mon Sep 07, 2009 7:25 pm

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
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

Re: 10385 - Duathlon

Post by coze » Mon Sep 07, 2009 9:56 pm

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 10385 - Duathlon

Post by serur » Tue Sep 08, 2009 8:47 pm

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

Code: Select all

CUT AFTER AC
Last edited by serur on Sat Sep 12, 2009 8:34 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

coze
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

Re: 10385 - Duathlon

Post by coze » Wed Sep 09, 2009 5:26 pm

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 10385 - Duathlon

Post by serur » Sat Sep 12, 2009 8:36 pm

Thanks coze, your suggestion was the very thing. Got it AC at last :)
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

DeadLock
New poster
Posts: 3
Joined: Thu Sep 24, 2009 2:05 am

Re: 10385 - Duathlon

Post by DeadLock » Thu Sep 24, 2009 2:10 am

what is the output for

Code: Select all

10
2
5 5
10 10

DeadLock
New poster
Posts: 3
Joined: Thu Sep 24, 2009 2:05 am

Re: 10385 - Duathlon

Post by DeadLock » Thu Sep 24, 2009 5:45 pm

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

SePulTribe
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Re: 10385 - Duathlon

Post by SePulTribe » Sun May 30, 2010 5:43 pm

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

docardoso
New poster
Posts: 1
Joined: Fri Jun 25, 2010 7:43 am

Re: 10385 - Duathlon

Post by docardoso » Fri Jun 25, 2010 7:49 am

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

Post Reply

Return to “Volume 103 (10300-10399)”