DMOPC '16 Contest 1 P3 - Shoe Shopping

View as PDF
Submit solution
Points: 7
Time limit: 0.6s
Memory limit: 64M
Author:
WallE256
Problem type

Captain Akeno and the crew stopped at a floating mall to replenish the ship's supply of toilet paper. As any normal girl does, the captain stopped at a shoe store, where they had two awesome deals. The deals are as follows:

  • If you group two pairs of shoes, you get the cheaper one at a 50% DISCOUNT.
  • If you group three pairs of shoes, you get the cheapest one for FREE.

Captain Akeno had already placed the pairs of shoes on the conveyor when she was told that she can only group adjacent pairs. The group of girls didn't have much money at hand, so they kindly ask you to tell them the minimum obtainable price.

Input Specification

The first line of input will contain the integer N (1 \le N \le 10\,000), the number of pairs of shoes.
The second line of input will contain N space-separated integers representing the prices of the pairs of shoes.

Output Specification

On the first line, you must print the smallest obtainable price with one decimal.

Sample Input

5
100 27 15 25 400

Sample Output

538.5

Comments


  • 0
    kresteodymium  commented on Dec. 21, 2021, 10:15 p.m.

    Are we limited to one deal for the entire transaction or can we choose both deals in various quantitues for the transaction?


  • -2
    Pleedoh  commented on May 15, 2017, 8:30 p.m. ← edit 2

    We assume they can get one of each deal right? And they don't affect each other?


  • -2
    Pleedoh  commented on May 13, 2017, 5:28 p.m.

    Should the price round to one decimal, or just express one decimal? Ex: Does 45.78 become 45.7 or 45.8?


    • -2
      wleung_bvg  commented on May 14, 2017, 5:21 a.m.

      It should be rounded. 45.78 becomes 45.8


      • -2
        Pleedoh  commented on May 15, 2017, 5:16 p.m. ← edited

        Alright, but what if there is no decimal? Ex if the answer is 178, will it mark it as wrong if I output 178.0?


        • -2
          billsboard  commented on Feb. 21, 2021, 10:35 p.m. ← edit 2

          It will mark 178 wrong I think. You should always have a decimal.


  • 5
    kevinwen  commented on Oct. 11, 2016, 10:38 p.m.

    Can you only do any grouping operation once?


  • 4
    xavier158  commented on Oct. 11, 2016, 7:51 p.m.

    which is the bigger price that a shoe can have?


    • 4
      WallE256  commented on Oct. 11, 2016, 7:59 p.m. ← edited

      The maximum price of a pair of shoes is 10000.