Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question from Croatian Olympiads, prepared by Ibrahim Mesecan.
Buy 3, Pay 2
Question:
The company that you work started a new promotional
season. People buy any three items, and they don't
pay for the cheapest item (of the three). Write a
program that reads product information for n items
and calculates the minimum amount (for the customer)
to pay. Pay attention that the items may be
grouped differently and different results may
come. For example if you are given the prices:
5 5 3 4 2 1 and if you process with
the groups: (5 5 3) (4 2 1),
the customer has to pay $16. However,
if you group (5 4 5) (3 2 1), the customer has
to pay $15. Find the minimum total amount to pay.
Input specification
You will be first given a number n, the number of
numbers where 0 ≤ n ≤ 10,000.
Then, in the following n lines, you will be
given n numbers where the numbers are floating point
numbers between 0 and 10,000. Please note that
n does not have to be a multiple of three.
Output specification:
Show the result with digits precision:
minimum total amount to pay.
Sample Input I
6
5 5 3 4 2 1
|
Sample Input II
4
3 7.2 4 5
|
Sample Output I
15.00
|
Sample Output II
15.20
|
Explanation
(for Sample input 2):
If you group, 7 5 and 4, $4 will be free.
Because there is no other triple,
he has to pay for: 7+5+3 = $15
Для отправки решений необходимо выполнить вход.
|