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: Runtime Error

Solution code:
money = 1000
stock = 0
leave_max = max(a[1:])

for i in range(n):
    if i == n-1:
        if stock != 0:
            money += a[i] * stock
        break

    leave_max = max(a[i+1:])

    if a[i] >= a[i+1]:
        if stock != 0:
            money += a[i] * stock
            stock = 0

        if a[i] > leave_max:
            break
        else:
            continue

    elif a[i] < a[i+1]:
        num = money // a[i]
        if num != 0:
            stock += num
            money -= stock * a[i]

print(money)

Submission status: Runtime Error

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

max_stock = 10000
dp = [[-1 for i in range(max_stock)] for _ in range(n+1)]
dp[0][0] = 1000

for i in range(n):
    for j in range(max_stock):
        if dp[i][j] >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j]) # do nothing
            dp[i+1][j + dp[i][j] // a[i]] = max(dp[i][j] % a[i], dp[i+1][j + dp[i][j] // a[i]]) # buy stock
            dp[i+1][0] = max(j * a[i] + dp[i][j], dp[i+1][0]) # sell stock
print(dp[n][0])

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
money = 1000
trade = False
num = 0
while num != len(a)-1:
    if a[num] == a[num+1]:
        a.remove(a[num])
    else:
        num += 1
for i in range(len(a)):
    if i == 0:
        a1 = a[i]
        a2 = a[i+1]
        if a1 < a2:
            count = money//a1
            money = money%a1
            trade = True
    elif 0 < i < len(a)-1:
        a1 = a[i-1]
        a2 = a[i]
        a3 = a[i+1]
        if ((a1 > a2) and (a3 > a2) and (trade==False)):
            count = money//a2
            money = money%a2
            trade = True
        elif ((a1 < a2) and (a3 < a2) and (trade==True)):
            money += a2*count
            trade = False
    else:
        if trade:
            if len(a) < 3:
                money += a2*count
            else:
                money += a3*count


print(money)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

# dp[i][j]: i日目にj株持っている時の最大金額
dp = [[-float('inf')] * 301 for i in range(N + 1)]
dp[0][0] = 1000

for i in range(N):
    for j in range(301):
        # 何もしない
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        # 株を買う
        if dp[i][j] > 0:
            for l in range((dp[i][j] // A[i]) + 1):
                dp[i + 1][j + l] = max(dp[i + 1][j + l], dp[i][j + l], dp[i][j] - A[i] * l)
        for b in range(j + 1):
            if 0 <= j - b <= 300:
                dp[i + 1][j - b] = max(dp[i + 1][j - b], dp[i][j - b], dp[i][j] + A[i] * b)
print(dp[N][0])

Submission status: Runtime Error

Solution code:
orz

Submission status: Runtime Error

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

sell = []

for i in range(1, n):
    if a[i - 1] < a[i]:
        sell.append(i)

for i in range(len(sell)):
    if i == 0:
        l = 0
    else:
        l = sell[i - 1] + 1
    r = sell[i] - 1
    stock = ans // min(a[l:r + 1])
    ans += (a[sell[i]] - min(a[l:r + 1])) * stock

print(ans)

Submission status: Runtime Error

Solution code:
if a[n-1] >= a[n-2]:
    peak.append(n-1)
for i in range(1, n-1):
    if a[i] >= a[i-1] and a[i] > a[i+1]:
        peak.append(i)
    if a[i] <= a[i-1] and a[i] < a[i+1]:
        botom.append(i)

for i in range(n):
    if i in botom:
        kabu = money//a[i]
        money %= a[i]
    if i in peak:
        money += kabu*a[i]
        kabu = 0

print(money)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
B=[]
B.append(A[0])
for i in range(1,N):
    if A[i]!=B[-1]: B.append(A[i])
i=1
length=len(B)
while i<length-1:
    if B[i]>B[i-1] and B[i]<B[i+1] or B[i]<B[i-1] and B[i]>B[i+1]:
        B.pop(i)
        length-=1
    else:
        i+=1
yen=1000
kabu=0
for i in range(len(B)):
    if B[0]<B[1]:
        if i%2==0 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        elif i%2==1:
            yen=yen+kabu*B[i]
    else:
        if i%2==1 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        elif i%2==0:
            yen=yen+kabu*B[i]
print(yen)

Submission status: Runtime Error

Solution code:
#D
N=int(input())
A=list(map(int,input().split()))
B=[]

for i in range(N-1):
    if A[i+1]>A[i]:
        B.append(["up",i])
    elif A[i+1]<A[i]:
        B.append(["down",i])
        
C=[]
for i in range(len(B)-1):
    if B[i][0]==B[i+1][0]:
        continue
    C.append(B[i])
C.append(B[-1])

while True:
    if C==[]:
        break
    if C[-1][0]=="down":
        C.pop(-1)
    else:
        break
        
kabu=0
money=1000
if C!=[]:
    if C[0][0]=="up":
        kabu+=money//A[0]
        money%=A[0]
for act in C:
    if act[0]=="up":
        money+=A[act[1]+1]*kabu
        kabu=0
    else:
        kabu+=money//A[act[1]+1]
        money%=A[act[1]+1]
print(money)

Submission status: Runtime Error

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

prices = sorted(list(set(a)),key=a.index)

curentVal = 1000
stockNum = 0

for i in range(len(prices) - 1):
    if prices[i] < prices[i+1]:
        num = curentVal // prices[i]
        curentVal -= prices[i] * num
        stockNum += num
    else:
        num = stockNum
        curentVal += prices[i] * num
        stockNum -= num

num = stockNum
curentVal += prices[i+1] * num
stockNum -= num

print(curentVal)

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
l=list(map(int,input().split()))
maxl=[]
minl=[]
for i in range(n):
    if i==0:
        if l[0]>l[1]:
            maxl.append(0)
        elif l[0]<l[1]:
            minl.append(0)
    elif i==n-1:
        if l[n-2]<l[n-1]:
            maxl.append(n-1)
    else:
        if l[i-1]<l[i] and l[i]>=l[i+1]:
            maxl.append(i)
        elif l[i-1]>l[i] and l[i]<=l[i+1]:
            minl.append(i)

ma=len(maxl)
mi=len(minl)
if ma==0 and mi==0:
    print(1000)
else:
    if ma!=0 and mi!=0 and maxl[0]<minl[0]:
        maxl.remove(maxl[0])
    maxx=deque()
    minn=deque()
    for i in maxl:
        maxx.append(i)
    for i in minl:
        minn.append(i)
    try:
        maa=maxx.popleft()
    except:
        maa=100
    try:
        mii=minn.popleft()
    except:
        mii=100
    money=1000
    while True:
        if maa>mii and maa!=100:
            kabu=money//l[mii]
            money-=l[mii]*kabu
            if minn:
                mii=minn.popleft()
            else:
                mii=100
        elif maa<mii:
            money+=l[maa]*kabu
            kabu=0
            if maxx:
                maa=maxx.popleft()
            else:
                maa=100
        else:
            break   
    print(money)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

# dp[i][j]: i日目にj株持っている時の最大金額
dp = [[-100000] * 301 for i in range(N + 1)]
dp[0][0] = 1000

for i in range(N):
    for j in range(301):
        # 株をl個購入
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if dp[i][j] > 0:
            for l in range(dp[i][j] // A[i] + 1):
                dp[i + 1][j + l] = max(dp[i + 1][j + l], dp[i][j + l], dp[i][j] - A[i] * l)
        for b in range(j + 1):
            if 0 <= j - b <= 300:
                dp[i + 1][j - b] = max(dp[i + 1][j - b], dp[i][j - b], dp[i][j] + A[i] * b)
print(dp[N][0])

Submission status: Runtime Error

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

dp = [[-1]*100000 for i in range(n+1)]

dp[0][0] = 1000

for i in range(n):
    for j in range(100000):
        if dp[i][j] >= 0:
            x = dp[i][j]
            c = x//a[i]
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
            dp[i+1][j+c] = max(dp[i+1][j+c],x-a[i]*c)
            dp[i+1][0] = max(dp[i+1][0],x+a[i]*j)
print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
n = int(input())
a_list = list(map(lambda x: int(x), input().split()))
possesion = 1000
num_stock = 0

for i in range(len(a_list) - 1):
    a_today = a_list[i]
    for a in a_list[i+1:]:
        if a != a_today:
            a_next = a
            break
    
    if a_today < a_next:
        # 買えるだけ買う
        possesion_yesterday = possesion
        possesion = possesion % a_today
        num_stock += possesion_yesterday // a_today
    if a_today > a_next:
        # うれるだけうる
        possesion += num_stock * a_today
        num_stock = 0

# 最終日は買えるだけ買う
possesion += num_stock * a_list[-1]
print(possesion)

Submission status: Runtime Error

Solution code:
def stockBuySell(price, n): 

	if (n == 1): 
		return
	i = 0
	while (i < (n - 1)): 
		while ((i < (n - 1)) and
				(price[i + 1] <= price[i])): 
			i += 1

		if (i == n - 1): 
			break
		quantity = money//price[i]
		money = money//quantity

		while ((i < n) and (price[i] >= price[i - 1])): 
			i += 1
			
		money = quantity*price[i-1]
		quantity = 0
		
		
n = int(input())
price = list(map(int, input().split()))
quantity = 0
money = 1000
stockBuySell(price, n) 
print(money)

Submission status: Runtime Error

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

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

M = 0

while M == 0:
    if len(AS) == 1:
        M = 2
    elif AS[0] >= AS[1]:
        AS.pop(0)
    else:
        M = 1

BS = [AS[0]]
T = AS[0]
B = AS[0]

if M == 2:
    print(1000)
else:
    for i in range(1, len(AS)):
        if i < len(AS)-1:
            if AS[i] > T:
                T = AS[i]
            elif AS[i] < T:
                B = AS[i]
                BS.append(T)
                BS.append(B)
                T = AS[i]
        else:
            if AS[i] > T:
                BS.append(AS[i])
            else:
                BS.pop(len(BS)-1)
    CS = [BS[0], BS[1]]
    for i in range(2, len(BS), 2):
        if BS[i+1] - BS[i] > BS[i-1] - BS[i-2]:
            CS.append(BS[i])
            CS.append(BS[i+1])
    print(CS)
    money = 1000
    kabu = 0
    for i in range(len(CS)):
        if i % 2 == 0:
            kabu = money // CS[i]
            money = money - (kabu * CS[i])
        else:
            money = money + (kabu * CS[i])
            kabu = 0
    print(money)

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
l=list(map(int,input().split()))
maxl=[]
minl=[]
for i in range(n):
    if i==0:
        if l[0]>l[1]:
            maxl.append(0)
        elif l[0]<l[1]:
            minl.append(0)
    elif i==n-1:
        if l[n-2]<l[n-1]:
            maxl.append(n-1)
    else:
        if l[i-1]<l[i] and l[i]>=l[i+1]:
            maxl.append(i)
        elif l[i-1]>l[i] and l[i]<=l[i+1]:
            minl.append(i)

ma=len(maxl)
mi=len(minl)
if ma!=0 and mi!=0 and maxl[0]<minl[0]:
    maxl.remove(maxl[0])
maxx=deque()
minn=deque()
for i in maxl:
    maxx.append(i)
for i in minl:
    minn.append(i)
try:
    maa=maxx.popleft()
except:
    maa=100
try:
    mii=minn.popleft()
except:
    mii=100
money=1000
while True:
    if maa>mii and maa!=100:
        kabu=money//l[mii]
        money-=l[mii]*kabu
        if minn:
            mii=minn.popleft()
        else:
            mii=100
    elif maa<mii:
        money+=l[maa]*kabu
        kabu=0
        if maxx:
            maa=maxx.popleft()
        else:
            maa=100
    else:
        break   
print(money)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

# dp[i][j]: i日目にj株持っている時の最大金額
dp = [[-100000] * 1001 for i in range(N + 1)]
dp[0][0] = 1000

for i in range(N):
    for j in range(1001):
        # 株をl個購入
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if dp[i][j] > 0:
            for l in range(dp[i][j] // A[i] + 1):
                dp[i + 1][j + l] = max(dp[i + 1][j + l], dp[i][j + l], dp[i][j] - A[i] * l)
        for b in range(j + 1):
            if j >= b:
                dp[i + 1][j - b] = max(dp[i + 1][j - b], dp[i][j - b], dp[i][j] + A[i] * b)
print(dp[N][0])

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
tl=[l[0]]
for i in range(1,n):
    if l[i]!=l[i-1] and l[i]!=0:
        tl.append(l[i])


a=[]
ma=False

for i in range(len(tl)):
    if i==0:
        if tl[i]>tl[i+1]:
            ma=True
            a.append(tl[i])
        else:
            ma=False
            a.append(tl[i])
    elif i==len(tl)-1:
        if tl[i]>tl[i-1]:
            a.append(tl[i])
        else:
            a.append(tl[i])
    else:
        if tl[i-1]<tl[i] and tl[i+1]<tl[i]:
            a.append(tl[i])
        elif tl[i-1]>tl[i] and tl[i+1]>tl[i]:
            a.append(tl[i])

if ma:
    a.pop(0)


num=0
ans=1000

for i in range(0,len(a)-1,2):
    
    thing1=(ans//a[i])*a[i+1]
    thing2=num*a[i+1]
    if thing1>thing2:
        ans=thing1+ans%a[i]
        num=0
        
    elif thing2>thing1:
        ans=thing2

print(ans)

Submission status: Runtime Error

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

for i in range(n):
    if a[0]<a[i]:
        up=True
        nin=a[0]
        break
    elif a[0]>a[i]:
        up=False
        break
    if i==n-1:
        print(1000)
        exit()

total=1000

for i in range(1,n-1):
    if up:
        if a[i-1]<=a[i] and a[i]>a[i+1]:
            total+=(total//nin)*(a[i]-nin)
            up=False
    else:
        if a[i-1]>=a[i] and a[i]<a[i+1]:
            nin=a[i]
            up=True
if nin<a[n-1]:
    total+=(total//nin)*(a[n-1]-nin)
print(total)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

# dp[i][j]: i日目にj株持っている時の最大金額
dp = [[-100000] * 501 for i in range(N + 1)]
dp[0][0] = 1000

for i in range(N):
    for j in range(501):
        # 株をl個購入
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if dp[i][j] > 0:
            for l in range(dp[i][j] // A[i] + 1):
                dp[i + 1][j + l] = max(dp[i + 1][j + l], dp[i][j + l], dp[i][j] - A[i] * l)
        for b in range(j + 1):
            if j >= b:
                dp[i + 1][j - b] = max(dp[i + 1][j - b], dp[i][j - b], dp[i][j] + A[i] * b)
print(dp[N][0])

Submission status: Runtime Error

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

m = 1000
k = 0

for i in range(n):
    if A[i] <= m and A[i] == min(A) and i != n-1:
        # 全体で最安なら買い
        k = m//A[i]
        m = m- A[i]*k
    elif A[i] < m and A[i] < max(A[i::]) and i != n-1:
        # 今後、現在の株価より高い株価があれば買い
        k = m//A[i]
        m = m - A[i]*k
    elif 0 < k and A[i] == max(A):
        # 全体で最高なら売り
        m = m + A[i]*k
        k = 0
    elif 0 < k and A[i] != min(A[i::]):
        # 今後、現在の株価より安い株価があれば売り
        m = m + A[i]*k
        k = 0
    elif 0 < k and A[i] == max(A[i::])
        # 今後、現在より高い株価がなければ売り
        m = m + A[i]*k
        k = 0
    else:
        pass

print (m)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
syoji = 1000
kabu = 0
kai = 0
for i in range(N):
  sw = 0
  if kabu == 0 and A[i] < A[i+1] and i < N-1:
    sw = 1
  elif kabu > 0 and kai < A[i]:
    syoji = syoji + kabu*A[i]
    kabu = 0 
  if sw == 1:#zengai
    for num in range (100):
      if syoji < num*A[i]:
        kabu = num-1
        syoji = syoji - (num-1)*A[i]
        kai = A[i]
        break
        
print(syoji)

Submission status: Runtime Error

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

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

M = 0

while M == 0:
    if len(AS) == 1:
        M = 2
    elif AS[0] >= AS[1]:
        AS.pop(0)
    else:
        M = 1

BS = [AS[0]]
T = AS[0]
B = AS[0]

if M == 2:
    print(1000)
else:
    for i in range(1, len(AS)):
        if i < len(AS)-1:
            if AS[i] > T:
                T = AS[i]
            elif AS[i] < T:
                B = AS[i]
                BS.append(T)
                BS.append(B)
                T = AS[i]
        else:
            if AS[i] > T:
                BS.append(AS[i])
    CS = [BS[0], BS[1]]
    for i in range(2, len(BS), 2):
        if BS[i+1] - BS[i] > BS[i-1] - BS[i-2]:
            CS.append(BS[i])
            CS.append(BS[i+1])
    print(CS)
    money = 1000
    kabu = 0
    for i in range(len(CS)):
        if i % 2 == 0:
            kabu = money // CS[i]
            money = money - (kabu * CS[i])
        else:
            money = money + (kabu * CS[i])
            kabu = 0
    print(money)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
B=[]
B.append(A[0])
for i in range(1,N):
    if A[i]!=B[-1]: B.append(A[i])
i=1
length=len(B)
while i<length-1:
    if B[i]>B[i-1] and B[i]<B[i+1] or B[i]<B[i-1] and B[i]>B[i+1]:
        B.pop(i)
        length-=1
    else:
        i+=1
yen=1000
kabu=0
for i in range(len(B)):
    if B[0]<B[1]:
        if i%2==0 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        else:
            yen=yen+kabu*B[i]
    else:
        if i%2==1 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        else:
            yen=yen+kabu*B[i]
print(yen)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
syoji = 1000
kabu = 0
kai = 0
for i in range(N):
  sw = 0
  if kabu == 0 and A[i] < A[i+1] and i < N-1:
    sw = 1
  elif kabu > 0 and kai < A[i]:
    syoji = syoji + kabu*A[i]
    kabu = 0 
  if sw == 1:#zengai
    for num in range (100):
      if syoji < num*A[i]:
        kabu = num-1
        syoji = syoji - (num-1)*A[i]
        kai = A[i]
        break
        
  print(syoji)

Submission status: Runtime Error

Solution code:
def INT():
    return int(input())

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

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

N = INT()
A = LI()
ans = 1000
purchase = 0

for i in range(1, N):
    tmp = ans
    
    if A[i] > A[i - 1]:
        for j in range(10);
            if tmp - A[i - 1] < 0:
                break
            tmp -= A[i - 1]
            purchase += 1
        ans = max(ans, tmp + A[i] * purchase)
        purchase = 0

print(ans)

Submission status: Runtime Error

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

money = 1000
num_item = 0

kakaku = []

# かぶりをなくす
for i in a:
    if len(kakaku) == 0:
        kakaku.append(i)
    else:
        if kakaku[-1] == i:
            pass
        else:
            kakaku.append(i)

dp = []
MAX = 10000
MIN = -1
tmp_min = MAX
tmp_max = MIN

up_flag = False
down_flag = False

if kakaku[0] < kakaku[1]:
    up_flag = True
else:
    down_flag = True

if up_flag:
    dp.append(kakaku[0])

# 減=>増=>減....の形にする
for i in range(1, len(kakaku)):
    # いま増加中or下後中
    if kakaku[i - 1] > kakaku[i]:
        if down_flag:
            pass
        else:
            down_flag=True
            up_flag=False
            dp.append(kakaku[i-1])
        down_flag = True
    else:
        if up_flag:
            pass
        else:
            down_flag = False
            up_flag = True
            dp.append(kakaku[i-1])
        up_flag = True
    # print('up', up_flag, 'down', down_flag, 'now item',kakaku[i], 'dp', dp)

if kakaku[-2] < kakaku[-1]:
    dp.append(kakaku[-1])

for i in range(len(dp)):
    if i % 2 == 0:
        num_item += money // dp[i]
        money -= dp[i] * num_item
    else:
        money += dp[i] * num_item
        num_item = 0

if num_item != 0:
    money += dp[-1] * num_item

print(money)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
minmax=[]
ninli=[]
naxli=[]
nin=a[0]
nax=0

for i in range(n):
    if a[0]<a[i]:
        up=True
        nin=a[0]
        break
    elif a[0]>a[i]:
        up=False
        break

total=1000

for i in range(1,n-1):
    if up:
        if a[i-1]<=a[i] and a[i]>a[i+1]:
            total+=(total//nin)*(a[i]-nin)
            up=False
    else:
        if a[i-1]>=a[i] and a[i]<a[i+1]:
            nin=a[i]
            up=True
if nin<a[n-1]:
    total+=(total//nin)*(a[n-1]-nin)
print(total)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

# dp[i][j]: i日目にj株持っている時の最大金額
dp = [[-100000] * 101 for i in range(N + 1)]
dp[0][0] = 1000

for i in range(N):
    for j in range(101):
        # 株をl個購入
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if dp[i][j] > 0:
            for l in range(dp[i][j] // A[i] + 1):
                dp[i + 1][j + l] = max(dp[i + 1][j + l], dp[i][j + l], dp[i][j] - A[i] * l)
        for b in range(j + 1):
            if j >= b:
                dp[i + 1][j - b] = max(dp[i + 1][j - b], dp[i][j - b], dp[i][j] + A[i] * b)
print(dp[N][0])

Submission status: Runtime Error

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

dictS={}
dictS[0]=1

for n in range (1,N):
    if n<K:
        # S.append(A[n]*S[-1])
        dictS[n]=(A[n]*dictS[n-1])%(10**9+9)

    else:
        # S.append(A[n]*S[-1]/A[n-K])
        dictS[n]=(A[n]*dictS[n-1]/A[n-K])%(10**9+9)

for i in range (K,N):
    if dictS[i]>dictS[i-1]:
        print('Yes')
    else:
        print('No')

Submission status: Runtime Error

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

K = 0
m = 1000

for i in range(N):
    if i == N-1:
        m += K*A[i]
        break
    for k in range(N-i):
        if A[i] < A[i+k+1]:
            if K > 0:
                m += K*A[i]
            K = m//A[i]
            m = m%A[i]
            break
        else:
            if A[i] > A[i+k+1]:
                m += K*A[i]
                K = 0
                break
            else:
                continue
print(m)

Submission status: Runtime Error

Solution code:
n=int(input())
#n,k=map(int,input().split())
v=list(map(int,input().split()))
l=list()
for i in v:
  if i not in l:
    l.append(i)
n=len(l)
d=list()
if l[0]>l[1]:
    d.append(l[0])
if l[0]<l[1]:
    d.append(l[0])
for i in range(1,n-1):
  if l[i-1]<l[i] and l[i+1]<l[i]:
    d.append(l[i])
  if l[i-1]>l[i] and l[i+1]>l[i]:
    d.append(l[i])
if l[-1]>l[-2]:
    d.append(l[-1])
if l[-1]<l[-2]:
    d.append(l[-1])
#print(d)
n=len(d)
p=1000
for i in range(1,n):
  if l[i-1]<l[i]:
    z=(p//l[i-1])*l[i]
    r=p%l[i-1]
    p=z+r
print(p)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, (input().split())))
a.append(0)
mon = 1000
kab = 0
x = 0
z = 0
while z <= n-1:
    if x == 0:
        while a[z+1] < a[z]:
            z += 1
            if z == n-1:
                break
        kab += mon//a[z]
        ans = mon
        mon -= kab*a[z]
        x = 1
        if z < n-1:
            z += 1
        else:
            break
    elif x == 1:
        while a[z+1] > a[z]:
            z += 1
            if z == n-1:
                break
        mon += kab*a[z]
        kab = 0
        x = 0
        if z < n-1:
            z += 1
        else:
            break
print(max(ans, mon))