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 = [int(num) for num in input().split()]

a.insert(0,99999)
a.append(-99999)

money = 1000
stocks = 0

prev_state = "decrease"
next_state = "none"

for i in range(1,len(a)-1):
    # bottom -> buy
    if a[i-1] > a[i]:
        prev_state = "decrease"
    elif a[i-1] < a[i]:
        prev_state = "increase"

    if a[i] > a[i+1]:
        next_state = "decrease"
    elif a[i] < a[i+1]:
        next_state = "increase"
    
    if prev_state == "decrease" and next_state == "increase":
        stocks += money // a[i]
        money %= a[i]
    elif prev_state == "increase" and next_state == "decrease":
        money += a[i]*stocks
        stocks = 0

print(money)

Submission status: Accepted

Solution code:
N = int(input())

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

cnt = 0

M = 1000

min_ind = 0

def kau(M, a, cnt):
    result_cnt = M // a
    result_kingaku = M - (result_cnt * a)
    return result_kingaku, result_cnt
    
def uru(M, a, cnt):
    result_cnt = 0
    result_kingaku = M + a * cnt
    return result_kingaku, result_cnt

operation = "kau"

for i in range(N - 1):
    eval(operation)(M, A[i], cnt)
    
    if operation == "kau":
        if A[i] < A[i + 1]:
            # print(f"day : {i}, M : {M}, cnt : {cnt}, operation : 買う")
            M, cnt = eval(operation)(M, A[i], cnt)
            operation = "uru"
    else:
        if A[i] > A[i + 1]:
            # print(f"day : {i}, M : {M}, cnt : {cnt}, operation : 売る")
            M, cnt = eval(operation)(M, A[i], cnt)
            operation = "kau"
if cnt:
    M, cnt = uru(M, A[-1], cnt)
    # print(f"day : {N-1}, M : {M}, cnt : {cnt}, operation : 売る")
print(M)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
pos = 1000
stock = 0
for i in range(N):
    if i == N - 1:
        pos += stock * A[i]
        stock = 0
    else:
        today = A[i]
        tomorrow = A[i + 1]
        if today < tomorrow:
            stock += pos // today
            pos %= today
        else:
            pos += stock * today
            stock = 0

# 結果出力
print(pos)

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
A = list(map(int, input().split()))
B = [0]*N # 1: top, -1: bottom

inc = 0 # 1: increasing, -1: decreasing
val = A[0]
bot = 0
for i, a in enu(A):
    if i == N-1:
        B[i] = 1
    if inc == 0:
        if val < a:
            B[i-1] = -1
            inc = 1
        elif val == a:
            pass
        else:
            B[i-1] = 1
            inc = -1
    elif inc == 1:
        if val < a:
            pass
        elif val == a:
            pass
        else:
            B[i-1] = 1
            inc = -1
    else:
        if val < a:
            B[i-1] = -1
            inc = 1
        elif val == a:
            pass
        else:
            pass
    val = a

# print(B)
money = 1000
stock = 0
for i, a in enu(A):
    if B[i] == -1:
        # print('buy')
        stock += money//A[i]
        money %= A[i]
    elif B[i] == 1:
        # print('sell')
        money += stock*A[i]
        stock = 0 

print(money)

Submission status: Accepted

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    a = inlt() + [0]
    q = 0
    w = 1000
    for i in range(len(a) - 1):
        if a[i + 1] >= a[i]:
            q = q + (w // a[i])
            w = w - ((w // a[i]) * a[i])
        else:
            w = w + (q * a[i])
            q = 0
    print(w)
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Submission status: Accepted

Solution code:
import math


def _run(n, a_list):
    buy_bool = [False] * n
    sell_bool = [False] * n
    for i in range(n - 1):
        today_low = a_list[i] < a_list[i + 1]
        tomorrow_low = a_list[i + 1] < a_list[i]
        # 今日の方が安いなら今日買う
        buy_bool[i] = today_low
        # 今日の方が高いなら今日売る
        sell_bool[i] = tomorrow_low
    sell_bool[n - 1] = True
    money = 1000
    stock = 0
    for i in range(n):
        if sell_bool[i]:
            money += a_list[i] * stock
            stock = 0
        elif buy_bool[i]:
            buy_stock = money // a_list[i]
            money = money - a_list[i] * buy_stock
            stock += buy_stock
    print(money)


def _main():
    N = int(input())
    A_list = list(map(int, input().split()))
    _run(N, A_list)


if __name__ == "__main__":
    _main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
aa = tuple(map(int, input().split()))

x = {0: 1000}
for i in range(n):
    xx = defaultdict(int)
    for stock, money in x.items():
        xx[0] = max(xx[0], money + stock * aa[i])
        ns = money // aa[i]
        xx[stock + ns] = max(xx[stock + ns], money - ns * aa[i])
    x = xx
print(x[0])

Submission status: Accepted

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

money = 1000
stock = 0

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

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

Submission status: Accepted

Solution code:
def main():
    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
        else:
            stock += money // A[i]
            money = money % A[i]
    money += stock * A[N-1]
    print(money)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
#sort = sorted(a)[::-1] 降順
n = int(input())
a = list(map(int, input().split()))
flag = 0 #0:購入フェーズ　1:売却フェーズ
money = 1000
stock = 0

for k in range(len(a)-1):
    #購入
    if flag == 0:
        if a[k] < a[k+1]:
            stock = int(money / a[k])
            money = money - (a[k] * stock)
            flag = 1

    else:
        if a[k] > a[k+1]:
            money += stock * a[k]
            stock = 0
            flag = 0

k += 1
if flag == 1:
    money += stock * a[k]

print(money)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()


dp = [[0,0] for i in range(n)]

den = [0 for i in range(n)]

for i in range(n-2,-1,-1):
	if a[i] > a[i-1]:
		den[i-1] = 1
	else:
		break

po = [0 for i in range(n)]

for i in range(1,n):
	if a[i] < a[i-1]:
		po[i] = po[i-1]+1
	else:
		po[i] = po[i-1] 

now = a[0]
st = 0
for i in range(n):
	for j in range(i+1,n):
		if a[j] >= a[j-1]:
			1
		else:
			dp[i][0] = j-1
			break
	else:
		dp[i][0] = j
	for j in range(i+1,n):
		if a[j] <= a[j-1]:
			1
		else:
			dp[i][1] = j-1
			break
	else:
		dp[i][1] = j

lb = 0
hav = 0
mo = 1000

for i in range(n):
	if dp[i][0] == i:
		mo += hav * a[i]
		hav = 0
	if dp[i][1] == i:
		hav += mo // a[i]
		mo %= a[i]
		lb = a[i]
print(mo + lb * hav)

Submission status: Accepted

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

dp=[[0,0] for i in range(n)]
b=300
c=0
y=1000
for i in range(0,n-1):
  if a[i]>b:#売る
    j=i+1
    by=0
    while j<n:
      if a[j]<a[i]:
        by=1
        break
      elif a[j]>a[i]:
        break
      j+=1
    if by==1:
      y+=c*a[i]
      c=0
      b=a[i]
  elif a[i]<b and c==0:#買う
    j=i+1
    by=0
    while j<n:
      if a[j]>a[i]:
        by=1
        break
      elif a[j]<a[i]:
        break
      j+=1
  
    if by==1:
      c+=(y//a[i])
      y-=(y//a[i])*a[i]
      
      b=a[i]
print(y+c*a[n-1])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
stock,bill=0,1000
i=0
while i<n:
    if a[i]<=a[i+1]:
        t=i
        while i<n-1 and a[i]<=a[i+1]: i+=1
        temp=bill//a[t]
        stock+=temp
        bill-=temp*a[t]
        if i==n-1:
            bill+=stock*a[n-1]
            print(bill)
            exit()
    elif a[i]>=a[i+1]:
        t=i
        while i<n-1 and a[i]>=a[i+1]: i+=1
        bill+=stock*a[t]
        stock=0
        if i==n-1:
            print(bill)
            exit()

Submission status: Accepted

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

check = ['0']

for i in range(N - 1):
    if data[i] < data[i + 1]:
        check.append("+")
    elif data[i] == data[i + 1]:
        check.append("0")
    else:
        check.append("-")
   
latest_buy = None
for i in range(N - 1):
    price = data[i]
    if check[i + 1] == "+":
        stock += money // price
        money -= price * (money // price)
        latest_buy = i
        
    if check[i + 1] == "-":
        money += price * stock
        stock = 0
        latest_buy = None

if latest_buy != None:
    print(stock * data[latest_buy + 1] + money)
else:
    print(money)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
_A = [0] * (N - 1)
for i in range(len(A) - 1):
    if A[i] < A[i + 1]:
        _A[i] = 1
    elif A[i] > A[i + 1]:
        _A[i] = -1

money = 1000
cnt = 0
flag = 0
for i in range(len(_A)):
    if flag == 0 or flag == -1: #下落中
        if _A[i] == 1: #上がりそう
            cnt += money // A[i]
            money -= (money // A[i]) * A[i] #全部買う
            flag = 1
    elif flag == 0 or flag == 1: #上昇中
        if _A[i] == -1:
            money += cnt * A[i]  # 全部売る
            cnt = 0
            flag = -1
    #print(money)

money += cnt * A[N - 1]  # 全部売る
print(money)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    money = 1000
    have = 0
    for i in range(len(a)-1):
        if a[i] < a[i+1]:
            have += money // a[i]
            money -= a[i] * (money // a[i])
        elif a[i] > a[i+1]:
            money += a[i] * have
            have = 0
    money += have * a[-1]
    print(money)
   
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()

    m = 1000
    up = []
    for i in range(N - 1):
        if A[i] < A[i+1]:
            up.append((A[i], A[i+1]))

    for i in range(len(up)):
        l, h = up[i]
        m = m // l * h + m % l

    print(m)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    N = INT()
    A = LIST()

    # 上昇列に分割する
    s = 0
    curr = A[0]
    money = 1000
    for i in range(1, N):
        # print(i, A[i], money)
        if curr <= A[i]:
            # print("A")
            curr = A[i]
        else:
            # print("B")
            n = money // A[s]   # 個買う
            money -= n*A[s]
            money += curr * n
            s = i
            curr = A[s]
    if curr == A[N-1] and s != N-1:
        n = money // A[s]   # 個買う
        money -= n*A[s]
        money += curr * n
    print(money)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
money = 1000
stock = 0
for i in range(n-1):
    if a_list[i+1] < a_list[i]:
        money += stock*a_list[i]
        stock = 0
    elif a_list[i+1] > a_list[i]:
        new_stock = money//a_list[i]
        money -= new_stock*a_list[i]
        stock += new_stock

print(money+stock*a_list[n-1])

Submission status: Accepted

Solution code:



n = int(input())
a = list(map(int, input().split()))
mny = 1000
stc = 0

sa = set(a)
sizea = len(sa)
ssa = sorted(list(sa))


for i in range(n):
    imj = False
    ilj = False
    for j in range(i+1,n):
        if a[i] < a[j]:
            imj = True
        elif a[i] > a[j]:
            ilj = True
        if imj and ilj:
            break
    
    if mny >= a[i] and imj and a[i] < a[i+1]:
        stc += mny//a[i]
        mny = mny - (a[i] * (mny//a[i]))
    elif ilj and a[i] > a[i+1]:
        mny += stc * a[i]
        stc -= stc


mny += stc * a[len(a)-1]

print(mny)

Submission status: Accepted

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

cache = 1000
kabu = 0
for i in range(n):
    if i == n - 1:
        cache += kabu * a[i]
        kabu = 0
        break

    if cache > a[i] and a[i] < a[i + 1]:
        kabu = cache // a[i]
        cache = cache % a[i]

    if kabu > 0 and a[i] > a[i + 1]:
        cache += kabu * a[i]
        kabu = 0

print(cache)

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
 
money = 1000
stocks = 0
 
for i in range (0, N-1):
    if L[i+1] > L[i]:
        stocks+= money//L[i]
        money = money%L[i]
    elif L[i+1] == L[i]:
        continue
    else:
        money+= stocks*L[i]
        stocks = 0

print(money+stocks*L[-1])

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()

    flag = False
    num, money = 0, 1000
    for i in range(N-1):
        if flag:
            if A[i] > A[i+1]:
                flag = False
                money += num * A[i]
                num -= money // A[i]
        else:
            if A[i] < A[i+1]:
                flag = True
                num += money // A[i]
                money -= num * A[i]

    print(A[-1]*num + money)
            

if __name__ == '__main__':
    main()

Submission status: Accepted

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

money = 1000
stock = 0
day = 0


def buy_all(m, s, price):
    stock_n = m // price
    price_all = price * stock_n
    s += stock_n
    m -= price_all

    return m, s


def sell_all(m, s, price):
    price_all = price * s
    s = 0
    m += price_all

    return m, s


while day < n - 1:
    today, tomorrow = a[day], a[day + 1]

    if today > tomorrow:
        money, stock = sell_all(money, stock, today)
    elif today < tomorrow:
        money, stock = buy_all(money, stock, today)
    else:
        pass

    day += 1

money, stock = sell_all(money, stock, a[-1])

print(money)

Submission status: Accepted

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))

def main():
    n = input_int()
    a_array = input_to_int_tuple()

    money = 1000
    buy = []

    for i, now_val in enumerate(a_array):
        next_val = 0
        if (i + 1) < len(a_array):
            next_val = a_array[i + 1]

        if now_val < next_val:
            cnt = money // now_val
            buy.append((now_val, cnt))
            money = money % now_val

        elif now_val > next_val:
            for val, cnt in buy:
                money += now_val * cnt
            buy = []

    print(money)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
v = []
before = 0
for i in a:
    if i!=before:v.append(i)
    before = i
money = 1000
stack = 0
if len(v) != 1:
    if v[0]<v[1]:
        buy_point = [1]
    else:
        buy_point = [0]
    for i in range(1,len(v)-1):
        if v[i-1]  < v[i] < v[i+1]:
            buy_point.append(2)
        elif v[i-1]  > v[i] > v[i+1]:
            buy_point.append(0)
        elif v[i-1]  < v[i] and v[i] > v[i+1]:
            buy_point.append(-1)
        elif v[i-1]  > v[i] and v[i] < v[i+1]:
            buy_point.append(1)
        else:
            print('error')
    if v[-2] < v[-1]:
        buy_point.append(-1)
    else:
        buy_point.append(0)

    for (i,j) in zip(v,buy_point):
        if j == 1:
            stack += money//i
            money = money%i
        elif j == -1:
            money += stack * i
            stack = 0
        elif j == 2:
            stack += money//i
            money = money%i

print(money)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[12]:


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


# In[20]:


def main():
    mylist = []
    s = 0
    m = 1000
    ans = m
    for i in range(1,N):
        if A[i] > A[i-1]:
            mylist.append(1)
        elif A[i] < A[i-1]:
            mylist.append(-1)
        else:
            mylist.append(0)
    for j,x in enumerate(mylist):
        if x > 0:
            b = m//A[j]
            s += b
            m -= b*A[j]
        elif x < 0:
            m += s*A[j]
            s = 0
        ans = max(ans, m+s*A[j])
    ans = max(ans, m+s*A[-1])
    print(ans)


# In[21]:


if __name__ == '__main__':
    main()


# In[ ]:

Submission status: Accepted

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

money =1000
idx = 0
tmp_id = 0

while(idx < N-1):
    if(A[idx] <= A[idx+1]):
        idx += 1
        if(idx >= N-1):
            min_a = min(A[tmp_id:(idx+1)])
            max_a = max(A[tmp_id:(idx+1)])
            if(min_a == max_a):
                break
            n = money//min_a
            money = money - n*min_a
            money += max_a*n
            break 
    else:
        min_a = min(A[tmp_id:(idx+1)])
        max_a = max(A[tmp_id:(idx+1)])
        
        if(min_a == max_a):
            idx += 1
            tmp_id = idx
            continue
        n = money//min_a
        money = money - n*min_a
        money += max_a*n
        
        tmp = A[idx]
        idx += 1
        tmp_id = idx
print(money)

Submission status: Accepted

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

s = 1000
c = 0
upflg = 0
dwnflg = 0
for i in range(n-1):
  if a[i+1] > a[i]:
    dwnflg = 0
    if upflg == 1:
      continue
    c = s//a[i]
    s -= c*a[i]
    upflg = 1
  elif a[i+1] == a[i]:
    continue
  else:
    upflg = 0
    if dwnflg == 1:
      continue
    s += c*a[i]
    dwnflg = 1
  # print (s)
if upflg == 1:
  s += c*a[-1]
print(max(s,1000))

Submission status: Accepted

Solution code:
#d

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

A = [201] + A + [99]

money = 1000
stock = 0

sell_point = [0]*len(A)
buy_point = [0]*len(A)

position = "buy"

for i in range(len(A)-1):
    if position=="buy":
        if A[i] < A[i+1]:
            buy_point[i] = 1
            position ="sell"
            #print("buy", A[i])
            ba = money//A[i]
            #print("buy_amount", ba)
            money -= ba*A[i]
            stock += ba
            
    elif position=="sell":
        if A[i] > A[i+1]:
            sell_point[i] = 1
            position = "buy"
            #print("sell", A[i])
            sa = stock
            #print("sell_amount", sa)
            money += sa*A[i]
            stock = 0
print(money)

Submission status: Accepted

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

money = 1000
stock = 0

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

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

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    b = [0]*n
    for i in range(n-1):
        if a[i] < a[i+1]:
            b[i] = 1        #次のほうが高い日
        elif a[i] > a[i+1]:
            b[i] = -1       #次のほうが安い日
    c = [0]*n
    if b[0] == 1:
        c[0] = 1
    elif b[0] == -1:
        c[0] = -1
    for i in range(1,n-1):
        if (b[i-1]==0 or b[i-1]==-1) and b[i] == 1:       #もし今日が前と同じか下がってて、次上がるなら
            c[i] = 1       #株を買うべき
        elif (b[i-1]==0 or b[i-1] ==1) and b[i] == -1:  #もし今日が前と同じかあがってて、次さがるなら
            c[i] = -1      #株を売るべき
    kab = 0
    money = 1000
    for i in range(n):
        if c[i] == -1:
            money += kab*a[i]
            kab = 0
        elif c[i] == 1:
            kab += money//a[i]
            money %= a[i]
    money += kab*a[-1]
    print(money)
resolve()

Submission status: Accepted

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

dp = [-1]*N
dp[0] = 1000
dp[1] = 1000
#dp[i] = max(dp[i-2],dp[i-1], (dp[i-2]//A[i-2])*A[i]+dp[i-2]%A[i-2])
for i in range(1,N):
  dp[i] = max(dp[i-1], (dp[i-1]//A[i-1])*A[i]+dp[i-1]%A[i-1])
print(dp[N-1])

Submission status: Accepted

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

dp = [0]*(N+1)
L1 = [[0]*2 for _ in range(N+1)]
L2 = [[0]*2 for _ in range(N+1)]
L1[0][0] = 1000

for i in range(N):
    for j in range(i+1):
        if L1[i+1][0] < L1[j][0]+L1[j][1]*A[i]:
            L1[i+1][0] = L1[j][0]+L1[j][1]*A[i]
            L1[i+1][1] = 0
        if L1[i+1][0] < L2[j][0]+L2[j][1]*A[i]:
            L1[i+1][0] = L2[j][0]+L2[j][1]*A[i]
            L1[i+1][1] = 0
        if L2[i+1][1] < L1[j][1]+L1[j][0]//A[i] or (L2[i+1][1] == L1[j][1]+L1[j][0]//A[i] and L2[i+1][0] < L1[j][0]%A[i]):
            L2[i+1][1] = L1[j][1]+L1[j][0]//A[i]
            L2[i+1][0] = L1[j][0]%A[i]
        if L2[i+1][1] < L2[j][1]+L2[j][0]//A[i] or (L2[i+1][1] == L2[j][1]+L2[j][0]//A[i] and L2[i+1][0] < L2[j][0]%A[i]):
            L2[i+1][1] = L2[j][1]+L2[j][0]//A[i]
            L2[i+1][0] = L2[j][0]%A[i]
    dp[i+1] = max(dp[i], L1[i+1][0]+L1[i+1][1]*A[i], L2[i+1][0]+L2[i+1][1]*A[i])

print(dp[-1])

Submission status: Accepted

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

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

#kane ha
b = 1000

#kabu ha
p = 0
q = 0

for e in a:
    b = max(b,p + q*e)

    q += p//e
    p = p%e

    p2 = b%e
    q2 = b//e

    if q2 > q:
        q = q2
        p = p2
    elif q2 == q:
        p = max(p,p2)

print(b)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))
    money = 1000
    stock = 0

    day = 0

    while day < n - 1:
        if stock == 0:
            cur = a[day]
            buy_day = day
            for i in range(day + 1, n):
                if cur >= a[i]:
                    cur = a[i]
                else:
                    buy_day = i - 1
                    break
            else:
                break
            stock += money // a[buy_day]
            money -= a[buy_day] * stock
            day = buy_day
        else:
            sell_day = 0
            cur = a[day]
            for i in range(day + 1, n):
                if cur <= a[i]:
                    cur = a[i]
                else:
                    sell_day = i - 1
                    break
            else:
                sell_day = n - 1
            money += a[sell_day] * stock
            stock = 0
            day = sell_day

    print(money)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
N=int(input())
alist=list(map(int,input().split()))

a2list=[alist[0]]
for i in range(1,N):
  if a2list[-1]!=alist[i]:
    a2list.append(alist[i])
#print(a2list)

N2=len(a2list)
if N2==1:
  print(1000)
  sys.exit(0)

yama_list=[False]*N2
tani_list=[False]*N2
if a2list[0]>a2list[1]:
  yama_list[0]=True
if a2list[0]<a2list[1]:
  tani_list[0]=True

for i in range(1,N2-1):
  if a2list[i-1]<a2list[i]>a2list[i+1]:
    yama_list[i]=True
  if a2list[i-1]>a2list[i]<a2list[i+1]:
    tani_list[i]=True
    
if a2list[N2-2]<a2list[N2-1]:
  yama_list[N2-1]=True
if a2list[N2-2]>a2list[N2-1]:
  tani_list[N2-1]=True
    
#print(yama_list)
#print(tani_list)

money=1000
kabu=0
for i in range(N2):
  if yama_list[i]:
    #sell all
    money+=a2list[i]*kabu
    kabu=0
  if tani_list[i] and i<N2-1:
    #buy as possible
    k=money//a2list[i]
    kabu+=k
    money-=k*a2list[i]
    
print(money)