Road to Millionaire

AtCoder

IDm_solutions2020_d

Time2000ms

Memory256MB

Difficulty—

To become a millionaire, M-kun has decided to make money by trading in the next $N$ days. Currently, he has $1000$ yen and no stocks - only one kind of stock is issued in the country where he lives. He is famous across the country for his ability to foresee the future. He already knows that the price of one stock in the next $N$ days will be as follows: * $A_1$ yen on the $1$\-st day, $A_2$ yen on the $2$\-nd day, ..., $A_N$ yen on the $N$\-th day. In the $i$\-th day, M-kun can make the following trade **any number of times** (possibly zero), **within the amount of money and stocks that he has at the time**. * Buy stock: Pay $A_i$ yen and receive one stock. * Sell stock: Sell one stock for $A_i$ yen. What is the maximum possible amount of money that M-kun can have in the end by trading optimally? ## Constraints * $2 \leq N \leq 80$ * $100 \leq A_i \leq 200$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $A_1$ $A_2$ $\cdots$ $A_N$ [samples]

Samples

Input #1

7
100 130 130 130 115 115 150

Output #1

1685

In this sample input, M-kun has seven days of trading. One way to have $1685$ yen in the end is as follows:

*   Initially, he has $1000$ yen and no stocks.
*   Day $1$: Buy $10$ stocks for $1000$ yen. Now he has $0$ yen.
*   Day $2$: Sell $7$ stocks for $910$ yen. Now he has $910$ yen.
*   Day $3$: Sell $3$ stocks for $390$ yen. Now he has $1300$ yen.
*   Day $4$: Do nothing.
*   Day $5$: Buy $1$ stock for $115$ yen. Now he has $1185$ yen.
*   Day $6$: Buy $10$ stocks for $1150$ yen. Now he has $35$ yen.
*   Day $7$: Sell $11$ stocks for $1650$ yen. Now he has $1685$ yen.

There is no way to have $1686$ yen or more in the end, so the answer is $1685$.

Input #2

6
200 180 160 140 120 100

Output #2

1000

In this sample input, it is optimal to do nothing throughout the six days, after which we will have $1000$ yen.

Input #3

2
157 193

Output #3

1216

In this sample input, it is optimal to buy $6$ stocks in Day $1$ and sell them in Day $2$, after which we will have $1216$ yen.

API Response (JSON)

{
  "problem": {
    "name": "Road to Millionaire",
    "description": {
      "content": "To become a millionaire, M-kun has decided to make money by trading in the next $N$ days. Currently, he has $1000$ yen and no stocks - only one kind of stock is issued in the country where he lives. H",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "m_solutions2020_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "To become a millionaire, M-kun has decided to make money by trading in the next $N$ days. Currently, he has $1000$ yen and no stocks - only one kind of stock is issued in the country where he lives.\nH...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments