Problem:


Score: 400 points

Problem Statement

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

Output

Print the maximum possible amount of money that M-kun can have in the end, as an integer.

Sample Input 1

7
100 130 130 130 115 115 150

Sample 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.

Sample Input 2

6
200 180 160 140 120 100

Sample Output 2

1000

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

Sample Input 3

2
157 193

Sample 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.



Sample input:
7
100 130 130 130 115 115 150


Sample output:
1685

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = tuple([int(t)for t in input().split()])

    ans = 1000
    stock = 0
    if a[0]<=a[1]:
        buy = ans//a[0]
        ans -= buy*a[0]
        stock += buy
    for i in range(1,n-1):
        if a[i-1]<=a[i]:
            ans+=stock*a[i]
            stock = 0
        if a[i]<=a[i+1]:
            buy = ans//a[i]
            ans -= buy*a[i]
            stock += buy

    ans+=stock*a[-1]
    stock = 0
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
yen = 1000
kabu = 0
for i in range(n-1):
    yen += kabu * a[i]
    kabu = 0
    if a[i] <= a[i+1]:
        kabu = yen // a[i]
        yen = yen % a[i]
yen += kabu * a[n-1]
print(yen)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.append(0)
money = 1000
stock = 0
for i in range(n):
    if a[i] < a[i+1] and stock == 0:
        stock,money = money//a[i],money%a[i]
    elif a[i] > a[i+1]:
        stock,money = 0,money+stock*a[i]
print(money)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))



money = 1000
stock = 0

for i in range(N):
    if stock > 0 and i>=1:
        if A[i] > A[i-1]:
            money += stock * A[i]
            stock -= stock
    if money > A[i] and i<=N-2:
        if A[i]<A[i+1]:
            stock += money//A[i]
            money -= (money//A[i]) * A[i]

        
print(money)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mo = 1000
now = True  #下がり待つとき #買うとき
have = 0    #持ってるカブの数
price = 0 #持ってるカブの値段
now_max = 0
now_min = 1000000000000
for i in range(n-1):
    if now:
        if a[i]<a[i+1]:
            have = int(mo/a[i])
            price = a[i]
            mo = mo-have*price
            now = not now
    else:
        if a[i]>a[i+1]:
            mo += have*a[i]
            heve = 0
            now = not now
if not now:
    mo += have*a[n-1]

print(mo)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 25 21:15:35 2020

@author: NEC-PCuser
"""

N = int(input())
A = list(map(int, input().split()))

money = 1000
kabu = 0

for i in range(N):
    if (i <= N - 2 and A[i] > A[i + 1]):
        money += kabu * A[i]
        kabu = 0
    elif (i <= N - 2 and kabu == 0):
        kabu = money // A[i]
        money = money % A[i]

if (kabu != 0):
    money += kabu * A[N - 1]

print(money)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

now = 1000
stack = 0
price = a[0]
for i in range(1, n):
    # 下がる時
    if price > a[i]:
        # 株を持っているなら下がる前の値段で売っておく
        if stack != 0:
            now += stack * price
            stack = 0
    # 値上がりする場合
    else:
        # 株を持っていないなら上がる前に買っておく
        if stack == 0:
            stack = now // price
            now -= stack * price
    price = a[i]

if stack != 0:
    now += stack * price
print(now)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=1000
bef=a[0]
up=[]
k=0
for i in a[1:]:
  if i>bef:
    up.append(1)
  else:
    up.append(0)
  bef=i
bef=up[0]
if bef:
  k=m//a[0]
  m=m%a[0]  

for i in range(1,n-1):
  if up[i]<bef:    
    m+=k*a[i]
    k=0
  elif up[i]>bef:
    k=m//a[i]
    m=m%a[i]
  bef=up[i]
m+=k*a[-1]
print(m)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(_x) for _x in input().split()]

    kabu = 0
    kin = 1000
    for i in range(N):
        if kabu > 0:
            kin = kin + A[i] * kabu
            kabu = 0
        if i < N-1:
            if A[i] < A[i+1]:
                kabu = int(kin/A[i])
                kin = kin - A[i] * kabu
    print(kin)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

'''
Author: andyli
Time: 2020-07-25 19:57:02
'''

import os
from io import BytesIO, IOBase
import sys


def main():
    n = int(input())
    A = list(map(int, input().split()))

    a, b, p = 1000, 0, 0
    while p+1 < n and A[p] >= A[p+1]:
        p += 1
    while p < n-1:
        t = a//A[p]
        b += t
        a -= t*A[p]
        while p+1 < n and A[p] <= A[p+1]:
            p += 1
        a += b*A[p]
        b = 0
        if p == n:
            break
        while p+1 < n and A[p] >= A[p+1]:
            p += 1
    print(a)
    return


# region fastio
BUFSIZE = 1048576


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip('\r\n')

# endregion


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a_list=list(map(int,input().split()))
current=1000
kabu=0
for i in range(n-1) :
  if a_list[i]<a_list[i+1] :
    kabu+=current//a_list[i]
    current=current%a_list[i]
    current += a_list[i+1] * kabu
    kabu = 0




print(current)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

m = 1000
k = 0

for i in range(n):
    #最終日は全額売る
    if i == n - 1:
        m += k * a[i]
        break

    #翌日上がるなら買う
    if a[i] < a[i + 1]:
        k += m // a[i]
        m = m % a[i]
        continue
    
    #翌日下がるなら売る
    if a[i] > a[i + 1]:
        m += k * a[i]
        k = 0
        continue

print(m)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
acd = A[0] <= A[1]
lst = [A[0]]
i = 1
while i < N:
    if acd:
        if A[i-1] > A[i]:
            lst.append(A[i-1])
            acd = 0
    else:
        if A[i-1] < A[i]:
            lst.append(A[i-1])
            acd = 1
    i += 1
if A[N-2] <= A[N-1]:
    lst.append(A[N-1])
if len(lst) == 1:
    print(1000)
    exit()
if lst[0] > lst[1]:
    lst = lst[1:]
if len(lst) < 2:
    X = 1000
else:
    X = 1000
    for i in range(0, len(lst), 2):
        c = X//lst[i]
        X -= c*lst[i]
        X += c*lst[i+1]
print(X)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
money = 1000
p = 0
def buy(m,a):
    global money
    global p
    num = m // a
    money -= num*a
    p += num
def sell(s,a):
    global money
    global p
    money += s*a
    p = 0
if a[0] <= a[1]:
    dx = 1
else:
    dx = -1
if dx == 1:
    buy(1000,a[0])
for i in range(n-2):
    if a[i+1] < a[i+2]:
        dy = 1
    elif a[i+1] == a[i+2]:
        dy = 0
    else:
        dy = -1
    if dx == 1 and dy == -1:
        sell(p,a[i+1])
    elif dx == -1 and dy == 1:
        buy(money,a[i+1])
    if dy != 0:
        dx = dy
sell(p,a[n-1])
print(money)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
money = 1000
kabu = 0

if A[0] < A[1]:
    kabu += money // A[0]
    money = money % A[0]

for i in range(1, N-1):
  if A[i-1] >= A[i] and A[i] < A[i+1]:
    kabu += money // A[i]
    money = money % A[i]
  elif A[i-1] <= A[i] and A[i] > A[i+1]:
    money += kabu * A[i]
    kabu = 0

money += kabu * A[N-1]
kabu = 0
print(money)

Submission status: Accepted

Solution code:
INF = 10 ** 10

def solve(ns):
    n = len(ns)
    dp = [ set([(1000, 0)]), set([]) ]
    p = 0
    for price in ns:
        q = p ^ 1
        dp[q] = set()
        for (money, stock) in dp[p]:
            m1 = money + stock * price
            dp[q].add((m1, 0))
            m2 = money % price
            s2 = stock + money / price
            dp[q].add((m2, s2))
            dp[q].add((money, stock))
        p = q
    maxi = -INF
    for (money, stock) in dp[p]:
        maxi = max(maxi, money)
    return maxi

def solve2(ns):
    n = len(ns)
    dp = [1000] + [-INF for i in xrange(n)]
    for i in xrange(1, n + 1):
        for j in xrange(i + 1, n + 1):
            if ns[j - 1] <= ns[i - 1]:
                continue
            money = dp[i - 1]

            # buy in day[i]
            stock = money / ns[i - 1]
            money = money % ns[i - 1]

            # sell in day[j]
            money = money + stock * ns[j - 1]
            stock = 0

            dp[j] = max(dp[j], money)
        dp[i] = max(dp[i], dp[i - 1])
    return max(dp)

assert solve2([200, 188, 181, 115, 160]) == 1360
assert solve2([200, 180, 160, 140, 120, 100]) == 1000
assert solve2([100, 130, 130, 130, 115, 115, 150]) == 1685
# assert solve([200, 180, 160, 140, 120, 100]) == 1000
assert solve2([157, 193]) == 1216

n = int(raw_input())
ns = map(int, raw_input().split())

# print solve(ns[:])
print solve2(ns[:])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
UD = []
last_idx = 0
for n in range(N-1):
    if A[n] < A[n+1]:
        UD.append('Up')
        last_idx = n
    else:
        UD.append('Down')
M = 1000
S = 0
for n in range(N-1):
    if UD[n] == 'Up':
        num = M//A[n]
        S += num
        M -= num*A[n]
    else:
        num = S*A[n]
        S = 0
        M += num
num = S*A[N-1]
S = 0
M += num
print(M)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]
N = int(input())
A = [int(x) for x in input().split()]

premin = A[0]
cur = 1000
for i in range(1, N):
    if A[i] > premin:
        cur = cur + (cur//premin)*(A[i]-premin)
        premin = A[i]
    premin = min(premin, A[i])

print(cur)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

money = 1000
kabu = 0

for i in range(N):
    if kabu == 0:
        flag = True
        for j in range(i+1, N):
            if A[i] > A[j]:
                flag = False
                break
            elif A[i] < A[j]:
                flag = True
                break
        else:
            flag = False
        if flag:
            buy = money // A[i]
            money -= buy * A[i]
            kabu += buy
    else:
        flag = True
        for j in range(i+1, N):
            if A[i] < A[j]:
                flag = False
                break
            elif A[i] > A[j]:
                flag = True
                break
        if flag:
            money += kabu * A[i]
            kabu = 0
    # print(money, kabu)

print(money)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))


money_high = 1000
kabu_high = money_high // A[0]
zankin = 0
for i in range(n):
    money_high = max(kabu_high * A[i] + zankin, money_high)
    kabu_high = max(money_high // A[i], kabu_high)
    zankin = money_high % A[i]

print(max(kabu_high * A[n-1] + zankin, money_high))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = 1000
for i in range(1, n):
    if a[i] > a[i - 1]:
        c = c // a[i - 1] * a[i] + c % a[i - 1]
print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

# 株は変えるだけ買うほうがよさそう
dp = defaultdict(int)
dp[0] = 1000
for a in A:
    key, val = zip(*dp.items())
    for k, v in zip(key, val):
        # 株売る
        dp[0] = max(dp[0], v + k * a)
        # 株買う
        buy = v // a
        dp[k + buy] = max(dp[k + buy], v - buy * a)

print(dp[0])

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    funds = 1000
    stock = 0

    for i in range(n):
        if i > 0 and A[i] > A[i-1]:
            # sell
            funds += A[i] * stock
            stock = 0
        if i < n-1 and A[i] < A[i+1]:
            # buy
            stock += funds // A[i]
            funds -= A[i] * stock

    print(funds)

resolve()

Submission status: Accepted

Solution code:
n = int(input())
ls = list(map(int,input().split()))
ans = 1000

A = [ls[0]]

for i in range(1,n-1):
  if ls[i-1]<ls[i]<ls[i+1]:
    continue
  if ls[i-1]>ls[i]>ls[i+1]:
    continue
  if ls[i]==ls[i-1]:
    continue
    
  A.append(ls[i])
  
if A[-1] != ls[-1]:
  A.append(ls[-1])

for i in range(1,len(A)):
  if A[i-1]< A[i]:
    ans = ans%A[i-1] + ans//A[i-1]*A[i]
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a = list(map(int,input().split()))
dp = [1000 for i in range(n)]

for i in range(n-1):
    for j in range(i,n):
        if a[i] < a[j]:
            mouke = dp[i] + (dp[i]//a[i])*(a[j]-a[i])
            dp[j] = max(dp[j],mouke)
        if j != 0:
            dp[j] = max(dp[j],dp[j-1])
print(dp[-1])

Submission status: Accepted

Solution code:
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n = int(readline().rstrip())
    A = list(map(int, readline().rstrip().split()))
    sumA = 0
    money = 1000
    for i in range(n - 1):
        if A[i + 1] - A[i] > 0:
            money += (A[i + 1] - A[i]) * math.floor(money / A[i])
    print(money)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.append(0)
ans = 1000
mx = -1
mn = -1
i = n-1
for j in range(n-1):
    if a[j]<a[j+1]:
        mn = a[j]
        i = j
        break
dec = False
if(i==n-1):
    dec = True
while i<n:
    if not dec and a[i]>a[i+1]:
        mx = a[i]
        dec = True
        ans += (mx-mn)*(ans//mn)
    if dec and a[i]<a[i+1]:
        mn = a[i]
        dec = False
    i+=1
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

okane = 1000
kabu = 0
syozi=False

for i in range(n):
    if syozi:
        if i == n-1:
            okane = okane + a[i]*kabu
            break
        if a[i+1] >= a[i]:
            continue
        else:
            okane = okane + a[i]*kabu
            kabu = 0
            syozi = False
    else:
        if i == n-1:
            break
        if a[i+1] <= a[i]:
            continue
        else:
            kabu = okane//a[i]
            okane = okane - kabu*a[i]
            syozi = True

print(okane)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

money = 1000
stocks = 0
up_flag = False

for i in range(n-1):
    if a[i] < a[i+1] and not up_flag:
        stocks += money//a[i]
        money -= stocks*a[i]
        up_flag = True
    elif a[i] > a[i+1] and up_flag:
        money += stocks*a[i]
        stocks = 0
        up_flag = False

if stocks>0:
    money += stocks*a[-1]

print(money)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))

sum=1000
have=0

for i in range(n-1):
    if have==0:
        if a[i]<a[i+1]:
            mai=sum//a[i]
            buy=mai*a[i]
            sum=sum-buy
            have=1
        if a[i]>a[i+1]:
            continue
        if a[i]==a[i+1]:
            continue
    
    if have==1:
        if a[i]<a[i+1]:
            continue
        if a[i]>a[i+1]:
            sum=sum+a[i]*mai
            have=0
            continue
        if a[i]==a[i+1]:
            continue


if have==1:
    sum=sum+mai*a[n-1]

print(sum)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

stock_dp = [[0, 0] for _ in range(n+1)]
value_dp = [0] * (n + 1)

value_dp[0] = 1000
for i in range(1, n + 1):
    x = value_dp[i - 1]
    y = stock_dp[i - 1][0] + stock_dp[i - 1][1] * a[i - 1]
    if x > y:
        value_dp[i] = x
    else:
        value_dp[i] = y
    x = value_dp[i - 1] // a[i - 1] 
    y = stock_dp[i - 1][0] // a[i - 1] + stock_dp[i - 1][1]
    rx = value_dp[i - 1] % a[i - 1]
    ry = stock_dp[i - 1][0] % a[i - 1]
    if x > y:
        stock_dp[i][0] = rx
        stock_dp[i][1] = x
    elif x < y:
        stock_dp[i][0] = ry
        stock_dp[i][1] = y
    else:
        stock_dp[i][0] = max(rx, ry)
        stock_dp[i][1] = x
print(value_dp[n])

Submission status: Accepted

Solution code:
n = int(input())
values = list(map(int, input().split()))

prev_direction = 0
money = 1000
stock = 0
for i, current in enumerate(values):
    if i == 0:
        continue

    yesterday = values[i - 1]
    # 上昇局面
    if current - yesterday > 0:
        if prev_direction != 1:
            # buy
            stockNum = money // yesterday
            buy = stockNum * yesterday
            money -= buy
            stock = stockNum
        prev_direction = 1

    elif current - yesterday < 0:
        # 下降局面
        if prev_direction != -1:
            sell = yesterday * stock
            stock = 0
            money += sell
        prev_direction = -1

    else:
        continue

lastSell = stock * values[len(values) - 1]
money += lastSell

print(money)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
money = 1000

L = [0 for _ in range(N)] #-1極小。1極大
for i in range(N):
  if i == 0:
    if A[i+1] >= A[i]:
      L[i] = -1
    else:
      L[i] = 1
  elif i == N-1:
    if A[i] >= A[i-1]:
      L[i] = 1
    else:
      L[i] = -1
  else:
    if A[i] >= A[i-1] and A[i] >= A[i+1]:
      L[i] = 1
    elif A[i] <= A[i-1] and A[i] <= A[i+1]:
      L[i] = -1
#print(L)
kabu = 0
for i in range(N):
  #print(money,kabu,L[i])
  if L[i] == 1:
    #print(money,kabu,L[i],"ok")
    money += kabu*A[i]
    kabu = 0
  elif L[i] == -1:
    #print(money,kabu)
    uri = money//A[i]
    money -= uri*A[i]
    kabu += uri
  #print(money,kabu)
ans = money+kabu*A[-1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

joutai = "nasi"
m = 1000
k = 0

for i in range(n-1):
    if joutai == "nasi":
        if a[i] < a[i+1]:
            k = m // a[i]
            m -= k * a[i]
            joutai = "ari"
    else:
        if a[i] > a[i+1]:
            m += k * a[i]
            k = 0
            joutai = "nasi"

m += k * a[n-1]

print(m)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1000
    i = 0
    while i < N:
        now = A[i]
        max = now
        next = i
        for j in range(i+1, N):
            if A[j-1] > A[j]:
                break
            if max < A[j]:
                max = A[j]
                next = j
        if now < max:
            cnt = ans // now
            ans += max * cnt - now * cnt
        i = next+1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
# greedy
# 翌日に上がるなら： 全力で買い
# 翌日に下がるなら： 全力で売り
# 値が動かないなら： ステイ
# 最終日なら： 全部売る

N = int(input())
prices = list(map(int, input().split()))

# 初期化
jpy = 1000
stocks = 0

for i in range(N):
    # 最終日なら全部売る
    if i == N - 1:
        jpy += prices[i] * stocks
        stocks = 0
        break
    
    # 翌日に上がるなら全力で買い
    if prices[i+1] > prices[i]:
        stocks += jpy // prices[i]
        jpy = jpy % prices[i]
    # 翌日に下がるなら全力で売り
    elif prices[i+1] < prices[i]:
        jpy += prices[i] * stocks
        stocks = 0
    # 値が動かないならステイ
    else:
        pass
print(jpy)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    *A, = map(int, input().split())

    money = 1000

    low = A[0]
    high = -1
    for x in A:
        if high < x:
            high = x
            continue

        if high > x:
            money += (high - low) * (money // low)
            low = high = x

    money += max(0, high - low) * (money // low)

    print(money)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[]

for i in input().split():
    a.append(int(i))
p=1000
for i in range(1,n):
    if(a[i]>a[i-1]):
        p=((p//a[i-1])*a[i])+(p%a[i-1])
print(p)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def list_split(l):
    res = []
    idx = 0
    for i in range(len(l) - 1):
        if l[i] > l[i + 1]:
            res.append(l[idx:i + 1])
            idx = i + 1

    res.append(l[idx:len(l)])

    return res


N, *A = map(int, read().split())
money = 1_000
n_stocks = 0
cost = 0

ll = list_split(A)

for l in ll:
    if len(l) == 1:
        continue
    acc = money // min(l)
    money -= acc * min(l)
    money += acc * max(l)

print(money)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
have = [1000, 0]
up = 0
for i in range(n - 1):
    if up:
        if a[i] > a[i + 1]:
            have[0] += have[1] * a[i]
            have[1] = 0
            up = 0
    else:
        if a[i] < a[i + 1]:
            have[1] = have[0] // a[i]
            have[0] = have[0] % a[i]
            up = 1
print(have[0] + have[1] * a[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()
	A=LI()
	A.append(0)

	L=[]
	R=[]

	f=0
	now=200
	i=0
	while i<n+1:
		if f==0:
			if A[i]<=now:
				now=A[i]
				i+=1
			else:
				L.append(now)
				f=1
		else:
			if A[i]>=now:
				now=A[i]
				i+=1
			else:
				R.append(now)
				f=0

	#print(L,R)

	ans=1000

	for i,j in zip(L,R):
		q,r=divmod(ans,i)
		ans=q*j+r
	print(ans)





















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

ans = 1000

KAI = -1
URI = 1
phase = KAI

kabu_min = a[0]
kabu_max = -1

for i in range(1, n):
  if phase == KAI and a[i] <= kabu_min:
    kabu_min = a[i]
  elif phase == KAI:
    kabu_max = a[i]
    phase = URI
  elif phase == URI and a[i] >= kabu_max:
    kabu_max = a[i]
  elif phase == URI:
    ans = (ans % kabu_min) + (ans // kabu_min) * kabu_max
    kabu_min = a[i]
    kabu_max = -1
    phase = KAI

if phase == URI and kabu_max > kabu_min:
  ans = (ans % kabu_min) + (ans // kabu_min) * kabu_max

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N = int(input())
A = list(map(int, input().split()))

P = 1000
k = 0
for i in range(1, N):
    if A[i-1] < A[i]:
        k = P // A[i-1]
        P -= k*A[i-1]
        P += k*A[i]

print(P)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))

    ans = 1000
    ll = rr = A[0]
    status = "down"
    for a in A[1:]:
        if status == "down":
            if ll < a:
                status = "up"
                rr = a
            else:
                ll = a
        else:
            if rr <= a:
                rr = a
            else:
                status = "down"
                q, r = divmod(ans, ll)
                ans = rr * q + r
                ll = a

    if status == "up":
        q, r = divmod(ans, ll)
        ans = rr * q + r

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
money = 1000
beet = 0
a = [int(i) for i in input().split()]

def buy(price):
    global money
    global beet
    beet = money // price
    money = money % price

def sell(price):
    global money
    global beet
    money += beet * price
    beet = 0

flag = True
for i in range(n-1):
    if flag:
        buy(a[i])
        flag = False
    if a[i] > a[i+1]:
        sell(a[i])
        flag = True
sell(a[-1])
print(money)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    i = 0
    stock = 0
    cash = 1000
    while i+1 < N:
        if A[i] < A[i+1] and stock == 0:
            stock += cash // A[i]
            cash -= stock * A[i]
            # print('buy {} at {} yen'.format(stock, A[i]))
        elif A[i] > A[i+1]:
            cash += stock * A[i]
            # print('sell {} at {} yen, total cash {}'.format(stock, A[i], cash))
            stock = 0
        i += 1
    else:
        cash += stock * A[-1]
        # print('sell {} at {} yen, total cash {}'.format(stock, A[-1], cash))
    print(cash)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,*A = map(int, open(0).read().split())
init = A[0]
cash = 1000
stock = 0
if A[1] <= A[0]:
    dif = -1
else:
    stock,cash = divmod(cash,A[0])
    dif = 1
for i in range(2,N):
    if A[i] > A[i-1]:
        if dif == -1:
            stock,cash = divmod(cash,A[i-1])
            dif = 1
    elif A[i] < A[i-1]:
        if dif == 1:
            cash = cash + stock * A[i-1]
            stock = 0
            dif = -1
if dif == 1:
    cash = cash + stock * A[N-1]
print(cash)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    init = 1000
    pinit = a[0]
    pprev = a[0]
    for i in range(1,len(a)):
        if(pprev > a[i]):
            c = init//pinit
            init -= c * pinit
            init += c*pprev
            pinit = a[i]
        pprev = a[i]
    if(pinit < a[n-1]):
        c = init//pinit
        init += c*(a[n-1] - pinit)
    print(init)
    return

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
dat = list(map(int, input().split()))
minval = maxval = dat[0]
kabu = 0
okane = 1000
prevval = dat[0]
for i in range(n):
    curval = dat[i]
    #print(">cur", curval)
    if curval == prevval:
        prevval = curval
        continue
    if curval > prevval:
        prevval = curval
        continue
    # curval のほうが小さい
    kabu = okane // minval
    okane -= (minval * kabu)
    #print(" buy ", kabu , "kabu by", (minval * kabu))
    okane += (prevval * kabu)
    #print(" sell ", kabu , "get", (prevval * kabu), "now okane", okane)
    minval = curval
    maxval = prevval
    prevval = curval
# 最後
#print("end")
curval = dat[n-1]
#print("minval", minval)
#print("curval", curval)
if curval > minval:
    kabu = okane // minval
    okane -= (minval * kabu)
    #print(" buy ", kabu , "kabu by", (minval * kabu))
    okane += (curval * kabu)
    #print(" sell ", kabu , "get", (curval * kabu))

print(okane)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))

ud = [0]

if A[1] > A[0]:
    trend = 1
elif A[1] == A[0]:
    trend = 0
else:
    trend = -1

if trend != 0:
    first_trend = trend
else:
    first_trend = 0
for i in range(1,N):
    if A[i] > A[i-1]:
        if first_trend==0:
            first_trend = 1
        if trend==-1:
            ud.append(i-1)
        trend = 1
    elif A[i] < A[i-1]:
        if first_trend==0:
            first_trend = -1
        if trend==1:
            ud.append(i-1)
        trend = -1

ud.append(N-1)

M = 1000

for i in range(len(ud)):
    if first_trend == 1:
        if i%2==0 and i!=len(ud)-1:
            stock = M // A[ud[i]]
            M = stock*A[ud[i+1]] + M % A[ud[i]]
    else:
        if i%2==1 and i!=len(ud)-1:
            stock = M // A[ud[i]]
            M = stock*A[ud[i+1]] + M % A[ud[i]]


print(M)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [A[0]]
Bf = [1]
C = []
for i in range(1, len(A)):
  if A[i-1] != A[i]:
    B.append(A[i])
    if A[i-1] < A[i]:
      Bf.append(0)
    else:
      Bf.append(1)
f = 1
for i in range(1, len(B)):
  if Bf[i-1] == f and Bf[i] == 1 - f:
    C.append(B[i-1])
    f = 1 - f
if Bf[-1] == 0:
  C.append(B[-1])
M = 1000
for i in range(len(C)//2):
  x = M // C[2*i]
  M = M - C[2*i] * x + C[2*i+1] * x
print(M)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 1000

for i in range(N-1):
    if A[i] < A[i+1]:
        k = M // A[i]
        M = M + (A[i+1] - A[i])*k

print(M)