Kayaks

Problem code: H2

All submissions for this problem are available.

Suppose we have an even number of people going on an excursion, and we would like to fit them into two-seated kayaks. All kayaks are identical, weighing 20kg each. Each person is described by two parameters, their strength and weight. The speed of a kayak can be calculated as the sum of strengths of both persons sitting in it, divided by the total weight of the loaded kayak (i.e., the weight of the kayak plus the weight of both persons). We would like to choose the allocation of people to kayaks so as to maximize the speed at which the whole whole group can travel, assuming that the group travels at the speed of the slowest kayak in it.

Input

First, 2 ≤ n ≤ 105, the number of people (n will always be even). Then, n pairs of integers follow, each pair describing one person: first, 50≤w≤100, the weight of the person (in kilograms), then 50≤p≤100, the strength of the person.

Output

Output one number: the maximum speed of the group which can be achieved by optimally choosing places for each person. The answer should be accurate up to 6 digits after the decimal point.

Example

Input:
4
50 50
50 60
70 100
100 60

Output:
0.842105

Date: 2009-09-15
Time limit: 2

s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK CAML CLPS PRLG WSPC BF ICK TEXT


Comments

If the output is 0.2 is it

sppraveen @ 1 Oct 2009 05:57 PM

If the output is 0.2 is it required to print 0.100000 all six decimal places padded with zeros?

If the output is 0.2 is it

sppraveen @ 1 Oct 2009 05:58 PM

If the output is 0.2 is it required to print 0.200000 all six decimal places padded with zeros?

No.

admin @ 1 Oct 2009 06:01 PM

No.

Are C++ submissions compiled

thocevar @ 1 Oct 2009 08:30 PM

Are C++ submissions compiled with -O2?

@Tomaz I believe they are.  

admin @ 2 Oct 2009 11:41 AM

@Tomaz I believe they are.

 

any body know the logic there

marutinaidu @ 3 Oct 2009 12:17 AM
any body know the logic there

total weight of the loaded

gautamverma @ 3 Oct 2009 01:07 AM

total weight of the loaded kayak i.e., the weight of the kayak plus the weight of both persons. What is the weight of kayak?

... All kayaks are identical,

flying_ant @ 3 Oct 2009 02:25 AM

... All kayaks are identical, weighing 20kg each. ...

My program runs without any

shyammurarka @ 3 Oct 2009 05:30 PM
My program runs without any Runtime Error on my laptop. The issue is as follows: After my calculation, I store my answer in a variable 'finalSpeed' of type double. On the Server -------------------- When the following line is executed, it gives Runtime Error. printf("%.6fn",finalSpeed); When I comment the above line, it obviously gives Wrong Answer. I cannot imagine why such a thing would happen?! Is there a bug in the Online Judge?

:D... My mistake. Sorry!

shyammurarka @ 3 Oct 2009 06:15 PM
:D...
My mistake. Sorry!

hello guys, I'm kind of new

digvijay1248 @ 4 Oct 2009 11:00 AM

hello guys, I'm kind of new here ,

can you tell me how to view the compilation error results?

error occured at codechef.

thanks.

can any body explain me this

rajul884 @ 4 Oct 2009 02:49 PM
can any body explain me this question bcoz in example output is 0.842105 but this get by choosing last two person and if i choose second and third person i will get more speed then 0.842105

@Rajul : The problem

porsh @ 4 Oct 2009 03:51 PM

@Rajul : The problem statement says "....maximize the speed at which the whole whole group can travel, assuming that the group travels at the speed of the slowest kayak in it...."

For the given problem, there are 3 possible pairings viz.

(1,2) ; (3,4).... speed1 = min (160/120, 160/190)

(1,3) ; (2,4).... speed2 = min (150/140, 120/170)

(1,4) ; (2,3).... speed3 = min (110/170, 160/140)

Ans = max(speed1, speed2, speed3) = 160/190 = 0.842105

THANKS SHISHIR MITTAL

rajul884 @ 4 Oct 2009 04:57 PM
THANKS SHISHIR MITTAL

THANKS SHISHIR MITTAL

rajul884 @ 4 Oct 2009 04:59 PM
THANKS SHISHIR MITTAL

Do we have to round up the

ankitshah_26 @ 4 Oct 2009 09:00 PM

Do we have to round up the 6th digit after decimal ??for eg if ans is 0.1234567 than we have to print 0.123456 or 0.123457

I don't have a gcc 4.0.0-8

anjani @ 4 Oct 2009 10:52 PM
I don't have a gcc 4.0.0-8 compiler. My program is compiled in tcpp and is made in c. My program is not compiling in codeChef. What do i do.............

@anjani: Use Dev CPP on

oldmonk @ 5 Oct 2009 11:55 AM

@anjani: Use Dev CPP on windows. That comes with gcc compiler.

@anjani you can take a look

admin @ 5 Oct 2009 02:48 PM

@anjani you can take a look at www.codechef.com/wiki for more information on where you can get the compilers from.

i'm getting run time

krishnaksr @ 7 Oct 2009 09:12 AM

i'm getting run time error....

but it doesn,t show this in dev-cpp

what should i do?

It probably doesn't show up

admin @ 7 Oct 2009 02:08 PM

It probably doesn't show up in dev-cpp because you haven't tested it on large inputs.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions