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.

Solution (Python):
def main():
    _ = int(input())
    *A, = map(int, input().split())
    A += [0]

    money = 1000
    stock = 0
    for a, b in zip(A, A[1:]):
        money += stock * a
        stock = 0
        if a < b:
            buy, rest = divmod(money, a)
            stock = buy
            money = rest
    print(money)


if __name__ == '__main__':
    main()

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

mon = 1000
kabu = 0

for i in range(N-1):
  if A[i] <= A[i+1]:
    kabu, mon = divmod(mon, A[i])
    mon += kabu * A[i+1]
    
print(mon)

Solution (Python):
n = int(input())
stocks = [int(x) for x in input().split()]
mymoney = 1000
mystock = 0

for i in range(0,len(stocks)-1):     
      
      if stocks[i] < stocks[i+1]:    
            
            mystock += mymoney//stocks[i]
            mymoney = mymoney%stocks[i]
      elif stocks[i] >= stocks[i+1]:  
            
            mymoney += mystock*stocks[i]
            mystock = 0
      

i += 1
mymoney += mystock * stocks[i]      
mystock = 0

print(mymoney)

Solution (Python):
def main():
    N=int(input())
    A=list(map(int,input().split()))
    ans=1000
    stocks=0
    for i in range(N-1):
        if A[i]>A[i+1]:
            ans+=stocks*A[i]
            stocks=0
        else:
            stocks+=(ans//A[i])
            ans-=(ans//A[i])*A[i]
    print(ans+stocks*A[-1])
if __name__=='__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
m = 1000
stocks = 0
drops = [False]*(n-1)
for i in range(n-1):
    if a[i] > a[i+1]:
        drops[i] = True
for i in range(n-1):
    if drops[i]:
        m+=stocks*a[i]
        stocks = 0
    else:
        stocks+=m//a[i]
        m -= (m//a[i])*a[i]
print(m + stocks*a[-1])

Solution (Python):
import copy


def get_int():
    return int(input())


def get_string():
    return input()


def get_int_list():
    return [int(x) for x in input().split()]


def get_string_list():
    return input().split()


def get_int_multi():  
    return map(int, input().split())


def get_string_char_list():
    return list(str(input()))





'''
while (idx < n) and ():

    idx += 1
'''

def main():

    n = get_int()
    a_list = get_int_list()

    w_min = a_list[0]
    w_max = a_list[0]
    pre = a_list[0]
    kabu = 0
    kane = 1000

    for i in range(1, n):

        if pre < a_list[i] and kabu == 0:
            kabu = kane // w_min
            kane = kane - kabu * w_min
            w_max = a_list[i]

        elif pre > a_list[i] and kabu > 0:
            kane = kane + w_max * kabu
            kabu = 0
            w_min = a_list[i]

        elif pre < a_list[i] and kabu > 0:
            w_max = a_list[i]

        elif pre > a_list[i] and kabu == 0:
            w_min = a_list[i]



        pre = a_list[i]

    if kabu > 0:
        kane = kane + w_max * kabu

    print(kane)






if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=list(map(int, input().split()))
mon=1000
kai=0
for i in range(n-1):
  if a[i]>a[i+1]:
    mon+=kai*a[i]
    kai=0
  elif a[i]<a[i+1] and kai==0:
    kai=int(mon/a[i])
    mon-=kai*a[i]

mon+=kai*a[n-1]

print(mon)

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    L=[0]*N
    
    
    for i in range(1,N):
        if A[i]>A[i-1]:
            L[i]=1
            if L[i-1]==1:
                L[i-1]=0
            else:
                L[i-1]=2
                
    mon=1000
    kabu=0
    
    for i in range(N):
        if L[i]==2:
            kabu=mon//A[i]
            mon-=kabu*A[i]
        elif L[i]==1:
            mon+=kabu*A[i]
            kabu=0
            
    print(mon)
                
    

main()

Solution (Python):
num = int(input())
kabu = [int(x) for x in input().split()]
kabu.append(-1)
mkabu = 0
max = 0
money = 1000
MAX = 0

for i in range(num):
    if MAX < kabu[i]:
        MAX = kabu[i]


for i in range(num):
    if kabu[i] == -1:
        bleak
    if 0 < mkabu: 
        money = money + kabu[i] * mkabu
        mkabu = 0


    if kabu[i] < kabu[i+1]: 
        mkabu = money // kabu[i]
        money = money % kabu[i]

if 0 < mkabu:
    money = money + kabu[-1] * mkabu

print(money)

Solution (Python):
def solve(n, a):
    ans = 1000
    for i in range(n-1):
        if a[i] < a[i+1]:
            ans += (ans // a[i]) * (a[i+1] - a[i])
    return ans

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

Solution (Python):
from typing import List


def solve(A: List[int], N: int) -> int:
    current_money = 1000
    for i in range(N - 1):
        stocks = 0

        if A[i] < A[i + 1]:
            stocks = current_money // A[i]
        current_money += (A[i + 1] - A[i]) * stocks
    return current_money


def main():
    N = int(input())
    A = [int(x) for x in input().split(" ")]

    print(solve(A, N))


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
ans = 1000
stock = 0
for i in range(n-1):
    if a[i+1] > a[i]:
        buy = ans//a[i]
        stock += buy
        ans -= buy*a[i]
    else:
        ans += stock*a[i]
        stock = 0

ans += stock*a[-1]
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, XS):
    cash = 1000
    stock = 0
    for i in range(N - 1):
        price = XS[i]
        if cash >= price:
            if XS[i + 1] > price:
                
                s = cash // price
                stock += s
                cash -= s * price
                continue
        if stock > 0:
            if XS[i + 1] < price:
                
                cash += stock * price
                stock = 0
    
    cash += stock * XS[-1]
    return cash


def main():
    
    N = int(input())
    XS = list(map(int, input().split()))
    print(solve(N, XS))



T1 = """
7
100 130 130 130 115 115 150
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1685
"""

T2 = """
6
200 180 160 140 120 100
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
1000
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

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

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

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

print(money)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

money = 1000
stock = 0

def is_minimal(idx):
    if idx!=N-1:
        if A[idx+1]>A[idx]:
            return True
        else:
            return False

def is_maximal(idx):
    if idx!=N-1:
        if A[idx+1]<A[idx]:
            return True
        else:
            return False

for i in range(N-1):
    if is_minimal(i):
        stock += money//A[i]
        money %= A[i]
    elif is_maximal(i):
        money += A[i]*stock
        stock = 0

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

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

currentmoney = 1000
stock = 0

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

print(currentmoney)

Solution (Python):



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


max_list = [0] * N
max_list[0] = 1000


for i in range(1, N):
    for j in range(0, i):
        a_remain = max_list[j] % a_nums[j]
        a_count = max_list[j] // a_nums[j]
        max_list[i] = max(max_list[j], a_nums[i]*a_count+a_remain)


print(max_list[N-1])

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

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

money = 1000
stock = 0

for i in range(N-1) :
  if A[i] > A[i+1] :
    money += stock * A[i]
    stock = 0
  elif A[i] < A[i+1] :
    temp = int(money / A[i])
    stock += temp
    money -= temp * A[i]
    
money += stock * A[N-1]
stock = 0
print(money)

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

x = 1000
for i in range(n-1):
    l = a[i]
    r = a[i+1]
    if (l < r):
        k = x//l
        x %= l
        x += k*r

print(x)

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

x = 1000
for i in range(n-1):
    l = a[i]
    r = a[i+1]
    if (l < r):
        k = x//l
        x %= l
        x += k*r

print(x)

Solution (Python):
N = int(input())
An = list(map(int, input().split()))
dp = [0 for x in range(N+10)]
dp[0] = 1000
for i in range(1, N):
    stock = dp[i-1] // An[i-1]

    money = dp[i-1]
    money -= stock * An[i-1]
    money += stock * An[i]

    dp[i] = max(dp[i-1], money)
print(dp[N-1])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
money = 1000
stock = 0

if a[0] <= a[1]:
    stock = money // a[0]
    money -= stock * a[0]

for i in range(1, n-1):
    if a[i] <= a[i-1] and a[i] <= a[i+1] and stock == 0:
        stock = money // a[i]
        money -= stock * a[i]
    if a[i] >= a[i-1] and a[i] >= a[i+1] and stock != 0:
        money += stock * a[i]
        stock = 0
if stock > 0:
    money += stock * a[-1]
    stock = 0
print(money)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    actions = ['' for _ in range(N)]
    left = 0
    for right in range(1, N):
        if A[right - 1] > A[right]:
            if left != right - 1:
                actions[left] = 'buy'
                actions[right - 1] = 'sell'
            left = right
    if left != right:
        actions[left] = 'buy'
        actions[right] = 'sell'
    money = 1000
    stock = 0
    for i, action in enumerate(actions):
        if action == 'buy':
            stock = money // A[i]
            money -= stock * A[i]
        elif action == 'sell':
            money += stock * A[i]
            stock = 0
    print(money)


if __name__ == '__main__':
    main()

Solution (Python):

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

dp=[0 for i in range(N)]
dp[0]=1000

for i in range(1,N):
    for j in range(i,N):
        
        dp[j]=max(dp[j-1],dp[j],dp[i-1]+(dp[i-1]//A[i-1])*(A[j]-A[i-1]))
        
print(dp[-1])

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

cash = 1000
stock = 0

for i in range(len(A)-1):
  next_trend = A[i+1] - A[i]
  price = A[i]
  
  
  if next_trend > 0 : 
    n = cash//price
    cash, stock = cash - n*price, stock + n
  if next_trend < 0: 
    cash = cash + stock*price
    stock = 0
  

if stock:
  cash += stock*A[-1]
  
print(cash)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]

possess = 1000

for i in range(N-1):
    if A[i] < A[i+1]:
        stock = possess//A[i]
        possess = possess % A[i] + A[i+1] * stock


print(possess)

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

money = 1000
for i in range(n-1):
    if a[i] < a[i+1]:
        money += (a[i+1]-a[i])*(money//a[i])
print(money)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
dp = [0]*n
dp[0] = 1000
for i in range(1,n):
  dp[i] = dp[i-1]
  for j in range(i):
    kabu = dp[j]//a[j]
    money = dp[j]+(a[i]-a[j])*kabu
    dp[i] = max(dp[i],money)
print(dp[-1])

Solution (Python):
def main(sample_file = ''):

    """ convenient functions
    
    
    
    
    
    """

    """convenient decorator
    
    
        
        
        
        
        
        
        
        
        
        
    """
    
    
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product 
    
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  
        b, e = 2, 0  
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):   
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict 
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
    from copy import deepcopy, copy 
    import operator
    from operator import itemgetter 
    
    
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd 
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)
    def make_divisors(n, reversed=False):
        """create list of divisors
        
        Args:
            number (int): number from which list of divisors is created
            reversed (bool, optional): ascending order if False. Defaults to False.
        
        Returns:
            list: list of divisors
        """
        divisors = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n//i)
        return sorted(list(divisors),reverse=reversed)
    
    
    
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    AtoZ = list('abcdefghijklmnopqrsruvwxyz') 
    modpow = lambda a, n, p = MOD: pow(a, n, p) 
    def modinv(a, p = MOD):
        
        
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        
        
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    class SegTree:
        """
        ref: https://qiita.com/takayg1/items/c811bd07c21923d7ec69
        init(init_val, ide_ele): 配列init_valで初期化 O(N)
        update(k, x): k番目の値をxに更新 O(logN)
        query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
        """
        def __init__(self, init_val, segfunc, ide_ele):
            """
            init_val: 配列の初期値
            segfunc: 区間にしたい操作
            ide_ele: 単位元
            n: 要素数
            num: n以上の最小の2のべき乗
            tree: セグメント木(1-index)
            """
            n = len(init_val)
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.num = 1 << (n - 1).bit_length()
            self.tree = [ide_ele] * 2 * self.num
            
            for i in range(n):
                self.tree[self.num + i] = init_val[i]
            
            for i in range(self.num - 1, 0, -1):
                self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

        def update(self, k, x):
            """
            k番目の値をxに更新
            k: index(0-index)
            x: update value
            """
            k += self.num
            self.tree[k] = x
            while k > 1:
                self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
                k >>= 1

        def query(self, l, r):
            """
            [l, r)のsegfuncしたものを得る
            l: index(0-index)
            r: index(0-index)
            """
            res = self.ide_ele
            l += self.num
            r += self.num
            while l < r:
                if l & 1:
                    res = self.segfunc(res, self.tree[l])
                    l += 1
                if r & 1:
                    res = self.segfunc(res, self.tree[r - 1])
                l >>= 1
                r >>= 1
            return res

    
    
    
    
    
    
    
    

    def BellmanFord(N, M, ABC, vertex_start, vertex_end, value_if_inf = -1, find_shortest = False):
        """to calculate furthest or shortest length between vertex_start and vertex_end using BellmanFord algorithm
        
        Args:
            N (int): number of vertices
            M (int): number of edges
            ABC (list): [(ai, bi, ci) for _ in range(N)] where i-th edge is directed from vertex ai to vertex bi and the length is ci 
            vertex_start (int): start vertex. usually use 0.
            vertex_end (int): end vertex. usually use N-1.
            value_if_inf (int or string as you like, optional): value you want when the furthest (or shortest) distance is infinite (or -infinite). Defaults to -1.
            find_shortest (bool, optional): choose False to find furthest path. Defaults to False.
        
        Returns:
            int or string: normally int (but can be str if you set value_if_inf to str)
            
        Example:
                N, M, P = R()
                ABC = [R() for _ in range(M)]
                ABC = [(a-1, b-1, c-P) for a, b, c in ABC]
                print(BellmanFord(N, M, ABC, 0, N-1, value_if_inf = 'inf'))

        """

        def make_reachable_list(N, M, ABC, vertex_start, vertex_end):
            reachable_to_direct = defaultdict(list)
            reachable_from_direct = defaultdict(list)
            reachable_from_start = [False] * N
            reachable_to_end = [False] * N
            reachable_from_start[vertex_start] = True
            reachable_to_end[vertex_end] = True
            reachable_from_both_sides = [False] * N
            dfs_from_start = []
            dfs_to_end = []
            for a, b, c in ABC:
                reachable_to_direct[a].append(b)
                reachable_from_direct[b].append(a)
                if a == vertex_start:
                    dfs_from_start.append(b)
                    reachable_from_start[b] = True
                if b == vertex_end:
                    dfs_to_end.append(a)
                    reachable_to_end[a] = True
            while dfs_from_start:
                v = dfs_from_start.pop()
                for i in reachable_to_direct[v]:
                    if not reachable_from_start[i]:
                        reachable_from_start[i] = True
                        dfs_from_start.append(i)
            while dfs_to_end:
                v = dfs_to_end.pop()
                for i in reachable_from_direct[v]:
                    if not reachable_to_end[i]:
                        reachable_to_end[i] = True
                        dfs_to_end.append(i)
            for i in range(N):
                reachable_from_both_sides[i] = reachable_from_start[i] and reachable_to_end[i]
            return reachable_from_both_sides
        
        reachable_from_both_sides = make_reachable_list(N, M, ABC, vertex_start, vertex_end)
        
        if find_shortest:
            dist = [INF for i in range(N)]
        else:
            dist = [-INF for i in range(N)]
        
        dist[vertex_start] = 0
        for i in range(N):
            updated = False
            for a, b, c in ABC:
                if not reachable_from_both_sides[a]:
                    continue
                elif find_shortest:
                    update_condition = dist[a] + c < dist[b]
                else:
                    update_condition = dist[a] + c > dist[b]
                if dist[a] != INF and update_condition:
                    dist[b] = dist[a] + c
                    updated = True
                    if i == N-1:
                        return value_if_inf
            if not updated:
                break
        return dist[vertex_end]

    
    def warshall_floyd(number_vertex, XYD, shift_one_for_vertex=False):
        
        
        
        
        
        d = [[float("inf")]*number_vertex for i in range(number_vertex)]
        for x, y, dist in XYD:
            if shift_one_for_vertex:
                x = x - 1
                y = y - 1
            d[x][y] = dist
            d[y][x] = dist
        for i in range(number_vertex):
            d[i][i] = 0 
        for k in range(number_vertex):
            for i in range(number_vertex):
                for j in range(number_vertex):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        return d


    """ initialize variables and set inputs
    
        
        
            
            
    
        
        
        
        
        
        
        
    
        
        
        
        
    
        
        
    """

    
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    r_float = lambda: float(r())
    R = lambda: list(map(int, r().split()))
    R_str = lambda: r().split()
    R_map = lambda: map(int, r().split())
    R_float = lambda: list(map(float, r().split()))
    R_tuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    
    
    
    
    
    
    
    """

    
    if sample_file:
        sys.stdin = open(sample_file)
        
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    N = r_int()
    
    A = [300] + R() + [0]
    A_ = []
    B = []
    
    tmp = 400
    for a in A:
        if a != tmp:
            A_.append(a)
        tmp = a
    
    for i in range(1, len(A_)-1):
        if (A_[i-1] - A_[i]) * (A_[i] - A_[i+1]) < 0:
            B.append(A_[i])
    
    ans = 1000
    for i in range(0, len(B), 2):
        ans = (ans//B[i])*B[i+1] + ans%B[i]
    print(ans)

    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    


    
    
    

    """memo: how to use defaultdict of list
    
    Dic = defaultdict(list)
    
    Dic[x].append(y)
    
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    
    >>> a = 5
    >>> bin_str_a = format(a, '
    >>> print(bin_str_a)
    0b0101 
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

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

a=[300]+a+[0] 
money=1000
numStock=0
LAST_UP=1
LAST_DN=2
last_change=LAST_DN

def buy(value):
    global money,numStock
    numStock+=money//value
    money-=numStock*value

def sell(value):
    global money,numStock
    money+=value*numStock
    numStock=0

for i in range(1,n+1):
    if a[i-1]<a[i]:
        last_change=LAST_UP
        if a[i]>a[i+1]: sell(a[i])
    elif a[i-1]>a[i]:
        last_change=LAST_DN
        if a[i]<a[i+1]: buy(a[i])
    else: 
        if a[i]<a[i+1]: 
            if last_change==LAST_DN: buy(a[i])
        elif a[i]>a[i+1]: 
            if last_change==LAST_UP: sell(a[i])

sell(a[n]) 

print(money)

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

money = 1000
stock = 0
for day in range(N):
    if day == N - 1:
        money += stock * A[day]
        stock = 0
    elif A[day] == A[day+1]:
        continue
    elif A[day] < A[day+1]:
        stock += money // A[day]
        money = money % A[day]
    elif A[day] > A[day+1]:
        money += stock * A[day]
        stock = 0

print(money)