LCC '18 Contest 5 S2 - Penny Pinching

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Since Canada has abolished the penny, purchase amounts have been rounded to the nearest 5 cents when paying cash. Fred, a very frugal shopper, has made use of this by breaking up his purchases so that the total amount he has to pay is as small as possible.

For example, if Fred wants to buy two items which cost $1.01 and $1.12, then he would rather buy those items separately and pay $1.00 + $1.10 = $2.10 rather than buying them together and paying $2.15.

Inspired by Fred’s idea, you have decided to turn his process into a program: given a set of prices, what is the minimum amount that you would have to pay if you split up the items correctly?

Input Specification

The first line of input contains an integer N (1 \le N \le 100,000), the number of items. The next line contains N space-separated item prices P ($0.00 < P < $10.00).

Output Specification

Output the minimum amount required to purchase all of the items.

Sample Input 1

1.01 1.12

Sample Output 1


Sample Input 2

1.01 2.02 3.03 4.04

Sample Output 2



There are no comments at the moment.