Задача №112814. Занимательная экономия
В известной сети гипермаркетов Heap-Hop ежегодно проводится следующая акция.
В декабре при покупке любого товара стоимостью не меньше 1 000 руб., за каждую целую тысячу рублей в стоимости одного товара выдаётся купон номиналом в 500 руб. Например, если мы покупаем в декабре один товар стоимостью 1 001 руб., а второй — 2 999 руб., то получим купон в 500 руб. за первый и всего два купона за второй. В январе полученные купоны можно использовать для оплаты 20% стоимости уже всей покупки в целом. То есть вне зависимости от стоимости отдельных товаров, если в январе общая сумма покупки в нашем примере будет не меньше 7 500 руб., то 1 500 мы оплатим купонами, а если меньше, то мы не сможем использовать все купоны полностью. Но даже за покупку стоимостью меньше 500 руб. мы сможем получить скидку в 20%, отдав купон номиналом 500 руб.
Семья Бережливых давно присмотрела ряд товаров в одном из гипермаркетов этой сети. Зная условия акции, они решили распределить покупки на два месяца так, чтобы в итоге заплатить за все товары вместе как можно меньше. Младший сын Бережливых Иван взялся написать программу, которая и выдаст соответствующие рекомендации, но родители не уверены, что его программа будет находить минимально возможную сумму денег, которой можно обойтись при покупке всех необходимых товаров с учётом акции. Поэтому подобную программу предлагается написать вам.
В первой строке входных данных находится число N — количество товаров, которые хочет купить семья Бережливых. Во второй строке записаны через пробел целые положительные числа ci — цены товаров. Каждого товара необходимо купить ровно одну единицу, но стоимости различных товаров могут совпадать.
Выведите одно вещественное число — минимальное количество рублей, которым можно обойтись при оплате всей покупки с использованием акции. Обратите внимание, ответ всегда выражается целым количеством копеек.
2
1000 1000
1800.00
3
1000 2000 500
3000.00
2
1001 1002
1802.60
В первом примере мы покупаем любой из предметов в первый месяц и получаем купон на 500 рублей. Тем не менее при покупке второго предмета можно будет оплатить не более 20% стоимости, что составит 200 рублей.
Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. 1 ≤ N ≤ 20, стоимость любого товара не превосходит 5 000. Оценивается из 40 баллов. Баллы начисляются только при прохождении всех тестов данной подзадачи. Решения, не прошедшие все тесты в этой подзадаче, дальше не тестируются.
Подзадача 2. 1 ≤ N ≤ 100, стоимость любого товара не превосходит 5 000. Оценивается из 30 баллов. Каждый тест оценивается отдельно.
Подзадача 3. 1 ≤ N ≤ 1 000, стоимость любого товара не превосходит 50 000. Оценивается из 30 баллов. Каждый тест оценивается отдельно.