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

Praveen SP - 1st Oct,2009 17:57:58.

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

Praveen SP - 1st Oct,2009 17:58:09.

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

No.

Aniruddha (Codechef) - 1st Oct,2009 18:01:22.

No.

Are C++ submissions compiled

Tomaz Hocevar - 1st Oct,2009 20:30:15.

Are C++ submissions compiled with -O2?

@Tomaz I believe they are.  

Aniruddha (Codechef) - 2nd Oct,2009 11:41:12.

@Tomaz I believe they are.

 

any body know the logic there

K Marutikumar Naidu - 3rd Oct,2009 00:17:15.
any body know the logic there

total weight of the loaded

Gautam verma - 3rd Oct,2009 01:07:15.

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,

Anil Kishore - 3rd Oct,2009 02:25:13.

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

My program runs without any

Shyam Prasad Murarka - 3rd Oct,2009 17:30:44.
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!

Shyam Prasad Murarka - 3rd Oct,2009 18:15:09.
:D...
My mistake. Sorry!

hello guys, I'm kind of new

digviay singh - 4th Oct,2009 11:00:01.

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

rajul - 4th Oct,2009 14:49:38.
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

Shishir Mittal - 4th Oct,2009 15:51:08.

@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

rajul - 4th Oct,2009 16:57:47.
THANKS SHISHIR MITTAL

THANKS SHISHIR MITTAL

rajul - 4th Oct,2009 16:59:44.
THANKS SHISHIR MITTAL

Do we have to round up the

Ankit Shah - 4th Oct,2009 21:00:56.

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 - 4th Oct,2009 22:52:45.
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

Kailash H D - 5th Oct,2009 11:55:06.

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

@anjani you can take a look

Aniruddha (Codechef) - 5th Oct,2009 14:48:02.

@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

krishna - 7th Oct,2009 09:12:11.

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

Aniruddha (Codechef) - 7th Oct,2009 14:08:24.

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

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM: