DMOPC '16 Contest 3 P5 - Shoe Shopping II - Olympiads Online Judge

DMOPC '16 Contest 3 P5 - Shoe Shopping II

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.4s

Rust 2.5s

Memory limit: 64M

Authors:

WallE256, ionutpop118

Problem type

After returning from the nautical lessons, Captain Akeno asked her good friend Xyene to go and get her some more shoes while she is at school, from the same shop. When Xyene arrived at the store, he observed some 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.

Xyene is rather lazy, and doesn't really care about the best price, so he asked the cashier to group the pairs as she sees fit. The cashier can only group adjacent pairs in the order Xyene placed them on the conveyor. Additionally, the cashier is instructed with a special number, $k$ ~k~, which represents that she needs to get the $k$ ~k~-th smallest unique obtainable price from grouping the pairs. How much money is Xyene going to pay?

Input Specification

The first line of input will contain two space-separated integers, $N$ ~N~ ( $5 \le N \le 10\,000$ ~5 \le N \le 10\,000~) and $k$ ~k~ ( $1 \le k \le 10\,000$ ~1 \le k \le 10\,000~).
The second line of input will contain $N$ ~N~ space-separated integers representing the prices of the pairs of shoes. It is guaranteed that the total sum of the numbers does not exceed $2^{31}-1$ ~2^{31}-1~.

Output Specification

On the first line, you must print the $k$ ~k~-th smallest unique obtainable price with one decimal. In case you can't find an answer, print -1.

Sample Input

5 3
100 27 15 25 400

Sample Output

541.0

Comments

24

laith123 commented on Dec. 13, 2016, 10:04 p.m. ← edited →

I be Spendin' dat $2^{31}$ ~2^{31}~ dollas on mah shoes homie. Idk about u but I roll big