Problem:


Score: 400 points

Problem Statement

To become a millionaire, M-kun has decided to make money by trading in the next N days. Currently, he has 1000 yen and no stocks - only one kind of stock is issued in the country where he lives.

He is famous across the country for his ability to foresee the future. He already knows that the price of one stock in the next N days will be as follows:

A_1 yen on the 1-st day, A_2 yen on the 2-nd day, ..., A_N yen on the N-th day.

In the i-th day, M-kun can make the following trade any number of times (possibly zero), within the amount of money and stocks that he has at the time.

Buy stock: Pay A_i yen and receive one stock.

Sell stock: Sell one stock for A_i yen.

What is the maximum possible amount of money that M-kun can have in the end by trading optimally?

Constraints

2 \leq N \leq 80

100 \leq A_i \leq 200

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the maximum possible amount of money that M-kun can have in the end, as an integer.

Sample Input 1

7
100 130 130 130 115 115 150

Sample Output 1

1685

In this sample input, M-kun has seven days of trading. One way to have 1685 yen in the end is as follows:

Initially, he has 1000 yen and no stocks.

Day 1: Buy 10 stocks for 1000 yen. Now he has 0 yen.

Day 2: Sell 7 stocks for 910 yen. Now he has 910 yen.

Day 3: Sell 3 stocks for 390 yen. Now he has 1300 yen.

Day 4: Do nothing.

Day 5: Buy 1 stock for 115 yen. Now he has 1185 yen.

Day 6: Buy 10 stocks for 1150 yen. Now he has 35 yen.

Day 7: Sell 11 stocks for 1650 yen. Now he has 1685 yen.

There is no way to have 1686 yen or more in the end, so the answer is 1685.

Sample Input 2

6
200 180 160 140 120 100

Sample Output 2

1000

In this sample input, it is optimal to do nothing throughout the six days, after which we will have 1000 yen.

Sample Input 3

2
157 193

Sample Output 3

1216

In this sample input, it is optimal to buy 6 stocks in Day 1 and sell them in Day 2, after which we will have 1216 yen.



Sample input:
7
100 130 130 130 115 115 150


Sample output:
1685

Submission status: Accepted

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

def stockBuySell(price, n): 
    balance = 1000
    # Prices must be given for at least two days 
    if (n == 1): 
        return
      
    # Traverse through given price array 
    i = 0
    while (i < (n - 1)): 
          
        # Find Local Minima 
        # Note that the limit is (n-2) as we are 
        # comparing present element to the next element 
        while ((i < (n - 1)) and 
                (price[i + 1] <= price[i])): 
            i += 1
          
        # If we reached the end, break 
        # as no further solution possible 
        if (i == n - 1): 
            break
          
        # Store the index of minima 
        buy = i 
        i += 1
          
        # Find Local Maxima 
        # Note that the limit is (n-1) as we are 
        # comparing to previous element 
        while ((i < n) and (price[i] >= price[i - 1])): 
            i += 1
              
        # Store the index of maxima 
        sell = i - 1
          
        balance = balance + (balance // price[buy]) * (price[sell] - price[buy])

    return balance
          
print(stockBuySell(a, n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
prices = list(map(int,input().split()))
stock_num = 0
cash = 1000

for i in range(n-1):
    if prices[i+1] >= prices[i]:
        temp = cash // prices[i]
        cash -= prices[i]*temp
        stock_num += temp
    else:
        cash += stock_num*prices[i]
        stock_num = 0

cash += stock_num*prices[n-1]
stock_num = 0

print(cash)

Submission status: Accepted

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

money = 1000
stock = 0

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n = int(input())
a = [int(x) for x in input().split()]

sold_day = set()
buy_day = set()

for i in range(1, n):
    if a[i] > a[i - 1]:
        sold_day.add(i)
        sold_day.discard(i - 1)

money = 1000
stock = 0

sold_day = list(sold_day)
sold_day.sort()

s = 0

for i in sold_day:
    temp = a[s:i]
    min_value = min(temp)
    x = money // min_value
    money -= min_value * x
    money += x * a[i]
    s = i + 1
print(money)

Submission status: Accepted

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

S = 1000

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

Submission status: Accepted

Solution code:
n = int(input())
a = [-1] + list(map(int, input().split()))

# dp[i] = (i+1)日目終了時点での金額の最大値
# dp[i+1] = max(dp[i], {dp[j] % a[k] + (dp[j] // a[k]) * a[l] | j<k<l<=i})
dp = [0] * (n + 1)
dp[0] = dp[1] = 1000
dp[2] = max(dp[0] % a[1] + (dp[0] // a[1]) * a[2], dp[1])

# print(a)
# print(dp)

for i in range(1, n + 1):
    cand = dp[i - 1]
    for j in range(i):
        for k in range(j + 1, i):
            for l in range(k + 1, i + 1):
                cand = max(cand, dp[j] % a[k] + (dp[j] // a[k]) * a[l])
    dp[i] = cand

print(dp[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline


n = int(input())
a = [int(item) for item in input().split()]
prev = a[0]
a_uniq = [a[0]]
for item in a:
    if item == prev:
        continue
    a_uniq.append(item)
    prev = item

if len(a_uniq) == 1:
    print(1000)
    exit()

increasing = None
if a_uniq[0] < a_uniq[1]:
    increasing = True
else:
    increasing = False

money = 1000
kabu = 0
if increasing:
    p = money // a[0]
    money -= p * a[0]
    kabu = p

prev = a_uniq[0]
ans = 1000
for item in a_uniq[1:]:
    if item < prev and increasing:
        money += kabu * prev
        kabu = 0
        increasing = False
        ans = max(ans, money)
    if item > prev and not increasing:
        p = money // prev
        money -= p * prev
        kabu = p
        increasing = True
    prev = item
if kabu:
    money += a_uniq[-1] * kabu
    ans = max(ans, money)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = 1000
dp = [0] * n
for i in range(n):
    if i == 0:
        dp[0] = 1000
        continue
    m = dp[i - 1]
    for j in range(i):
        x = dp[j] // a[j]
        y = dp[j] % a[j]
        z = a[i] * x
        #print(x, y, z)
        m = max(m, y + z)
    dp[i] = m
    #print(dp)
print(dp[n - 1])

Submission status: Accepted

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

A.append(0)

tani=[]
yama=[]

next_buy=True
cur_val=float("inf")
cur_money=1000
cur_stock=0

for a in A:
    if next_buy:
        if a>cur_val:#前の値段で買う
            #print("buy {}".format(cur_val))
            cur_stock=cur_money//cur_val
            cur_money-=cur_stock*cur_val
            cur_val=a
            next_buy=False
        else:
            cur_val=a
    else:#うる
        if a<cur_val:
            #print("sell {}".format(cur_val))
            cur_money+=cur_stock*cur_val
            cur_stock=0
            cur_val=a
            next_buy=True
        else:
            cur_val=a

print(cur_money)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
x = ip()
i = 0
ct = 1000
while i < n-1: 
	while i < (n - 1) and x[i + 1] <= x[i]: 
		i += 1
	if i == n - 1: 
		break
	buy = i 
	i += 1
	while i < n and x[i] >= x[i - 1]: 
		i += 1
	sell = i - 1
	
	no = ct//x[buy]
	profit = no*(x[sell]-x[buy])
	ct += profit
print(ct)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
diff = [A[i+1] - A[i] for i in range(n-1)]
# if slope is upward, buy if possible
# if slope is negative, sell if possible
cash = 1000
stock = 0
for i in range(n-1):
    if diff[i] > 0:
        # buy
        inc_stock = cash //A[i]
        stock += inc_stock
        cash -= inc_stock * A[i]
    else:
        #sell all stock
        cash += stock * A[i]
        stock = 0
cash += stock * A[-1]
print(cash)

Submission status: Accepted

Solution code:
#d
n=int(input())
a=list(map(int,input().split()))
m=1000
kabu=0
t=0
a.insert(0,300)
for i in range(1,n):
    if a[i-1]>=a[i] and a[i]<a[i+1] and t==0:
        kabu=m//a[i]
        m=m%a[i]
        t=1
    elif a[i-1]<=a[i] and a[i]>a[i+1] and t==1:
        m+=kabu*a[i]
        t=0

if t==1:
    m+=kabu*a[n]
print(m)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N = INT()
A = LIST()

up = False
sell = [0] * N
buy = [0] * N
for i in range(N-1):
    if not up and A[i] < A[i+1]:
        up = True
        buy[i] = 1
    if up and A[i] > A[i+1]:
        up = False
        sell[i] = 1
sell[N-1] = 1

money = 1000
stock = 0
for i in range(N):
    if buy[i]:
        d, m = divmod(money, A[i])
        stock += d
        money = m
    if sell[i]:
        money += stock * A[i]
        stock = 0
print(money)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
m = 1000
s = 0
if a[0] < a[1]:
  s = s+m//a[0]
  m = m-(m//a[0])*a[0]
for i in range(N-2):
  if a[i+1] == a[i+2] and a[i+1] == a[i]:
    pass
  elif a[i+1]>=a[i+2] and a[i+1]>=a[i]:
    m = m+s*a[i+1]
    s = 0
  elif a[i+1]<=a[i+2] and a[i+1]<=a[i]:
    s = s+m//a[i+1]
    m = m-(m//a[i+1])*a[i+1]
  else:
    pass
m = m+s*a[-1]
print(m)

Submission status: Accepted

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

money=1000
kabu=0
for i in range(n-1):
    if a[i]<a[i+1]:
        # kau
        if money<a[i]:
            continue
        kabu=money//a[i]
        money=money-kabu*a[i]
    elif a[i]==a[i+1]:
        pass
    else:
        money=money+kabu*a[i]
        kabu=0
    # print(i,money,kabu)

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  kane=1000
  pairs=[]
  i=0
  j=1
  while True:
    if j>=n:
      break
    if l[i]<l[j]:
      pairs.append((i,j))
      i=j
      j=i+1
    elif l[i]==l[j]:
      i=j
      j+=1
    else:
      i=j
      j+=1

  # print(pairs)
  kabu=0
  for x,y in pairs:
    kabu+=kane//l[x]
    kane%=l[x]
    kane+=kabu*l[y]
    kabu=0

  return kane

# main()
print(main())

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    money = 1000
    kab = 0
    cand = [A[0]]
    pre = A[0]
    for i in range(1,N):
        if A[i] < pre:
            cand.append(A[i-1])
            cand.append(A[i])
        pre = A[i]
    if pre <= A[-1]:
        cand.append(A[-1])
    if len(cand) % 2 == 1:
        cand.pop(-1)
    for i in range(len(cand)):
        if i % 2 == 0:
            cnt = money // cand[i]
            kab += cnt
            money -= cand[i] * cnt 
        else:
            money += cand[i] * kab
            kab = 0
    
    print(money)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(money)

Submission status: Accepted

Solution code:
N=int(input())
values=input().split()
for i in range(N):
  values[i]=int(values[i])
day=0
yen=1000
while day<N-1:
  if values[day+1]>values[day]:
    stocksbuyable=yen//values[day]
    yen+=stocksbuyable*(values[day+1]-values[day])
  day+=1
print(yen)

Submission status: Accepted

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

#1300
#35
L=[0]*N
if A[0]<A[1]:
    L[0]=1
    up=1
elif A[0]==A[1]:
    up=0
else:
    up=-1

for i in range(1,N):
    if i==N-1:
        L[i]=-1
        break
    if up==1:
        if A[i]>A[i+1]:
            up=-1
            L[i]=-1
    elif up==0:
        if A[i-1]<A[i]:
            L[i-1]=1
            up=1
        elif A[i-1]>A[i]:
            up=-1

    else:
        if A[i]<A[i+1]:
            up=1
            L[i]=1

#print(L)
now=1000
have=0
for i in range(len(L)):
    l=L[i]
    if l==1:
        have=now//A[i]
        now=now%A[i]
    elif l==-1:
        now+=A[i]*have
        have=0
print(now)

Submission status: Accepted

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

B = [(1000, 0)]

for (i, a) in enumerate(A):
    C = []
    for b1, b2 in B:
        C.append((b1, b2))
        if b1 >= a: C.append((b1 % a, b2 + b1 // a))
        if b2: C.append((b1 + b2 * a, 0))
    C.sort(reverse = True)

    max_rest_A = 0
    if i < N - 1: max_rest_A = max(A[i + 1:])
    
    price = 0
    temp = (0 , 0)
    for c1, c2 in C:
        if price < c1 + c2 * max_rest_A:
            price = c1 + c2 * max_rest_A
            temp = (c1, c2)
    B = [C[0], temp]

answer = 1000
for b1, b2 in B:
    if answer < b1:
        answer = b1
print(answer)

Submission status: Accepted

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


# 次の日の方が安いなら全て売る
# 次の日の方が高いなら全て買う
#　同じなら何もしない
money = 1000
stock=0
for i in range(n-1):
    if a[i] < a[i+1]:
        tmp = money//a[i]
        stock += tmp
        money -= tmp * a[i]
    elif a[i]== a[i+1]:
        pass
    else:
        money += stock *a[i]
        stock =0

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

Submission status: Accepted

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

flag = False
ans = 1000
for i in range(n - 1):
    if a[i] < a[i + 1]:
        flag = True
        break

if flag:
    x = 0
    for i in range(n):
        if x == 0:
            x = ans // a[i]
            ans = ans % a[i]
            #print(ans, x, a[i])

        if i == n - 1 or a[i] > a[i + 1]:
            ans += x * a[i]
            x = 0
print(ans)

Submission status: Accepted

Solution code:
n,*aa = map(int, open(0).read().split())

ans = 1000

mn=mx=aa[0]

for i in range(1,n):
    if mn<=aa[i] and mx<=aa[i]:
        mx = aa[i]
    else:
        ans += (mx-mn)*(ans//mn)
        mn=mx=aa[i]
ans += (mx-mn)*(ans//mn)

print(ans)

Submission status: Accepted

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

money = 1000
kabu = 0
for i in range(N):
    today = A[i]
    if i !=N-1:
        tomorrow = A[i+1]
    else:
        tomorrow = 0
    
    if today < tomorrow:
        buy = money//today#できるだけ買う
        money -= today*buy#買った分引く
        kabu += buy
    elif today > tomorrow:
        money += kabu * today
        kabu = 0

print(money)

Submission status: Accepted

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
A = nn()

A.append(0)

money = 1000
stock = 0

last = N - 1
while A[last] <= A[last-1]:
    last -= 1 

#print(A, last)

for i in range(last):
    if A[i+1] > A[i]:
        stock += money // A[i]
        money = money % A[i]

    if A[i+1] < A[i]:
        money += A[i] * stock
        stock = 0

    #print(i, money, stock)

print(money+A[last]*stock)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
m=1000
k=0
mi=A[0]
ma=A[0]
for i in range(1,N):
    if A[i]>A[i-1]:
        k,m=divmod(m,A[i-1])
        m+=A[i]*k
print(m)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().rstrip().split(" ")))
uru = [0,0]
uruold = [0,1000]
kau = [0,0]
kauold = [1000 // A[0],1000 % A[0]]
for i in range(N):
    if uruold[0] * A[i] + uruold[1] < kauold[0] * A[i] + kauold[1]:
        uru[0] = 0
        uru[1] = kau[0] * A[i] + kau[1]
    else:
        uru = uruold
    if uruold[1] // A[i] + uruold[0] > kauold[1] // A[i] + kauold[0] or (uruold[1] // A[i] + uruold[0] == kauold[1] // A[i] + kauold[0] and uruold[1] % A[i] > kauold[1] % A[i]):
        kau[0] = uruold[1] // A[i] + uruold[0]
        kau[1] = uruold[1] % A[i]
    else:
        kau = kauold
    uruold = uru
    kauold = kau
print(max(uru[1]+ uru[0] * A[N-1],kau[1] + kau[0] * A[N-1]))

Submission status: Accepted

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

Submission status: Accepted

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

c = 1000
s = 0

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

print(c)

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] < A[i + 1]:
        stock, ans = divmod(ans, A[i])
        ans += A[i + 1] * stock
print(ans)

Submission status: Accepted

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

DP = [[[0,0] for i in range(2)] for i in range(N+1)]
DP[0][0][1] = 1000
DP[0][1][1] = 1000
ans = 1000
for i in range(1,N+1):
    if DP[i-1][0][0] < DP[i-1][1][1]//A[i-1]:
        DP[i][0] = [DP[i-1][1][1]//A[i-1],DP[i-1][1][1]%A[i-1]]
    elif DP[i-1][0][0] == DP[i-1][1][1]//A[i-1]:
        DP[i][0] = [DP[i-1][1][1]//A[i-1],max(DP[i-1][0][1],DP[i-1][1][1]%A[i-1])]
    else:
        DP[i][0] = DP[i-1][0]

    if DP[i-1][1][1] < DP[i-1][0][0]*A[i-1]+DP[i-1][0][1]:
        DP[i][1] = [0,DP[i-1][0][0]*A[i-1]+DP[i-1][0][1]]
    else:
        DP[i][1] = DP[i-1][1]

    ans = max(ans,DP[i][1][1])

print(ans)

Submission status: Accepted

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

c=0
money=1000
stock=0


while c<N:
    if c==N-1:  #final
        money+=A[c]*stock
        stock=0
    elif A[c]<A[c+1] and stock==0:  #buy
        stock+=money//A[c]
        money-=A[c]*stock
    elif A[c]>A[c+1]:  #sell
        money+=A[c]*stock
        stock=0
    
    #print(c,money,stock)
    c+=1
    
    
#例外：買わないほうが得
D=sorted(A,reverse=True)
if A==D:
    print(1000)
else:
    print(money)

Submission status: Accepted

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

qnt_cash = 1000
qnt_stock = 0

def buy(cash, stock, price):
  stock += cash // price 
  cash = cash % price
  return cash, stock

def sell(cash, stock, price):
  cash += stock * price
  stock = 0
  return cash, stock


for i in range(N - 1):
  if A[i] < A[i + 1]:
    qnt_cash, qnt_stock = buy(qnt_cash, qnt_stock, A[i])
  elif A[i] > A[i + 1]:
    qnt_cash, qnt_stock = sell(qnt_cash, qnt_stock, A[i])

if qnt_stock > 0:
  qnt_cash, qnt_stock = sell(qnt_cash, qnt_stock, A[N - 1])

print(qnt_cash)

Submission status: Accepted

Solution code:
import sys


def buy(money, stock, price):
    p, q = divmod(money, price)
    stock += p
    money = q
    return money, stock


def sell(money, stock, price):
    money += stock * price
    stock = 0
    return money, stock


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    money = 1000
    stock = 0
    for i in range(n):
        if i == n - 1:
            money, stock = sell(money, stock, a[i])
        else:
            if a[i] < a[i + 1]:
                money, stock = buy(money, stock, a[i])
            elif a[i] > a[i + 1]:
                money, stock = sell(money, stock, a[i])
    print(money)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
X=1000
kabu=0
t=0
_a=A[0]
for a in A:
  if t==0:
    if _a>=a:
      pass
    else:
      kabu=X//_a
      X-=_a*kabu
      t=1
  else:
    if _a<=a:
      pass
    else:
      X+=_a*kabu
      kabu=0
      t=0
  _a=a
if kabu>0:
  X+=A[-1]*kabu
print(X)

Submission status: Accepted

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

N = int(input().rstrip('\n'))
As = [int(x) for x in input().rstrip('\n').split()]
now = 1000
kabu = 0
time = 'buy'
for i in range(N):
  if i < N-1:
    if time =='buy':
      if As[i] < As[i+1]:
        kabu += now // As[i]
        now = now % As[i]
        time = 'sell'
    else:
      if As[i]>As[i+1]:
        now += kabu * As[i]
        kabu = 0
        time = 'buy'
  else:
    now += kabu*As[-1]
print(now)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())

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

r=1000
k=0
for ii in range(n-1):
	if a[ii+1]<a[ii]:
		r+=k*a[ii]
		k=0
	else:
		dk=r//a[ii]
		r-=dk*a[ii]
		k+=dk
	#print(ii,r,k)
print(r+k*a[n-1])

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().split()))

money = 1000
min_price = float("inf")
for i in range(N):
    if min_price > A[i]:
        min_price = A[i]
    elif min_price < A[i]:
        num = money // min_price
        money = money - min_price * num + A[i] * num
        min_price = A[i]

print(money)

Submission status: Accepted

Solution code:
import sys
from math import ceil
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split())) + [0]
    kabu = 0
    money = 1000
    max_money = 1000
    state = 0
    for i in range(N):
        a = A[i]
        if state == 0 and a < A[i + 1]:
            kabu = money // a
            money = money % a
            state = 1
        elif state == 1 and a > A[i + 1]:
            money += kabu * a
            max_money = max(max_money, money)
            kabu = 0
            state = 0
    money += kabu * A[-1]
    max_money = max(max_money, money)
    print(max_money)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

up_streaks = []
i = 1
while i < n:
    if a[i] > a[i-1]:
        # 上がっている
        st = i-1
        en = i
        i+=1
        while i < n:
            if a[i] < a[i-1]:
                break
            else:
                en = i
            i+=1
        up_streaks.append([st, en])
    i+=1

cur = 1000
for st, en in up_streaks:
    cur = cur +  (a[en] - a[st]) * (cur//a[st])
print(cur)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys = sys.stdin.buffer.readline
N = int(input())
A = list(map(int, input().split()))

G = []
for i in range(N - 1):
    if A[i] == A[i + 1]:
        s = 'N'
    elif A[i] < A[i + 1]:
        s = 'U'
    else:
        s = 'D'
    G.append(s)
G = np.array(G)
# print(f'{G=}')

if not np.any(G == 'U'):
    print(1000)
    exit()

money = 1000
kabu = 0
for i in range(N - 1):
    if G[i] == 'N':
        continue
    if G[i] == 'U':
        buy_kabu, nokori_money = divmod(money, A[i])
        kabu += buy_kabu
        money = nokori_money
    else:
        money += kabu * A[i]
        kabu = 0
    # print(f'{money=}, {kabu=}')

money += kabu * A[-1]
kabu = 0
# print(f'{money=}, {kabu=}')
print(money)

Submission status: Accepted

Solution code:
n = int(input()) + 1
a = list(map(int, input().split())) + [0]
money = 1000
stock = 0
greater = [False for i in range(n)]
less = [False for i in range(n)]
buy = [False for i in range(n)]
for i in range(n-1):
    greater[i] = ( a[i] < a[i+1] ) 
    less[i] = a[i] > a[i+1]
    if less[i] and i < n-1:
        buy[i+1] = True
for i in range(n):
    if greater[i]:
        count = money // a[i]
        stock += count
        money -= count * a[i]
    if less[i]:
        count = stock
        stock = 0
        money += count * a[i]
print(money)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
holds = 0
ans = 1000
for i in range(n-1):
    if a[i] <= a[i+1]:
        div, mod = divmod(ans, a[i])
        holds += div
        ans = mod
    else:
        ans += holds * a[i]
        holds = 0

print(ans + holds * a[i+1])

Submission status: Accepted

Solution code:
n = int(input())
data = [int(x) for x in input().split(' ')]

bs = []
for i in range(n):
    if i != n-1:
        if data[i] < data[i+1]:
            bs.append('b')
        else:
            bs.append('s')
    else:
        bs.append('s')

money = 1000
units = 0
for i in range(n):
    if bs[i] == 'b':
        units += money // data[i]
        money = money % data[i]
    else:
        money += data[i] * units
        units = 0

print(money)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
fact = math.factorial
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N = i()
A = l()
num1 = 1000
num2 = 0
F = 0
s = [1000]
for i in range(N-1):
    if A[i] > A[i+1] and F == 1:
        num1 += num2*A[i]
        s.append(num1)
        num2 = 0
        F = 0
    if A[i] < A[i+1] and F == 0:
        num2 = num1 // A[i]
        num1 -= A[i]*(num1//A[i])
        s.append(num1)
        F = 1

    if i+1 == N-1:
        s.append(num1+num2*A[i+1])
print(max(s[-1],s[-2]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
x = 1000
m = a[0]
f = False
for i in range(1,n):
    if a[i]<a[i-1]:
        if f:
            c = x//m
            x %= m
            x += c*a[i-1]
            f = False
            m = a[i]
        else:
            m = a[i]
    else:
        f = True
if f:
    c = x//m
    x %= m
    x += c*a[-1]
    f = False
print(x)

Submission status: Accepted

Solution code:
import sys, math

if(__name__ == "__main__"):
    N = int( input().strip() )
    Alist = list( map(int, input().strip().split() ) )

    i = 0
    bills = 0
    money = 1000
    while(i<N-1):
        while(i<N-1 and Alist[i] >= Alist[i+1]):
            i += 1
        if(i>=N-1):
            break

        bills = money //Alist[i]
        money -= bills * Alist[i]
        while(i<N-1 and Alist[i] < Alist[i+1]):
            i += 1
        money += bills * Alist[i]
        bills = 0
    print(money)

Submission status: Accepted

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

start = [[0, 1000], [0, 1000]]
#0: all stack, 1: all money
max_index = [i for i, v in enumerate(A) if v == max(A)][-1]
#print(max_index)

money_list = []
for i in range(N):
  money = max([
    start[0][0] * A[i] + start[0][1],  start[1][0] * A[i] + start[1][1]
  ])
  money_list.append(money)
  start = [[money//A[i], money - (money//A[i])*A[i] ],  [0, money]]
print(max(money_list))

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==0:
        if a[i]<a[i+1]:
            y=x//a[i]
            x%=a[i]
    elif i==n-1:
        x+=y*a[i]
    else:
        if y>0 and a[i]>a[i+1]:
            x+=y*a[i]
            y=0
        elif y==0 and a[i]<a[i+1]:
            y=x//a[i]
            x%=a[i]
print(x)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
money = 1000
stock = 0

for i in range(N-1):
    #buy
    if A[i] < A[i+1] and money >= A[i]:
        stock = money//A[i]
        money = money % A[i]
    #sell
    if A[i] > A[i+1] and stock != 0:
        money += stock*A[i]
        stock = 0
        

ans = money + stock*A[N-1]       

print(ans)