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:
N=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(N-1)]
for i in range(N-1):
  if A[i]<A[i+1]:
    B[i]=1
B=[0]+B
money=1000
tmp=0
up=[]
down=[]
for i in range(N-1):
  if B[i]==0 and B[i+1]==1:
    up.append(i)
  if B[i]==1 and B[i+1]==0:
    down.append(i)
import bisect   
if up:
  if down==[]:
    down.append(N-1)
  if down!=[] and down[-1]<up[-1]:
    down.append(N-1)

for i in range(len(up)):
  k=bisect.bisect_left(down,up[i])
  money+=(A[down[k]]-A[up[i]])*(money//A[up[i]])     
print(money)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math


def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))

n = get_int()
ls = get_list()
peak_pts = []
inc = True if ls[1]>ls[0] else False
if ls[1]>ls[0]:
    peak_pts.append(0)
i = 1
while i<n:
    if ls[i]>=ls[i-1]:
        if not inc:
            peak_pts.append(i - 1)
            inc = not inc
    else:
        if inc:
            peak_pts.append(i-1)
            inc = not inc
    i += 1
if ls[-1]>=ls[-2]:
    peak_pts.append(n-1)

#print(peak_pts)
profit = 1000
le = len(peak_pts)
ava_bought,ava_sell = 1000,0
for ind in range(0,le,2):
    i = peak_pts[ind]
    if ind+1<le:
        midprofit = 0

        # Buy
        j = i
        totalshares = 0
        while j<peak_pts[ind+1]:
            shares = (ava_bought//ls[j])
            ava_bought -= shares*ls[j]
            midprofit -= shares*ls[j]
            ava_sell += shares*ls[j]
            totalshares += shares
            if ava_bought==0: break
            if j+1<n and ls[j+1]>ls[j]: break
            j += 1

        #Sell
        j = peak_pts[ind+1]
        midprofit += ls[j]*totalshares
        if midprofit>0:
            profit += midprofit
        ava_bought = profit
        #print(ava_bought, ava_sell, midprofit,totalshares)
print(profit)

Submission status: Accepted

Solution code:
import sys
import itertools


def resolve(in_):
    n = int(next(in_))
    a = tuple(map(int, next(in_).split()))
    
    m = 1000
    s = 0

    b, c = itertools.tee(a)
    next(c)
    for x, y in zip(b, c):
        # print(f'{x=} {y=}')
        if x < y:
            ss, mm = divmod(m, x)
            m = mm
            s += ss
        elif x > y:
            mm = x * s
            m += mm
            s = 0
        # print(m, s)
    else:
        mm = y * s
        m += mm
        s = 0
        # print(m, s)

    return m


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n = int(input())
aL = list(map(int, input().split(" "))) + [0]
bL = ["NO" for _ in range(n)]

mk = 0
mm = 1000

up = False
for i in range(n):
    cr = aL[i]
    nx = aL[i + 1]

    if up:
        if cr > nx:
            up = False
            mm += mk * cr
            mk = 0
    else:
        if cr < nx:
            up = True
            mk = mm // cr
            mm = mm % cr

print(mm)

Submission status: Accepted

Solution code:
n = int(input())
la = [10000]+[int(w) for w in input().split()]+[-1]

money = 1000

cheap = la[1]
for i in range(2, len(la)):
    if la[i] >= la[i-1]:
        cheap = min(cheap, la[i-1])
        continue
    if la[i-1] >= la[i-2]:
        kabu = money//cheap
        money += kabu*(la[i-1] - cheap)
        cheap = la[i]
    cheap = min(cheap, la[i])
print(money)

Submission status: Accepted

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

for i in range(N):
    if i == N - 1:
        asset += stock * A[i]
        stock = 0
    else:
        if A[i] < A[i + 1]:
            r, v = divmod(asset, A[i])
            # print(r, v)
            stock += r
            asset = v
        else:
            asset += stock * A[i]
            stock = 0
print(asset)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().strip().split()))
money=1000
stock=0
for n in range(N):
    if n<N-1:
        if A[n]<A[n+1]:
            if money>=A[n]:
                stock+=money//A[n]
                money%=A[n]
        else:
            money+=A[n]*stock
            stock=0
    else:
        money+=A[n]*stock
print(money)

Submission status: Accepted

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

a = a + [0]
b = 1000
c = 0
for i in range(1, n):
    numb = a[i-1]
    numa = a[i]
    numaa = a[i+1]
    if numb < numa and b > c*100:
        c = b//numb
        b = b%numb
    if numa > numaa:
        b += c*numa
        c = 0

print(b)

Submission status: Accepted

Solution code:
#-*- using:utf-8 -*-

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

money = 1000
kabu = 0

for i in range(N-1):
    if A[i] < A[i+1]:
        #買い
        tmp = money // A[i]
        money = money - tmp*A[i]
        kabu = kabu+tmp
        #売り
        money = money + kabu*A[i+1]
        kabu = 0
print(money)

Submission status: Accepted

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

stock = 0
money = 1000
prev_trend = a[1] - a[0]

if prev_trend > 0:
    stock += money // a[0]
    money -= a[0] * (money // a[0])

if len(a) > 2:
    for i in range(1, n-1):
        next_trend = a[i+1] - a[i]
        if prev_trend >= 0 and next_trend < 0:
            money += a[i] * stock
            stock = 0
        elif prev_trend <= 0 and next_trend > 0:
            stock += money // a[i]
            money -= a[i] * (money // a[i])
        prev_trend = a[i+1] - a[i]

money += a[n-1] * stock
stock = 0

print(money)

Submission status: Accepted

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

p = 1000
n = 0
for i in range(N-1):
    if A[i+1] > A[i]:
        n += p//A[i]
        p = p % A[i]

    if A[i+1] < A[i]:
        p += n*A[i]
        n = 0

p += n*A[-1]
print(p)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N = z()
A = zz()

diff = [0]*(N-1)
prev = A[0]
for i in range(1, N):
    diff[i - 1] = A[i] - A[i - 1]
ans = 0
# n日目に全部売ってゲームを終わるとする
for n in range(N):
    money = 1000
    kabu = 0
    for i in range(N):
        if (i == n):
            money += kabu*A[i]
            kabu = 0
            ans = max(ans, money)
            # print(i)
            break

        if (diff[i] > 0):
            buy_kabu = (money//A[i])
            money -= (A[i]*buy_kabu)
            kabu += buy_kabu
        else:
            money += kabu*A[i]
            kabu = 0

        # print(money, kabu)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

# どこで反転するかを記録する
pre = [0] * N
pre_index = 0
old_a = A[0]
if A[0] > A[1]:
    old_coef = -1
elif A[0] < A[1]:
    old_coef = 1
else:
    old_coef = 0

for i in range(1, N):
    if A[i] > old_a:
        coef = 1
    elif A[i] < old_a:
        coef = -1
    else:
        coef = 0
    if coef != 0 and coef != old_coef:
        for j in range(pre_index, i):
            pre[j] = i - 1
        pre_index = i
        old_coef = coef
    old_a = A[i]
for j in range(pre_index, N):
    pre[j] = N - 1
# print("pre: {}".format(pre))

shojikin = 1000
stock = 0
if A[0] < A[pre[0]]:
    q, mod = divmod(shojikin, A[0])
    stock += q
    shojikin = mod
elif pre[0] == N - 1:
    # 何もしないほうが良い場合
    print('1000')
    quit()

# print("1st shojikin: {} stock: {}".format(shojikin, stock))

pre = list(set(pre))
pre.sort()
# print("sorted: {}".format(pre))
for deal_index in pre:
    if stock:
        shojikin += stock * A[deal_index]
        stock = 0
        # print("uri deal: {} shojikin: {} stock: {}".format(deal_index, shojikin, stock))
    else:
        q, mod = divmod(shojikin, A[deal_index])
        stock += q
        shojikin = mod
        # print("kai deal: {} shojikin: {} stock: {}".format(deal_index, shojikin, stock))
# 下がり続けた場合は払い戻し
if stock:
    shojikin += stock * A[deal_index]
    stock = 0
print(shojikin)

Submission status: Accepted

Solution code:
N=int(input())
a_list=list(map(int,input().split()))
K=1000//a_list[0]
L=1000-K*a_list[0]
sum=K*a_list[0]+L
for i in range(N-1):
    if   a_list[i]<a_list[i+1]:
        sum=K*a_list[i+1]+L
        #print(i,K,L,sum)
    elif a_list[i]>a_list[i+1]:
        K=sum//a_list[i+1]
        L=sum-K*a_list[i+1]
print(sum)

Submission status: Accepted

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

Budget = 1000
Bond = 0

for n in range(len(A)-1):
  if A[n] < A[n+1]:
    Bond = Budget//A[n]
    Budget = (Budget - Bond*A[n]) + Bond*A[n+1]
    
print(Budget)

Submission status: Accepted

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

kabu=0
money=1000
x=x-1
lastday=0
for i in range(len(A)):
    if A[x-i]>A[x-i-1]:
        lastday=x-i
        break
    
for i in range(lastday):
    if A[i]<A[i+1]:
        buy=money//A[i]
        money-=A[i]*buy
        kabu+=buy
    elif A[i]>A[i+1]:
        money+=A[i]*kabu
        kabu=0

money+=A[lastday]*kabu
print(money)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
mochi=1000
x=A[0]
y=0
k=0
kabu=0
for i in range(1,N):
    if i<N-1:
        if A[i-1]<=A[i] and A[i]>=A[i+1]:
            x=A[i]
            y=min(A[k:i])
            kabu=mochi//y
            mochi-=kabu*y
            mochi+=kabu*x
            k=i
    else:
        if A[i-1]<A[i]:
            x=A[i]
            y=min(A[k:i])
            kabu=mochi//y
            mochi-=kabu*y
            mochi+=kabu*x
            k=i

print(mochi)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

print(cash)

Submission status: Accepted

Solution code:
#D
N=int(input())
A = list(map(int, input().split()))
ans=1000
for i in range(1,len(A)):
    if A[i-1]<A[i]:
        ans=ans+(ans//A[i-1])*(A[i]-A[i-1])
print(ans)

Submission status: Accepted

Solution code:
#M-SOLUTIONS D
n = int(input())
a = list(map(int, input().split()))
money = 1000
stocks = 0
signal = 0
for i in range(len(a)-1):
  if signal == 0:
    if a[i+1] > a[i]:
      stocks, money = divmod(money, a[i])
      signal = 1
      #print(i,money,stocks)
  else:
    if a[i+1] < a[i]:
      money += stocks * a[i]
      stocks = 0
      signal = 0
      #print(i,money,stocks)
money += stocks*a[-1]
print(money)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys

N = int(sys.stdin.readline())

A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

cur = 1000
for i in range(N-1):
    if A[i] < A[i+1]:
        cur = (A[i+1]-A[i])*(cur//A[i])+cur
    #print(i,cur)
print(cur)

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    s = [0] * n
    for i in range(n - 1):
        if a[i + 1] > a[i]:
            s[i + 1] = 1
        elif a[i + 1] == a[i]:
            continue
        else:
            s[i + 1] = -1
    #print(s)
    tak = 1000
    stock = 0
    for i in range(n - 1):
        if s[i + 1] == 1 and not stock:
            stock = tak // a[i]
            tak = tak % a[i]
        elif s[i + 1] == -1 and stock:
            tak += stock * a[i]
            stock = 0
    if s[-1] >= 0:
        tak += a[-1] * stock
    print(tak)


solve()

Submission status: Accepted

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

l = []
s = 0
for i in range(N-1):
    if A[i] > A[i+1]:
        l.append([s,i])
        s = i+1
    else:
        continue

l.append([s,N-1])

ans = 1000
for s,e in l:
    kabu = (ans//A[s])
    ans += (A[e]-A[s])*kabu
    ##print(ans,kabu)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=1000
k=0
peak=-1
for i in range(n-1):
    if a[i]<a[i+1]:
        peak=i+1

for i in range(peak):
    if a[i+1]>a[i] and k==0:
        k=m//a[i]
        m-=k*a[i]
#        print(k,m,"rise")
    elif a[i+1]<a[i]:
        m+=k*a[i]
        k=0
#        print(k,m,"fall")
if peak!=-1:
    m+=k*a[peak]
    k=0
#    print(k,m,"peak")
print(m)

Submission status: Accepted

Solution code:
N = int(input())
stocks = list(map(int,input().split()))
now_stock = stocks[0]
cash = 1000
max_min_stocks = []
if now_stock <= stocks[1]:
    up_flag = True
    max_min_stocks.append(stocks[0])
else:
    up_flag = False
f_up_flag = up_flag
i = 1

while i < N:
    next_stock = stocks[i]
    if up_flag:
        if now_stock <= next_stock:
            now_stock = next_stock
        else:
            max_min_stocks.append(now_stock)
            up_flag = False
    else:
        if now_stock >= next_stock:
            now_stock = next_stock
        else:
            max_min_stocks.append(now_stock)
            up_flag = True
    now_stock = next_stock
    i += 1
if up_flag:
    max_min_stocks.append(stocks[-1])
else:
    max_min_stocks.append(stocks[-1])
# print(max_min_stocks)

if len(max_min_stocks) >= 2:
    for i in range(len(max_min_stocks) // 2):
        hold_stocks = cash // max_min_stocks[2 * i]
        cash -= hold_stocks * max_min_stocks[2 * i]
        cash += hold_stocks * max_min_stocks[2 * i + 1]
print(cash)

Submission status: Accepted

Solution code:
N=int(input())
A= list(map(int,input().split()))
kabu=0
kane=1000
kabukin=0
for a in range(N-1):
    if A[a]<A[a+1] and kane>A[a]:
        #if kabukin<A[a]*kabu:
            kabu=int(kane/A[a])
            kabukin=kabu*A[a]
            kane=kane-kabu*A[a]
    elif A[a]>A[a+1] and kabu>=1:
        kane=kane+kabu*A[a]
        kabu=0

if kabu>0:
    kane+=kabu*A[-1]
print(kane)

Submission status: Accepted

Solution code:
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    n = int(stdin.readline().rstrip())
    A = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    money = 1000
    kabu = 0
    down = 0
    up = 0
    kijun = A[0]
    for i in range(1,n):
        a = A[i]
        if i == 1:
            if kijun < a:
                buy = kijun
                katta = money//buy
                kabu += katta
                money -= katta*buy
                down = 0
                up = 1
                kijun = a
            elif kijun > a:
                down = 1
                kijun = a
        if up == 1:
            if kijun > a:
                sell = kijun
                money += sell * kabu
                kabu = 0
                up = 0
                down = 1
                kijun = a
            else:
                kijun = a
        elif down == 1:
            if kijun < a:
                buy = kijun
                katta = money//buy
                kabu += katta
                money -= katta*buy
                down = 0
                up = 1
                kijun = a
            else:
                kijun = a
        else:
            if kijun < a:
                buy = kijun
                katta = money//buy
                kabu += katta
                money -= katta*buy
                down = 0
                up = 1
                kijun = a
            elif kijun > a:
                sell = kijun
                money += sell * kabu
                kabu = 0
                up = 0
                down = 1
                kijun = a
    if kabu > 0:
        money += kabu * A[-1]
    print(money)




if __name__ == '__main__':
    solve()

Submission status: Accepted

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

buysold = [0]*n
for i in range(n-1):
    if a[i+1] < a[i]:
        buysold[i] = 1
#print(buysold)
res = 1000
flag = False
kabu = 0
for i in range(n):
    if buysold[i] == 0 and not flag:
        kabu = res // a[i]
        res -= kabu*a[i]
        flag = True
    if buysold[i] == 1 and flag:
        res += kabu*a[i]
        kabu = 0
        flag = False

if buysold[n-1] == 0:
    res += kabu*a[n-1]
print(res)

Submission status: Accepted

Solution code:

def main():
    N = int(input())
    A = [int(x) for x in input().split(" ")]
    cash = 1000
    stock = 0
    for i in range(N-1):
        if A[i] < A[i+1]:
            stock += cash // A[i]
            cash = cash % A[i]
        elif stock != 0 and A[i] > A[i+1]:
            cash = cash + A[i]*stock
            stock = 0
    print(cash + A[-1]*stock)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
a=0
c=1000
for i in range(N-1):
  if A[i]<A[i+1] and a==0:
    a,c=divmod(c,A[i])
    sb="False"
  elif A[i]>A[i+1] and a>0:
    c+=a*A[i]
    a=0

print(a*A[-1]+c)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    small = [a[0]]
    diff = 1  # 1: increasing, 0: decreasing
    for i in range(1, n):
        if (a[i] < a[i - 1] and diff == 1) or (a[i] > a[i - 1] and diff == 0):
            small.append(a[i - 1])
            diff += 1
            diff %= 2
    small.append(a[-1])
    ans = 1000
    stock = 0
    for i, s in enumerate(small):
        if i % 2 == 0:
            stock += ans // s
            ans %= s
        else:
            ans += s * stock
            stock = 0
    if stock > 0:
        ans += stock * small[-1]
    print(max(1000, ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 1000
    pm = 1
    for i in range(n-1):
        if a[i] < a[i+1]:
            t = ans // a[i]
            ans += t * (a[i+1] - a[i])

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import os
import heapq
import sys
import math
import bisect
import operator
from collections import defaultdict
from io import BytesIO, IOBase
def gcd(a,b):
    if b==0:

        return a
    else:
        return gcd(b,a%b)
def power(x, p,m):
    res = 1
    while p:
        if p & 1:
            res = (res * x) % m
        x = (x * x) % m
        p >>= 1
    return res
def inar():
    return [int(k) for k in input().split()]


# def bubbleSort(arr,b):
#     n = len(arr)
#     for i in range(n):
#         for j in range(0, n - i - 1):
#             if arr[j] > arr[j + 1] and b[j]!=b[j+1]:
#                 arr[j], arr[j + 1] = arr[j + 1], arr[j]
#                 b[j],b[j+1]=b[j+1],b[j]
def lcm(num1,num2):
    return (num1*num2)//gcd(num1,num2)

def main():
    #for _ in range(int(input())):
    n=int(input())
    arr=inar()
    mn=arr[0]
    mx=arr[0]
    take=1000
    for i in range(1,n):
        if arr[i]<mx:
            got=take//mn
            rem=take%mn
            take=got*mx
            take+=rem
            mx=arr[i]
            mn=arr[i]
        else:
            mx=max(arr[i],mx)
    got = take // mn
    rem = take % mn
    take = got * mx
    take += rem
    print(take)














BUFSIZE = 8192


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)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    INF = 10 ** 18
    last_max = A[0]
    last_min = A[0]

    money = 1000
    stock = 0
    old_trend = 0
    trend = A[1] - A[0]
    buy_point = []
    bought_point = []

    for i in range(N-1):
        trend = A[i+1] - A[i]
        if trend * old_trend > 0 or trend == 0:
            continue
        else:
            if trend > 0:
                buy_point.append(i)
            if trend < 0:
                bought_point.append(i)
        old_trend = trend

    if len(buy_point) > len(bought_point):
        bought_point.append(N-1)

    for i in range(N):
        if i in buy_point:
            buy = money//A[i]
            stock += buy
            money -= buy*A[i]

            nx_bought_idx = bisect_right(bought_point,i)
            bought_value = A[nx_bought_idx]
            j = i - 1
            while j >= 0 and money >= 100:
                if A[j] < bought_value and money >= A[i]:
                    money -= A[j]
                    stock += 1
                    break
                j -= 1
        
        if i in bought_point:
            bought = stock
            stock = 0
            money += bought * A[i]
    print(money)
    


if __name__ == "__main__":
    main()

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]:
      have = M // A[i]
      rest = M % A[i]
      M = have*A[i+1]+rest
      
print(M)

Submission status: Accepted

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

money = 1000


for i in range(1, n):
  p_now = arr[i]
  p_before = arr[i-1]
  if p_before < p_now:
    stock = money // p_before
    money += stock*(p_now - p_before)

print(money)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

count = 0
set = [a[0]]

for i in range(n-1):
    if a[i] >= a[i+1]:
        count += 1
if count == n-1:
    print(1000)
    exit()

for i in range(1,n):
    if a[i-1] != a[i]:
        set += [a[i]]

#print(set)
num = len(set)
seifu = 0

set2 = [set[0],set[1]]

if set[0] > set[1]:
    seifu = -1
else:
    seifu = 1

i_now = 1

for i in range(2,num):
    if set[i-1] < set[i] and seifu < 0:
        set2 += [set[i]]
        seifu = 1
        i_now += 1
    elif set[i-1] < set[i] and seifu > 0:
        set2[i_now] = set[i]
    elif set[i-1] > set[i] and seifu > 0:
        set2+= [set[i]]
        i_now += 1
        seifu = -1
    elif set[i-1] > set[i] and seifu < 0:
        set2[i_now] = set[i]


if set2[0] > set2[1]:
    set2 = set2[1:]

if len(set2)%2 != 0:
    set2 = set2[:len(set2)-1]



buy = 0
coin = 1000
num2 = 0

for i in range(len(set2)-1):
    if set2[i] < set2[i+1] and buy == 0:
        num2 = coin//set2[i]
        coin = coin - set2[i] * num2
        buy = 1

    elif set2[i] > set2[i+1] and buy == 1:
        coin = coin + num2 * set2[i]
        buy = 0


coin += num2*set2[len(set2)-1]

print(coin)

Submission status: Accepted

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

money=1000
stocks=0

for i in range(N): 
    if i==N-1:
        #売る
        money+=(A[i]*stocks)
        stocks=0
    elif A[i+1]>A[i]:
        #買う
        plus_stock,money=divmod(money,A[i])
        stocks+=plus_stock
    elif A[i+1]<A[i]:
        #売る
        money+=(A[i]*stocks)
        stocks=0
print(money)

Submission status: Accepted

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

dp = [[[0]*2 for _ in range(2)] for _ in range(N)]

dp[0][0][0] = 1000
dp[0][1][0] = 1000%A[0]
dp[0][1][1] = 1000//A[0]

for i, a in enumerate(A):
  if i == 0:
    dp[0][0][0] = 1000
    dp[0][1][0] = 1000%a
    dp[0][1][1] = 1000//a
  else:
    if dp[i-1][0][0] < dp[i-1][1][0] + dp[i-1][1][1]*a:
      dp[i][0][0] = dp[i-1][1][0] + dp[i-1][1][1]*a
    else:
      dp[i][0][0] = dp[i-1][0][0]
    if dp[i-1][1][1] < dp[i][0][0]//a or dp[i-1][1][1] == dp[i][0][0]//a and dp[i-1][1][0] < dp[i][0][0]%a:
      dp[i][1][0] = dp[i][0][0]%a
      dp[i][1][1] = dp[i][0][0]//a
    else:
      dp[i][1][0] = dp[i-1][1][0]
      dp[i][1][1] = dp[i-1][1][1]
if dp[N-1][0][0] < dp[N-1][1][0] + dp[N-1][1][1]*A[N-1]:
  print(dp[N-1][1][0] + dp[N-1][1][1]*A[N-1])
else:
  print(dp[N-1][0][0])

Submission status: Accepted

Solution code:
import numpy as np
import copy

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

#買い0_売り1
trigger = 0

As_seiri = []

tmp = 0
for i in range(N-1):
    if(As[i] < As[i+1] and trigger == 0):
        As_seiri.append(As[i])
        trigger = 1
        continue

    elif(As[i] > As[i+1] and trigger == 1):
        As_seiri.append(As[i])
        trigger = 0
        continue

#print(As_seiri, trigger)

if(len(As_seiri) == 0):
    print("1000")
    exit()


money = 1000
kabu = 0

for A in As_seiri:
    if(kabu == 0):
        kabu = money // A
        money = money - kabu * A
    
    else:
        money = money + (kabu * A)
        kabu = 0

print(money + kabu * As[-1])

Submission status: Accepted

Solution code:
#Problem D
N = int(input())
a = list(map(int,input().split()))

atm = 1000

for i in range(N-1):
    kb = 0
    if a[i+1] > a[i]:
        kb = atm//a[i]
        atm -= a[i]*kb
        atm += a[i+1]*kb
    elif a[i+1] < a[i]:
        pass

print(atm)

Submission status: Accepted

Solution code:
n=int(input())
inp = list(map(int,input().split()))
ini=(0,1000)
now=(0,1000)
m=inp[0]
now=(1000//m,1000%m)
flag=0
for i in range(1,len(inp)):
    if inp[i]>m:
        ini=(0,now[0]*inp[i]+now[1])
        now=(ini[1]//inp[i],ini[1]%inp[i])
        m=inp[i]
    else:
        now=(ini[1]//inp[i],ini[1]%inp[i])
        m=inp[i]
print (ini[1])

Submission status: Accepted

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

yen = 1000

kabu = 0

for i in range(n-1):
    if a[i] < a[i+1]:
        kabu_today = yen // a[i]
        kabu += kabu_today
        yen = yen % a[i]
        
    else:
        yen += kabu * a[i]
        kabu = 0
    
#    print(yen, kabu,a[i], a[i] < a[i+1])

yen += kabu * a[n-1]
kabu = 0

print(yen)

Submission status: Accepted

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