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: Wrong Answer

Solution code:
N = int(input())
line  = list(map(int, input().split()))
money = 1000
k = line[0]
ln = [line[0]]
for i in range(1,N):
    if line[i] != ln[-1]:
        ln.append(line[i])
#print(ln)
while len(ln) > 1:
    if ln[0] >  ln[1]:
        ln = ln[1:]
    else:
        break
#print(ln)
while len(ln) > 1:
    if ln[-1] < ln[-2]:
        ln = ln[:-2]
    else:
        break
        
st = True        
ln1= [ ]
for i in range(len(ln)-1):
    #print(ln[i] - ln[i+1] <0 == st)
    if (ln[i] - ln[i+1] <0 )== st :
        ln1.append(ln[i])
        st = not st
ln1.append(ln[-1])
#print(ln1)

for i in range(int(len(ln1)/2)):
    money = ln1[2*i +1] * int(money / ln1[2*i]) + (money %ln1[2*i])
    #print(money)
print(money)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

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

money = 1000
stock = 0
status = "wait-for-buying"

last_sell = A.index(max(A))
for i in range(A.index(max(A))):
    if status == "wait-for-buying":
        if A[i] >= A [i+1]:
            pass
        else:
            #buy
            stock = money//A[i]
            money = money%A[i]
            status = "wait-for-selling"
            
    else:
        if A[i] <= A [i+1]:
            pass
        else:
            #sell
            money = stock*A[i]
            stock = 0
            status = "wait-for-buying"

money += stock*max(A)
print(money)

Submission status: Wrong Answer

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

l = []
tmp = []
for i in range(n-1):
    if a[i] < a[i+1] and len(tmp) == 0:
        tmp.append(a[i])
    elif a[i] > a[i+1] and len(tmp) == 1:
        tmp.append(a[i])
        l.append(tmp)
        tmp = []
if a[-2] < a[-1]:
    tmp.append(a[-1])
    l.append(tmp)

res = 1000
for a, b in l:
    res += (res // a) * (b - a)

print(res)

Submission status: Wrong Answer

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

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

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




if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
lis = [0]*n
sw = 0
for i in range(n):
    if i >= 1 and a[i] > a[0]:
        sw = 1
    if i == n-1:
        break
    if a[i] > a[i+1]:
        lis[i] = -1
b = a[::-1]
for i in range(n-1):
    if b[i] < b[i+1]:
        if lis[n-i-1] == -1:
            pass
        else:
            lis[n-i-1] = 1
lis[-1] = -1
if sw == 1:
    lis[0] = 1
m = 1000
k = 0
for i in range(n):
    if lis[i] == 1:
        k += m//a[i]
        m = m%a[i]
    elif lis[i] == -1:
        m += k*a[i]
        k = 0
print(m)

Submission status: Wrong Answer

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

ans = 1000
maxv = 0
minv = a[0]
for i in range(1, n):
    if i < n - 1:
        if a[i] < maxv:
            ans += (maxv - minv) * (ans // minv)
            maxv = a[i]
            minv = a[i]
        else:
            maxv = max(maxv, a[i])
            minv = min(minv, a[i])
    else:
        if a[i] > minv:
            ans += (a[i] - minv) * (ans // minv)

print(ans)

Submission status: Wrong Answer

Solution code:
def function(N, A):
    money = 1000
    kabu = 0
    for i in range(N-1):
        if (i == 0) & (A[0] < A[1]):
            kabu = int(1000/A[0])
            money = 1000-kabu*A[0]
        elif (A[i-1] > A[i]) & (A[i] < A[i+1]):
            kabu = int(money/A[i])
            money = money-kabu*A[0]
        elif (A[i-1] < A[i]) & (A[i] > A[i+1]):
            money = money+kabu*A[i]
            kabu = 0
    return money+kabu*A[N-1]


if __name__ == '__main__':
    N = int(input())
    A = input().split()
    A = [int(a) for a in A]
    print(function(N, A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
h = 0
m = 1000
for i in range(n):
    if i==0 and a[1]>a[0]:
        h1 = m//a[i]
        h += h1
        m -= a[i] * h1
    elif i==n-1:
        m += a[i] * h
        h = 0
    else:
        if a[i] > a[i-1]:
            m += a[i] * h
            h = 0
        elif max(a[i+1::])>a[i] < a[i-1]:
            h1 = m//a[i]
            h += h1
            m -= a[i] * h1

print(m)

Submission status: Wrong Answer

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    b = []

    for i in range(n-1):
        if a[i] < a[i+1]:
            break
    if i < n:
        b.append(a[i])

    pm = 1
    tmp = a[i]
    j = n-1
    for j in range(i+1,n-1):
        if a[j] > pm * a[j+1]:
            b.append(a[j])
            pm *= -1
            tmp = a[j]

    if tmp < a[n-1]:
        b.append(a[n-1])
    ans = 1000
    hand = 0
    for i in range(len(b) // 2):
        x,y = b[2*i], b[2*i+1]
        t = ans // x
        ans -= t * x
        hand += t
        ans += hand * y
        hand = 0

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

dp = [[-1]*n for i in range(100)]
for i in range(1000//a[0]+1):
    dp[i][0] = 1000-a[0]*i

for i in range(1, n):
    for g in range(100):
        for l in range(100):
            if dp[l][i-1] >= 0:
                if l < g:
                    dp[g][i] = max(dp[l][i-1] - a[i]*(g-l), dp[g][i])
                else:
                    dp[g][i] = max(dp[l][i-1] + a[i]*(l-g), dp[g][i])
            else:
                break


ans = 0
for m in range(100):
    ans = max(ans, dp[m][n-1])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
#from scipy import signal


n = int(input())
ajs = input().split()
ajs = [int(aj) for aj in ajs]
ajs = np.array(ajs)

#actions = itertools.product([-1, 0, 1], repeat=n)
#for action in actions:

ajs_delta = ajs[1:] - ajs[:-1]
print(ajs_delta)
for i in range(1, ajs_delta.shape[0]):
  if ajs_delta[i] == 0:
    ajs_delta[i] = ajs_delta[i-1]
    
print(ajs_delta)
  
kyokuchi = {'lower':[], 'upper':[]}
#maxId = signal.argrelmax(ajs)

first_value = 0
for aj_delta in ajs_delta:
  if aj_delta != 0:
    first_value = aj_delta
    break

if ajs_delta[0] > 0:
  kyokuchi['lower'].append(0)
elif ajs_delta[0] < 0:
  kyokuchi['upper'].append(0)
elif ajs_delta[0]  == 0 and first_value > 0:
  kyokuchi['lower'].append(0)

for i in range(0, ajs_delta.shape[0]-1):
  if ajs_delta[i] * ajs_delta[i+1] < 0:
    if ajs_delta[i] > 0:
      kyokuchi['upper'].append(i+1)
    else:
      kyokuchi['lower'].append(i+1)

if ajs_delta[-1] > 0:
  kyokuchi['upper'].append(n-1)
else:
  kyokuchi['lower'].append(n-1)


kyokuchi_s = sorted(kyokuchi['upper'] + kyokuchi['lower'])
  
current_money = 1000
pos = 0

for idx in kyokuchi_s:
  if pos >= 0:#買い
    stock = int(current_money / ajs[idx])
    current_money = current_money % ajs[idx]
    pos = -1
  else:
    current_money += stock * ajs[idx]
    stock = 0
    pos = 1
    
print(current_money)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    m = 1000
    c = 0

    dif = [t1 - t0 for t0,t1 in zip(A[:-1], A[1:])]
    pre = 0
    for d in range(N-1):
        if dif[d] == 0:
            dif[d] = pre
        pre = dif[d]


    if dif[0] > 0:
        c = m // A[0]
        m -= A[0] * c
    for i in range(1,N-1):
        if (dif[i-1] < 0)and(dif[i]>0):
            c = m // A[i]
            m -= A[i] * c
        elif (dif[i-1] > 0)and(dif[i]<0):
            m += A[i] * c
            c = 0
    
    m += A[N-1] * c
    c = 0

    print(m)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
m = 1000
s = 0
flag = "e"
idx = 0
for i in range(N-1):
  if A[i]<A[i+1] and (flag == "d" or flag == "e"):
    s += m//A[i]
    m = m%A[i]
    flag = "u"
  elif A[i]>A[i+1] and (flag == "u" or flag == "e"):
    m += s*A[i]
    s = 0
    idx = i
    flag = "d"
  elif A[i]==A[i+1]:
    flag = "e"
    
m += s*max([A[idx],A[N-1]])

print(m)

Submission status: Wrong Answer

Solution code:
import sys
import heapq, math
from bisect import bisect_right
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

B = [A[0]]

for i in range(1, N):
    if A[i - 1] != A[i]:
        B.append(A[i])

N = len(B)


def solve():
    ret = 1000
    l = 0
    while l < N:
        while l < N - 1 and B[l] > B[l + 1]:
            l += 1

        if l == N - 1:
            return ret

        C = [B[l]]
        while l < N - 1 and B[l] < B[l + 1]:
            C.append(B[l + 1])
            l += 1

        if len(C) % 2 == 1:
            del C[1]

        for i in range(0, len(C), 2):
            cnt = ret // C[i]
            ret -= cnt * C[i]
            ret += cnt * C[i + 1]

        l += 1
    return ret


print(solve())

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

money = 1000
stock = 0

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

    elif a[i] >= a[i+1]:
        money += a[i] * stock
        stock = 0
        continue

    elif a[i] < a[i+1]:
        stock = money // a[i]
        money -= stock * a[i]

print(money)

Submission status: Wrong Answer

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

ans = 1000
buy = A[0]
sell = 0
cnt = 0
flg = False
for i in range(1, N):
    if flg:
        buy = A[i]
        sell = 0
        cnt = 0
        flg = False

    if buy < A[i] and sell < A[i]: #真に大きい時
        if cnt: #株を既に買っていたら
            sell = A[i]
        else:
            cnt = ans//buy #買う株は決まった
            sell = A[i] #売る時の株の値段
    else:
        if sell > 0:
            ans += (sell - buy) * cnt
            flg = True #株を売った
        else: #買う株をできるだけ安いのにしたい
            buy = A[i]

if sell: #最後に売る株が決まったらまだ売ってない
    ans += (sell - buy) * cnt
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=1000
ze=201
cou=0
for i in range(n):
  if a[i]<ze:
    cou+=m//a[i]
    m=m%a[i]
    ze=a[i]
    
  elif a[i]>ze:
    m+=a[i]*cou
    cou=0
    ze=a[i]
  else:
    continue
print(m)

Submission status: Wrong Answer

Solution code:
n, *a = map(int, open(0).read().split())
max_a = max(a)
money = 1000
stock = 0
if a[0] != max_a:
    stock += money // a[0]
    money = money % a[0]
    for i in range(1, n):
        if a[i] < a[i-1]:  # buy
            stock += money // a[i]
            money = money % a[i]
            # print('buy')
        elif a[i] > a[i-1] and (min(a[i:]) != a[i] or i == n-1):  # sell
            money += stock * a[i]
            stock = 0
            # print('sell')
        # print(i, money, stock)
print(money)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
stuck=[0]*N
flag=False
base=A[-1]
for i in range(N):
    money=A[N-i-1]
    if base<money and flag:
        stuck[i]=1
        flag=False
        base=money
    elif base>money and not flag:
        stuck[i]=-1
        flag=True
        base=money
flag=False
stuck=stuck[::-1]
money=1000
kabu=0
for i in range(N):
    if stuck[i]==-1:
        kabu=money//A[i]
        money-=A[i]*kabu
        flag=True
    elif stuck[i]==1:
        money+=A[i]*kabu
        flag=False
if flag:
    money+=A[-1]*kabu
print(money)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import itertools
import array
import textwrap
import math

N = int(input())
A = list(map(int, input().split()))
a = sorted(A, reverse=True)
if a == A:
    print('1000')
    sys.exit()
temp = A[0]
m = 1000
min = A[0]
temp0 = 0
for i in range(N):
    if i < temp0:
        continue
    for k in range(i, N):
        if temp > A[k]:
            min = A[k]
            # print(min)
        if temp < A[k]:
            m = A[k]*(m//min)+(m-(m//min)*min)
            min = A[k]
            temp = A[k]
            # print(m)
            temp0 = k
            break
    # print(i)
print(m)

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
al = list(map(int,input().split()))

al = list(dict.fromkeys(al))
n = len(al)

ans = 0
for v in itertools.product(range(3),repeat=n):
    money = 1000
    kabu = 0

    for i in range(n):
        if v[i] == 0:
            kabu += money // al[i]
            money = money % al[i]
        elif v[i] == 1:
            money += kabu * al[i]
            kabu = 0
        else:
            continue
    ans = max(ans, money)
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
money = 1000
stocks = 0
down = 1
for i in range(n-1):
    # 下がってるけど次上がる→買う
    if down and A[i+1] > A[i]:
        down = -1
        stocks = money // A[i]
        money %= A[i]
        # 最後から二日目なら売る
        if i == n-2:
            money += A[i+1] * stocks
            stoks = 0
    # 上がってるけど次下がる→売る
    elif down == -1 and A[i+1] < A[i]:
        down = 1
        money += A[i] * stocks
        stoks = 0
print(money)

Submission status: Wrong Answer

Solution code:
import math
a = input()
b = input().split(" ")
c = []
for i in b:
  c.append(i)
money = 1000
senet = 0
chk = 0
c.sort(reverse=True)
for i in range(int(a)):
  for j in range(int(a)):
    if j != int(a)-1:
      if b[j] > b[j+1]:
        pass;
      else:
        chk = 1 
  if chk == 0:
    break;
  elif i == int(a)-1:
    if senet != 0:
      money = money + (senet * int(b[i]))
    else:
      pass;
  elif i == 0:
    senet += math.floor(money / int(b[i]))
    money = money-(math.floor(money / int(b[i]))*int(b[i]))
  elif int(b[i]) < int(b[i+1]):
    if int(c[0]) > int(b[i]) and b.index(c[0]) > i:
      senet += math.floor(money / int(b[i]))
      money = money-(math.floor(money / int(b[i]))*int(b[i]))
    else:
      pass
  elif int(b[i]) > int(b[i+1]):
    money += senet * int(b[i])
    senet = 0 
  elif int(b[i]) == int(b[i+1]):
    pass;
print(money)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
K = [0]*N
s = 1000
kab = 0

if A[0] < A[1]:
  K[0] = -1
elif A[0] > A[1]:
  K[0] = 1
for i in range(1, N):
  if A[i-1] < A[i]:
    K[i] = 1 # 1は最高値
    if K[i-1] == 1: 
      K[i-1] == 0
  elif A[i-1] > A[i]:
    K[i] = -1 # -1は最低値
    if K[i-1] == -1:
      K[i-1] == 0
#print(K)
M = list(K)
for i in range(N):
  a = M.pop()
  if a == 1:
    break
  elif (a == -1):
    K[-i] = 0

#print(K)
  
for i in range(N):
  if K[i] == -1:
    kab = s // A[i]
    s -= A[i]*kab
  elif K[i] == 1:
    s += A[i]*kab
    kab = 0
print(s)

Submission status: Wrong Answer

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

real = 1000
unreal = 0

for i in range(n-1):

    if a[i] < a[i+1]:
        unreal, real = divmod(real, a[i])

    elif a[i] > a[i+1]:
        real += (unreal * a[i])
        unreal = 0

    else:
        continue

real += unreal * a[n-1]
print(real)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
start = n-1
for i in range(n-1):
  if a[i]<a[i+1]:
    start = i
    break
#print(start)
money = 1000
kabu = 0
l = [a[start]]
high = 1
for i in range(start+1,n-1):
  if high==1:
    if a[i]<=a[i+1]:
      continue
    else:
      l.append(a[i])
      high = 0
  else:
    if a[i]>=a[i+1]:
      continue
    else:
      l.append(a[i])
      high = 1
if high==1 and a[-2]<a[-1]:
  l.append(a[-1])
if high==0 and a[-2]>a[-1]:
  l.append(a[-1])
#print(l)
if len(l)%2==0:
  for i in range(len(l)):
    if i%2==0:
      kabu += money//l[i]
      money -= (money//l[i])*l[i]
    else:
      money += kabu*l[i]
      kabu = 0
   # print(money,kabu)
  print(money)
else:
  l.pop()
  for i in range(len(l)):
    if i%2==0:
      kabu += money//l[i]
      money -= (money//l[i])*l[i]
    else:
      money += kabu*l[i]
      kabu = 0
    #print(money,kabu)
  print(money)

Submission status: Wrong Answer

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

money = 1000
kabu = 0

kabu_p = la[0]
cheap_p = kabu_p
bef_trend = -1
for a in la[1:]:
    trend = 1 if a > kabu_p else -1

    if bef_trend*trend == -1 and bef_trend == 1:
        kabu = money//cheap_p
        money += kabu*(kabu_p - cheap_p)
        cheap_p = kabu_p
    else:
        cheap_p = min(cheap_p, a)
    kabu_p = a
    bef_trend = trend
print(money)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
l = []
for i in range(n-1):
    if A[i] < A[i+1]:
        l.append(1)
    elif A[i] > A[i+1]:
        l.append(-1)
    else:
        l.append(0)

m = 1000
k = 0

for i in range(n):
    if i != n-1:
        if l[i] == 1: # 株を買う
            k = m//A[i]
            m = m-k*A[i]
        elif l[i] == 0: # なにもしない
            pass
        else: # -1 なので株を売る
            m = m + A[i]*k
            k = 0
    else: #最後に株があれば全部売る
        if k != 0:
            m = m + A[i]*k

print (m)

Submission status: Wrong Answer

Solution code:
n=int(input())
m=list(map(int,input().split()))
a=[]
if m[0]<m[1]:
    a.append([0,-1])
for i in range(1,n-1):
    if m[i]>m[i-1] and m[i]>=m[i+1]:
        a.append([i,1])
    elif m[i]<=m[i-1] and m[i]<m[i+1]:
        a.append([i,-1])
    elif m[i]<m[i-1] and m[i]<=m[i+1]:
        a.append([i,-1])
    elif m[i]<=m[i-1] and m[i]<m[i+1]:
        a.append([i,1])
if m[n-1]>m[n-2]:
    a.append([n-1,1])
#print(a)
k=0
r=1000
t=0
for i in range(len(a)):
    if a[i][1]==-1 and t==0:
        k=r//m[a[i][0]]
        r-=k*m[a[i][0]]
        t=1
    elif a[i][1]==1 and t==1:
        
        
        r+=k*m[a[i][0]]
        k=0
        t=0
        
    #print(k,r)
print(r)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans=1000
kabu=0
flag=0

for i in range(n-1):
    if a[i]<a[i+1]:
        if flag !=1:
            kabu=int(ans/a[i])
            ans-=(kabu*a[i])
            #print(ans,kabu)
        flag=1
        if i==(n-2):
            ans+=(kabu*a[i+1])
    if a[i]>a[i+1]:
        if flag == 1:
            ans+=(kabu*a[i])
            #print(ans)
        flag=-1


print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[0]*N
A=list(map(int,input().split()))
money=1000
money_temp=1000
kazu=0
for i in range(N-1):
    if(A[i]<A[i+1]):
        kazu=money//A[i]
        money_temp=money
        money=money-A[i]*kazu
        #print('ue')
        #print(A[i])
        #print(A[i+1])

    else:
        money_temp=money
        money=money+kazu*A[i]
        kazu=0
        #print('sita')
        #print(A[i])
        #print(A[i+1])

money=money+kazu*A[N-1]

print(money)

Submission status: Wrong Answer

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

ans=1000
i=0
while i<n:
    j=i
    mi=a[i]
    while j<n and mi>=a[j]:
        mi=min(mi,a[j])
        j+=1
    
    if j==n:
        break

    stock=ans//mi
    ans-=stock*mi
    ans+=a[j]*stock
    i=j+1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
l = []
for i in range(n-1):
    if A[i] < A[i+1]:
        l.append(1)
    elif A[i] > A[i+1]:
        l.append(-1)
    else:
        l.append(0)
print (l)

m = 1000
k = 0

for i in range(n):
    if i != n-1:
        if l[i] == 1: # 株を買う
            k = m//A[i]
            m = m-k*A[i]
        elif l[i] == 0: # なにもしない
            pass
        else: # -1 なので株を売る
            m = m + A[i]*k
            k = 0
    else: #最後に株があれば全部売る
        if k != 0:
            m = m + A[i]*k

print (m)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    A.append(-1)

    for money_cand in range(10**5,1000, -1):
        money = money_cand
        stock = 0
        for i in range(N-1, -1, -1):
            if A[i] > A[i+1]:
                stock += money // A[i]
                money = money % A[i]
            elif A[i] < A[i+1]:
                money += stock * A[i]
                stock = 0
        
        else:
            money += stock * A[i]
            if money == 1000:
                print(money_cand)
                return
    
    print("1000")

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import itertools

N = int(input())
AA = list(map(int, input().split()))
GA = itertools.groupby(AA)
A = []
for key, group in GA:
    A.append(key)

d = defaultdict(lambda: 0)
d[0] = 1000

for i in range(len(A)):
    dd = d.copy()
    for s,m in dd.items():
        if m%A[i] != 0:
            temp = m//A[i]
            for j in range(1,temp+1):
                if(d[s+j]<m-j*A[i]):
                    d[s+j]=m-j*A[i]
        else:
            d[s+m//A[i]]=0
        for j in range(1,s+1):
            if(d[s-j]<m+j*A[i]):
                d[s-j]=m+j*A[i]

print(d[0])

Submission status: Wrong Answer

Solution code:
# 全部使え オールオアナッシングや

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

dp = {}


def rec(i, money, stock):
    if (i, money, stock) in dp:
        return dp[(i, money, stock)]
    if i == n:
        return money
    # 有り金全部株に変える
    ret2 = 0
    if money > 0:
        p = money // a[i]
        ret2 = rec(i + 1, money - p * a[i], stock + p)
    # 有り株全部金に変える
    ret3 = 0
    if stock > 0:
        ret3 = rec(i + 1, money + stock * a[i], 0)
    ret = max(money, ret2, ret3)
    dp[(i, money, stock)] = ret
    return ret


print(rec(0, 1000, 0))

Submission status: Wrong Answer

Solution code:
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    C = 1000
    kabu = 0
    buy = []
    sell = []

    for i in range(n - 1, 0, -1):
        if A[i] > A[i - 1]:
            sell.append(i)
            if i == 1:
                buy.append(0)
        elif A[i] < A[i - 1] and len(sell) != 0:
            buy.append(i)

    for i in range(n):
        if i in buy:
            k = C // A[i]
            C -= k * A[i]
            kabu += k
        elif i in sell:
            C += kabu * A[i]
            kabu = 0

    print(C)

resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
c = [0]*n
cash = 1000
stock = 0
#1:底 2:頂点 0:どちらでもない

for i in range(1,n):
    if a[i-1]<a[i]:
        b[i]='+'
    elif a[i-1]>a[i]:
        b[i]='-'
    elif a[i-1]==a[i]:
        b[i]=b[i-1]

if b[1]=='+':
    c[0]=1
elif b[1]=='-':
    c[0]=2

for i in range(1,n-1):
    if b[i]=='+' and b[i+1]=='-':
        c[i]=2
    elif b[i]=='-' and b[i+1]=='+':
        c[i]=1

if b[n-1]=='+':
    c[n-1]=2
elif b[n-1]=='-':
    c[n-1]=1
last = n
ch = 0
for i in range(n):
    if c[n-1-i]==1:
        ch = 1
    elif c[n-1-i]==2 and ch==0:
        break
    elif c[n-1-i]==2 and ch==1:
        last = n-i
        break
    elif ch == 1 and i==n-1:
        last=0
        break

for i in range(last):
    if c[i]==1:
        stock += cash//a[i]
        cash -= cash//a[i]*a[i]
    if c[i]==2:
        cash += stock*a[i]
        stock =0
print(cash)

Submission status: Wrong Answer

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

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


print(b)

Submission status: Wrong Answer

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

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