No.286 Modulo Discount Store
yuki2006Problem Statement
There is a store selling $N$ items, each with a list price of $M_i$ yen.
When you buy an item at this store, each purchase is discounted by "the sum of the "list" prices of the items bought so far, modulo 1000 (the remainder when divided by 1000, $Mod\ 1000$)" yen.
However, if the price of the item being bought would be less than 0 yen after the discount, you buy it for 0 yen.
You want to buy all $N$ items, without buying the same item twice.
Calculate the minimum total amount paid to buy all $N$ items.
You may buy the items in any order, but you cannot buy them simultaneously and can only buy them one at a time.
Input
$N$ $M_1$ $M_2$ $\dots$ $M_N$
All input values are integers.
$1 \le N \le 15 $
$1 \le M_i \le 10000$ This represents the list price of item $i$.
Output
Calculate the minimum total amount paid to buy all $N$ items.
Sample
Sample 1
Input
3 100 200 300
Output
200
Buy the items in the order item $1$, item $2$, item $3$.
Buy item $1$, priced at 100 yen. At this point nothing has been bought yet, so there is no discount, and you buy it for 100 yen.
Buy item $2$, priced at 200 yen. At this point item $1$ has been bought, so 100 yen is taken off, and you can buy it for (200-100=)100 yen.
Buy item $3$, priced at 300 yen. At this point item $1$,item $2$ have been bought, so 300 yen is taken off, and you can buy it for 0 yen.
Therefore, you can buy everything for 200 yen.
Sample 2
Input
3 1000 900 800
Output
1000
Buy the items in the order item $2$, item $1$, item $3$.
Buy item $2$, priced at 900 yen. At this point nothing has been bought yet, so there is no discount, and you buy it for 900 yen.
Buy item $1$, priced at 1000 yen. At this point item $2$ has been bought, so 900 yen is taken off, and you can buy it for 100 yen.
Buy item $3$, priced at 800 yen. At this point item $1$,item $2$ have been bought, so 900 yen is taken off
(the discount is 900 yen, the remainder when the total list price so far, 1900 yen, is divided by 1000), and you can buy it for 0 yen.
Therefore, you can buy everything for 1000 yen. No purchase order allows you to buy everything for less than 1000 yen.
Sample 3
Input
5 10000 1000 100 10 1
Output
10877
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。