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:
import sys
readline = sys.stdin.readline

def solve():
    N = int(readline())
    A = list(map(int, readline().split()))

    money = 1000
    stock = 0
    for i in range(N):
        if i == N - 1:
            money += stock * A[i]
        else:
            if A[i + 1] > A[i]:
                inc_stock = money // A[i]
                stock += inc_stock
                money -= inc_stock * A[i]
            else:
                money += stock * A[i]
                stock = 0
    
    print(money)

solve()

Submission status: Accepted

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

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

Submission status: Accepted

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

dp = [[0, 0] for _ in range(n+1)]

dp[0] = [(1000, 0), (1000, 0)]

for i in range(n):
    kabuka = a[i]
    money = max(dp[i][0][0], dp[i][1][0] + kabuka * dp[i][1][1])
    num_kabu = money // kabuka
    num_amari = money % kabuka
    dp[i+1] = [(money, 0), (num_amari, num_kabu)]


print(dp[-1][0][0])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))+[0]
ans = 1000
money = 1000
kabu = 0
for i in range(N):
    if A[i+1] > A[i]:
        hoge = money//A[i]
        money -= hoge*A[i]
        kabu += hoge
    else:
        money += A[i]*kabu
        kabu = 0
        ans = max(money,ans)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mon = 1000
sto = 0
A = list(map(int,input().split()))
for i in range (n):
    if i == n-1:
        mon += sto * A[i]
    elif A[i+1] > A[i]:
        buy = mon//A[i]
        sto += buy
        mon -= buy * A[i]
    elif A[i+1] < A[i]:
        mon += sto * A[i]
        sto = 0
print(mon)

Submission status: Accepted

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

ans = []

is_up = False
is_down = False
for i in range(n):
    if i == 0:
        ans.append(a[i])
        continue
    if is_up:
        if a[i - 1] <= a[i]:
            continue
        else:
            ans.append(a[i - 1])
            is_up = False
            is_down = True
    elif is_down:
        if a[i - 1] >= a[i]:
            continue
        else:
            ans.append(a[i - 1])
            is_up = True
            is_down = False
    else:
        if a[i - 1] < a[i]:
            is_up = True
        elif a[i - 1] > a[i]:
            is_down = True
ans.append(a[-1])

res = 1000
money = 1000
stock = 0
ans.append(-1)

for i in range(len(ans) - 1):
    if ans[i] < ans[i + 1]:
        stock += money // ans[i]
        money -= (money // ans[i]) * ans[i]
    elif ans[i] > ans[i - 1]:
        money += stock * ans[i]
        stock = 0
        res = max(res, money)
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
c = 1000
for i in range(1, n):
    if a[i] > a[i - 1]:
        c = c // a[i - 1] * a[i] + c % a[i - 1]
print(c)

Submission status: Accepted

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#from decimal import Decimal
from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7



n=int(data())
a=mdata()
k=1000
s=0
for i in range(n):
    if i>0 and a[i]>a[i-1]:
        k+=s*a[i]
        s=0
    if i<n-1 and a[i]<a[i+1]:
        s=k//a[i]
        k=k%a[i]
k+=s*a[-1]
out(k)

Submission status: Accepted

Solution code:
n=int(input())
gold=1000
kabu=0
lst=list(map(int,input().split()))
for i in range(n-1):
    if lst[i]<lst[i+1]:
        tmp,gold=divmod(gold,lst[i])
        kabu+=tmp
    if lst[i]>lst[i+1]:
        gold+=kabu*lst[i]
        kabu=0
gold+=kabu*lst[-1]
print(gold)

Submission status: Accepted

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

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

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

yen = 1000
stocks = 0

for i in range(len(A)):
    if i < len(A)-1 and A[i+1] > A[i]:
        # buy
        new_stocks = yen // A[i]
        stocks += new_stocks
        yen -= new_stocks*A[i]
    if i == len(A)-1 or A[i+1] < A[i]:
        # sell
        yen += stocks*A[i]
        stocks = 0

print(yen)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = []
	B.append(A[0])
	for i in range(1, N - 1):
		if A[i - 1] >= A[i] and A[i] >= A[i + 1]:
			pass
		if A[i - 1] <= A[i] and A[i] <= A[i + 1]:
			pass
		else:
			B.append(A[i])

	B.append(A[-1])
	M = len(B)
	# print(B)
	money = 1000
	kabu = 0
	for i in range(M - 1):
		if B[i] < B[i + 1]:
			kabu += int(money // B[i])
			money %= B[i]
		else:
			money += kabu * B[i]
			kabu = 0

	# print(money, kabu)
	money += kabu * B[-1]
	print(money)


if __name__ == '__main__':
	main()

Submission status: Accepted

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

n = readint()
a = readints()


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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    cur=1000
    curk=0
    for i,a in enumerate(A):
        if i==N-1:
            cur+=a*curk
            curk=0
            continue

        if a<=A[i+1]:
            x=cur//a
            curk+=x
            cur-=x*a
        else:
            cur+=a*curk
            curk=0
    print(cur)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
money = 1000
stocks = 0
for i in range(N-1):
    if A[i] < A[i+1]:
        stocks += money//A[i]
        money %= A[i]
    elif A[i] > A[i+1]:
        money += stocks*A[i]
        stocks = 0
print(money+stocks*A[-1])

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
k=0
g=1000
if A[0]<A[1]:
    k=g//A[0]
    g=g%A[0]
for i in range(1,N-1):
    if A[i]>A[i+1]:
        g+=k*A[i]
        k=0
    elif A[i]<A[i+1]:
        k+=g//A[i]
        g=g%A[i]
g+=k*A[-1]
print(g)

Submission status: Accepted

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

money = 1000
stock = 0
for i in range(N):
    if i == 0:
        if As[0] < As[1]:
            stock = money // As[0]
            money %= As[0]
    elif i == N - 1:
        money += As[i] * stock
        stock = 0
    else:
        if As[i-1] >= As[i] and As[i+1] >= As[i]:
            stock += money // As[i]
            money %= As[i]
        elif  As[i-1] <= As[i] and As[i+1] <= As[i]:
            money += As[i] * stock
            stock = 0

print(money)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[a[0]]
f=-1
for i in a:
  if b[-1]<i:
    if f==1:b[-1]=i
    else:
      b.append(i)
      f=1
  if b[-1]>i:
    if f==-1:b[-1]=i
    else:
      b.append(i)
      f=-1
if f==-1:del b[-1]
if len(b)==0:exit(print(1000))
now=1000
for i in range(0,len(b),2):
  bb=now//b[i]
  now-=bb*b[i]
  now+=bb*b[i+1]
print(now)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
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 zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
A = [k for k, g in groupby(A)]
A = [300]+A+[0]
money = 1000
kabu = 0
for i in range(1, len(A)-1):
    if A[i-1] > A[i] < A[i+1]:  # かう
        n = money//A[i]
        money -= A[i]*n
        kabu += n
    if A[i-1] < A[i] > A[i+1]:  # うる
        money += kabu*A[i]
        kabu = 0
print(money)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A += [0]

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

print(money)

Submission status: Accepted

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

Submission status: Accepted

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

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

m=1000

for i in range(n-1):
    if a[i+1]>a[i]:
        k=m//a[i]
        m+=a[i+1]*k-a[i]*k

print(m)

Submission status: Accepted

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

s = 1000
j = 0

for i in range(n-1):
    if a[i] < a[i+1]:
        j += s // a[i]
        s = s % a[i]
    elif a[i] > a[i+1]:
        s += j * a[i]
        j = 0

s += j * a[n-1]
j = 0

print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split())) + [-1]
m = 1000
s = 0
for i in range(N):
    if A[i+1]>A[i]:
        n = m//A[i]
        s += n
        m %= A[i]

    if A[i+1]<A[i]:
        m += s*A[i]
        s = 0

print(m)

Submission status: Accepted

Solution code:
N = int(input())
A_s = list(map(int, input().split()))
is_up = []
for i, A in enumerate(A_s):
    if i == len(A_s)-1:
        break
    if A_s[i+1] >= A_s[i]:
        is_up.append(True)
    else:
        is_up.append(False)
wallet = 1000
stocks = 0
for i, A in enumerate(A_s):
    if i == len(A_s)-1:
        wallet += stocks * A
        stocks = 0
        break
    if is_up[i]:
        stocks += wallet // A
        wallet = wallet % A
    else:
        wallet += stocks * A
        stocks = 0


print(wallet)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = 1000
x = []
tnp = [a[0]]
for i in range(1,n):
    if (a[i-1]>a[i]):
        x.append(tnp)
        tnp = [a[i]]
    else:
        tnp.append(a[i])
x.append(tnp)
#print(x)
ans = 1000
for i in range(len(x)):
    if (len(x[i])>1):
        ans = ans%min(x[i]) + ans//min(x[i])*max(x[i])
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
money = 1000
for i in range(N-1):
    if A[i+1] < A[i] :
        continue
    else:
        money = money//A[i] *A[i+1] + money%A[i]
print(money)

Submission status: Accepted

Solution code:
import sys
# print(sys.version)
N = int(input())

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

P = 1000
K = 0
for i in range(N-1):
    if A[i] < A[i+1]:
        K += P // A[i]
        P %= A[i]
    elif A[i] > A[i+1]:
        P += K*A[i]
        K = 0
P += K * A[-1]
print(P)

Submission status: Accepted

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

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

print(m)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
T = [0]*N
kane = 1000
kabu = 0
for i in range(N-1):
    now = A[i]
    next = A[i+1]
    if now<next:
        ko = kane//now
        kane += -1*ko*now
        kabu += ko
    elif now>next:
        kane += kabu*now
        kabu = 0

kane += kabu*next
print(kane)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()
    res = 1000
    l = -1
    r = -1
    for a in A:
        if l < 0:
            l = a
            continue

        if r < 0:
            if l >= a:
                l = a
            else:
                r = a
        else:
            if r <= a:
                r = a
            else:
                res += (res // l) * (r - l)
                l = a
                r = -1

    if r >= 0:
        res += (res // l) * (r - l)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dp = {0:1000}

for a in A:
    new_dp = defaultdict(lambda: -float('inf'))
    for stock, money in dp.items():
        new_dp[0] = max(new_dp[0], money + stock * a)
        new_dp[stock] = max(new_dp[stock], money)
        can_buy = money // a
        new_dp[stock + can_buy] = max(new_dp[stock+can_buy], money - can_buy * a)
    dp = new_dp
print(max(dp.values()))

Submission status: Accepted

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

now = 1000
prevp = A[0]
stocks = 0

ans = 1000
for i in range(1,N):
  prevp = A[i-1]
  nowp = A[i]
  if stocks == 0 and prevp < nowp:
    stocks = now // prevp
    now = now % prevp
  elif stocks > 0 and prevp > nowp:
    now += prevp * stocks
    stocks = 0
  ans = max(ans, now)
  #print(ans, stocks, now)
  
ans = max(ans, now + A[-1] * stocks)
print(ans)

Submission status: Accepted

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

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

print(money)

Submission status: Accepted

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


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

    cash = 1000
    for i in range(N-1):
        if A[i+1]>=A[i]:
            stock = cash //A[i]
            cash += stock*(A[i+1]-A[i])

    print(cash)







if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import bisect

def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans = 1000
    for i in range(1, n):
        if A[i-1] <= 1000 and A[i] > A[i-1]:
            r = ans % A[i-1]
            ans = ans // A[i-1] * A[i] + r
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int, read().split())

m = 1000
s = 0

for i in range(n):
    if i+1 < n:
        if a[i] < a[i+1]:
            s += m//a[i]
            m %= a[i]
        else:
            m += s*a[i]
            s = 0
    else:
        m += s*a[i]
        s = 0
        
print(m)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
m = 1000

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

print(m)

Submission status: Accepted

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

money = (1000, 0)
stock = (0, 0)

for A in A_list:
	mm = money
	ms = (money[0] % A, money[0] // A)
	sm = (stock[0] + stock[1] * A, 0)
	ss = (stock[0] % A, stock[1] + stock[0] // A)
	
	if mm[0] > sm[0] or (mm[0] == sm[0] and mm[1] > sm[1]):
		money = mm
	else:
		money = sm
	
	if ms[1] > ss[1] or (ms[1] == ss[1] and ms[0] > ss[0]):
		stock = ms
	else:
		stock = ss

print(money[0])

Submission status: Accepted

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

tmp = 0
a_filter = []
idx = 0
while idx < len(a) - 1:
    if a[idx] < a[idx+1]:
        a_filter += [a[idx],a[idx+1]]
    idx+=1

ret = 1000
tmp = 0
for i,x in enumerate(a_filter):
    if i % 2:
        ret += tmp*x
    else:
        tmp = ret // x
        ret -= tmp * x
print(ret)

Submission status: Accepted

Solution code:
# Fast IO (only use in integer input)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

subSeqStart = []
subSeqEnd = []

subSeqStart.append(a[0])

for i in range(N):
    if i == N-1:
        subSeqEnd.append(a[i])
        break
    if a[i] > a[i+1]:
        subSeqEnd.append(a[i])
        subSeqStart.append(a[i+1])

Money = 1000
Stock = 0
for i in range(len(subSeqStart)):
    Stock += Money // subSeqStart[i]
    Money -= Stock * subSeqStart[i]
    Money += Stock * subSeqEnd[i]
    Stock = 0
print(Money)

Submission status: Accepted

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

N = int(readline())
A = [None] + list(map(int, readline().split()))

ans = 1000
dp = [0]*(N+1)
dp[0] = 1000
for i in range(1, 1+N):
    a = A[i]
    res = 1000
    for j in range(1, i):
        res = max(res, dp[j], dp[j] % A[j] + (dp[j]//A[j])*A[i])
    dp[i] = res

print(dp[N])

Submission status: Accepted

Solution code:
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 %= A[i]
  else:
    cash += A[i] * stock
    stock = 0
  #print(cash, stock)

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

Submission status: Accepted

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

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

print(money)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
alst = list(map(int, input().split()))
lst = [[0, [0, 0]] for _ in range(n)]

lst[0][0] = 1000
lst[0][1][0] = 1000 // alst[0]
lst[0][1][1] = 1000 % alst[0]
for i, num in enumerate(alst[1:], start = 1):
    m1 = lst[i - 1][1][1] + lst[i - 1][1][0] * num
    lst[i][0] = max(lst[i - 1][0], m1)
    lst[i][1][0] = lst[i][0] // num
    lst[i][1][1] = lst[i][0] % num
    
print(lst[-1][0])

Submission status: Accepted

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
g = 1000
s = 0
for i in range(1, N):
    if A[i] > A[i-1]:
        t = g // A[i-1]
        g -= t * A[i-1]
        s += t
    else:
        g += s * A[i-1]
        s = 0
print(g + s * A[-1])

Submission status: Accepted

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

B = 1000
for i in range(N-1):
  if A[i+1]>A[i]:
    B = B//A[i]*A[i+1]+B%A[i]
print(B)

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    def simulate(n, L):
        money = 1000
        stock = 0
        for i in range(n-1):
            if L[i+1] == L[i]:
                continue
            elif L[i+1] > L[i]:
                num = money // L[i]
                stock += num
                money -= num * L[i]
            else:
                money += stock * L[i]
                stock = 0
        return money + stock * L[-1]

    
    
    n = ii()
    L = lmi()
    ans = simulate(n, L)
    print(ans)

        


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

money = 1000
for i in range(1, N):
    if As[i] > As[i-1]:
        n = money // As[i-1]
        money = money - (As[i-1] * n) + (As[i] * n)
print(money)