IITKWPCD - Partition the sticks
You are given a set of N sticks and are required to partition them into groups of exactly 3 sticks each. While doing so, you can leave out any number of sticks out of these groups (in particular, no groups may be formed). One condition needs to be met: sticks in each group need to form a triangle. A triangle can be constructed if sum of any two sticks lengths is greater than the third length.
Your are required to partition the sticks so that the sum of triangle areas from all the groups is maximized.
Input
Very first line of the input contains integer T: number of test cases (1 <= T <= 5).
For each test case, first line contains integer N: number of sticks. (1 <= N <= 15).
Second line contains N space separated integers: the lengths li of the sticks. (1 <= li <= 10^3, 1 <= i <= N).
Output
For each test case, output the maximal area in a separate line. Round value to exactly 6 decimal places. Always print exactly 6 decimal places.
Example
Input:
3
3
7 8 5
4
7 8 6 3
3
7 2 1
Output:
17.320508
20.333163
0.000000
hide comments
smso:
2019-03-13 06:26:50
dp and use double instead of float |
|
visha_l:
2017-01-12 15:07:39
13
|
|
Siu Ching Pong (Asuka Kenji):
2015-01-31 07:40:14
The questions says:
|
|
tyson:
2014-06-27 08:24:01
@praveen123 i m not able to figure out why my code gives wrong answer please provide me with a test case |
|
u torrent:
2013-09-22 18:44:04
WA :( Last edit: 2013-09-22 18:47:29 |
|
praveen123:
2013-09-03 03:02:36
@:D, thank you for updating the problem statement, Now it looks far better than previous one :) |
|
:D:
2013-09-02 16:41:03
Description updated. |
|
utpal kumar jha:
2013-08-23 22:56:05
same here getting WA again and again and i am pretty sure my logic's correct and answer for the test case given below is matching with the correct answer.. please provide some more test cases Last edit: 2013-08-24 12:17:24 |
|
[Lakshman]:
2013-08-20 14:29:39
I am getting 397587.875000
|
Added by: | praveen123 |
Date: | 2013-08-05 |
Time limit: | 1s-2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: |