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:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

a = LIST()

curr = 1000

st = 0

for i in range(1, n):
    if(a[i]>a[i-1]):
        if(curr>0):
            temp = curr//a[i-1]
            st+=temp
            curr-=temp*a[i-1]
    elif(a[i]<a[i-1]):
        if(st>0):
            curr+=st*a[i-1]
            st = 0

if(st>0):
    curr+=st*a[-1]
print(curr)

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N = int(input())
  A = [float('inf')]+list(map(int, input().split()))+[-float('inf')]
  updown = ['']*(N+1)
  updown[0] = 'down'
  for i in range(1,N+1):
    if A[i]>A[i+1]:
      updown[i] = 'down'
    elif A[i]<A[i+1]:
      updown[i] = 'up'
    else:
      updown[i] = updown[i-1]
  stock = 0
  money = 1000
  if 'up' not in updown:
    ind = -1
  else:
    ind = N-updown[::-1].index('up')
  for i in range(N):
    if updown[i]=='up' and updown[i+1]=='down':
      money += A[i+1]*stock
      stock = 0
      if i==ind:
        break
    elif updown[i]=='down' and updown[i+1]=='up':
      stock += money//A[i+1]
      money %= A[i+1]
  return money
print(solve())

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
money = 1000
new_l = []
for i in range(n-1):
    if l[i] != l[i+1]:
        new_l.append(l[i])
new_l.append(l[n-1])
# print(new_l)

for i in range(len(new_l)-1):
    if new_l[i] < new_l[i+1]:
        div = money//new_l[i]
        money += (new_l[i+1]-new_l[i])*div
    # print(div,money)
print(money)

Submission status: Accepted

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

cash=1000
stock=0
for i in range(n):
  if i==n-1:
    if stock!=0:
      cash+=A[i]*stock
      stock=0
    break
  if A[i]==A[i+1]:pass
  elif A[i]<A[i+1]:
    stock+=cash//A[i]
    cash%=A[i]
  else:
    if stock!=0:
      cash+=A[i]*stock
      stock=0
    
print(cash)

Submission status: Accepted

Solution code:
import sys
import copy
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

m = 1000
c = 0
i = 0
while(i < n-1):
    if(c == 0):
        if(a[i] < a[i+1]):
            c = m // a[i]
            m = m % a[i]
    else:
        if(a[i] > a[i+1]):
            m = m + c * a[i]
            c = 0
    i = i+1

if(c != 0):
    m = m + c * a[n-1]

print(m)

Submission status: Accepted

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

m = 1000
s = 0

def buy(p):
  global m, s
  s += m // p
  m = m % p

def sell(p):
  global m, s
  m += s * p
  s = 0

for i in range(n-1):
  cur = a[i]
  nxt = a[i+1]
  if cur < nxt:
    if s == 0:
      buy(cur)
  elif cur > nxt:
    if s > 0:
      sell(cur)
if s > 0:
  sell(a[n-1])
print(m)

Submission status: Accepted

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

genkin = 1000
kabu = 0

for i in range(N-1):
    if A[i] < A[i+1]:
        kabu += genkin // A[i]
        genkin = genkin % A[i]
    if A[i] > A[i+1]:
        genkin += kabu * A[i]
        kabu = 0
    # print(genkin, kabu)

print(genkin + kabu * A[N-1])

Submission status: Accepted

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

money = 1000
kabu = 0

for i in range(N-1):
    if arr[i] < arr[i+1]:
        buy = money//arr[i]
        kabu += buy
        money -= buy*arr[i]

    if arr[i] > arr[i+1]:
        money += kabu*arr[i]
        kabu = 0


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

Submission status: Accepted

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

wallet = 1000
stock = 0

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

wallet += stock * a[n-1]

print(wallet)

Submission status: Accepted

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

dp = [[0]*(200) for i in range(N)]#所持金jの時のi日目の最大株
kabu0 = 1000#株をひとつも持ってない状態での所持金最大

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

for i in range(1,N):
    for j in range(0,200,1):
        dp[i][j]=dp[i-1][j]
    dp[i][kabu0%A[i]]=kabu0//A[i]
    for j in range(0,200,1):
        kabu0 = max(kabu0,A[i]*dp[i-1][j]+j)
    

print(kabu0)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
sign = 1
mountain, valley = [], []
for i in range(N-1):
  if A[i] < A[i+1]:
    valley.append(0)
    break
  elif A[i] > A[i+1]:
    mountain.append(0)
    break
for i in range(N-1):
  if A[i] > A[i+1]:
    if sign == 1:
      mountain.append(i)
      sign = -1
  elif A[i] < A[i+1]:
    if sign == -1:
      valley.append(i)
      sign = 1
for i in range(N-1, 0, -1):
  if A[i-1] < A[i]:
    mountain.append(N-1)
    break
  elif A[i-1] > A[i]:
    valley.append(N-1)
    break
M = 1000
kb = 0
lm, lv = len(mountain), len(valley)
for i in range(lv):
  flg = True
  cnt = i
  while flg:
    if cnt >= lm:
      flg = False
      break
    elif cnt < lm:
      if mountain[cnt] < valley[i]:
        cnt += 1
      else:
        break
  if flg:
    kb += (M // A[valley[i]])
    M -= (M // A[valley[i]]) * A[valley[i]]
    M += kb * A[mountain[cnt]]
    kb = 0
print(M)

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]:
        stock += money//a[i]
        money =money%a[i]
    elif a[i] >a[i+1]:
        money +=stock*a[i]
        stock = 0
 
print(money+stock*a[n-1])

Submission status: Accepted

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

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    tmp = A[0]
    money = 1000

    for a in A:
        if tmp < a:
            c = money // tmp
            money -= tmp * c
            money += c * a
            tmp = a
        else:
            tmp = min(tmp, a)
    print(money)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    inlis = list(map(int, input().split()))
    
    kabu = 0
    tmp = inlis[0]
    shoji = 1000

    for i in range(0, n-1):
        if inlis[i] > tmp:
            shoji += inlis[i] * kabu
            tmp = inlis[i]
            kabu = 0
            #print(i, inlis[i], kabu, shoji)
            if inlis[i+1] > inlis[i]:
                kabu += shoji // inlis[i]
                shoji -= inlis[i] * kabu
                #print(i, inlis[i], kabu, shoji)
        elif inlis[i] <= tmp:
            if inlis[i+1] > inlis[i]:
                kabu += shoji // inlis[i]
                shoji -= inlis[i] * kabu
                tmp = inlis[i]
                #print(i, inlis[i], kabu, shoji)
    if inlis[n-1] > inlis[n-2]:
        shoji += inlis[n-1] * kabu
        kabu = 0
    print(shoji)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Contest No.: M-SOLUTIONS Programming Contest 2020
# Problem No.: D
# Solver:      JEMINI
# Date:        20200725

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))

    money = 1000
    stock = 0
    minVal = nums[0]
    maxVal = nums[0]

    if n == 2:
        if nums[0] < nums[1]:
            money = 1000 - (1000 // nums[0]) * nums[0]
            stock = (1000 // nums[0])

            print(money + stock * nums[1])
        else:
            print(1000)
        return

    upFlag = False
    downFlag = False
    # if nums[0] < nums[1]:
    #     upFlag = True
    
    # elif nums[0] > nums[1]:
    #     downFlag = True
    money = 1000
    stock = 0
    for i in range(n - 1):
        # print(upFlag, downFlag)
        # print(money, stock)
        # local minimum
        if nums[i] < nums[i + 1]:
            if upFlag:
                continue
            else:
                # buy
                tempStock = money // nums[i]
                stock += tempStock
                money -= tempStock * nums[i]
                downFlag = False
                upFlag = True
        # local maximum
        if nums[i] > nums[i + 1]:
            if downFlag:
                continue
            else:
                # sell
                money += stock * nums[i]
                stock = 0
                downFlag = True
                upFlag = False
        # print(upFlag, downFlag)
        # print(money, stock)
    


    if stock:
        money += stock * nums[-1]

    print(money)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

a_pre = A[0]
A_new = [a_pre]
for a in A[1:]:
    if a != a_pre:
        A_new.append(a)
    a_pre = a


minimum = []
maximum = []
N_ = len(A_new)
for i in range(N_):
    max_ = []
    min_ = []
    if i<N_-1:
        s = A_new[i] < A_new[i+1]
        max_.append(not s)
        min_.append(s)
    if i>0:
        s = A_new[i] < A_new[i-1]
        max_.append(not s)
        min_.append(s)
    maximum.append(all(max_))
    minimum.append(all(min_))


stock = False
M = 1000
S = 0
a_pre = None
for max_, min_, a in zip(maximum, minimum, A_new):
    if ~stock and min_:
        S = M // a
        a_pre = a
        stock = True
    if stock and max_:
        M += S * (a-a_pre)
        S = 0

print(M)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化

def main():
    INF = 10**9
    n = int(input())
    A = list(map(int,input().split()))
    B = [0] * n
    for i in range(len(A) - 1):
        B[i + 1] = A[i + 1] - A[i]
    #print(B)
    B.append(-INF)
    C = ['D'] * (n + 1)
    for i in range(1, len(B)):
        if B[i] > 0:
            C[i] = 'U'
        if B[i] == 0:
            C[i] = C[i - 1]
    #print(C)

    money = 1000
    stock = 0

    for i in range(n):
        if C[i] == 'D' and C[i + 1] == 'U':
            stock = money // A[i]
            money = money - (stock * A[i])
        if C[i] == 'U' and C[i + 1] == 'D':
            #売る
            money += stock * A[i]
            stock = 0
    print(money)
    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

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

A_max = max(A)
A_min = min(A)

c = 1000
s = 0
p = 0

for i in range(N - 1):
    # 買い時判定
    if A[i] < A_max and A[i] < A[i + 1]:
        t = c // A[i]
        p = A[i]
        c -= A[i] * t
        s += t
        continue

    # 売り時判定
    if A[i] > A_min and p < A[i] and A[i] > A[i + 1]:
        c += A[i] * s
        s = 0
        p = 0
        continue

# 最終日
c += A[N - 1] * s
s = 0

print(c)

Submission status: Accepted

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

# print(a)

hi = []
for i in range(1, n - 1):
    if a[i - 1] < a[i] and a[i + 1] < a[i]: hi.append(i)
mn = a[0]
p1 = 0
money = 1000
stocks = 0

# print(hi)

for i in hi:
    while p1 < i:
        mn = min(mn, a[p1])
        p1 -= -1
    stocks = money // mn
    money = money % mn
    money += stocks * a[i]
    mn = a[i]
# print(money, stocks)
for i in range(p1 + 1, n):
    mn = min(mn, a[i])
stocks = money // mn
money = money % mn
money += stocks * a[n - 1]

print(money)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
tmp=a[0]
up=0
check=0
stock=0
n=1000
for i in range(N-1):
    if i==0:
        if a[i]<=a[i+1]:
            check=1
            stock=n//a[i]
            n-=stock*a[0]
        else:
            check=2
    else:
        if check==1:
            if a[i]<=a[i+1]:
                pass
            else:
                check=2
                n+=stock*a[i]
                stock=0
        elif check==2:
            if a[i]<=a[i+1]:
                check=1
                stock=n//a[i]
                n-=stock*a[i]
    #print(n,stock,check)
if check==1:
    n+=stock*a[-1]
print(n)

Submission status: Accepted

Solution code:
# coding: utf-8

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

now_kabu = 0
shoji = 1000
for i in range(N-1):
    if A[i+1] > A[i]:
        now_kabu += shoji // A[i]
        shoji -= shoji // A[i] * A[i]
    if now_kabu != 0:
        shoji += A[i+1] * now_kabu
        now_kabu = 0

print(shoji)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))+[0]
baibai = []
kane = 1000
kabu = 0
for i in range(N):
    sa = A[i+1] -A[i]
    if sa == 0:
        baibai.append(0)
    elif sa != abs(sa):
        baibai.append(-1)
    else:
        baibai.append(1)
if 1 in baibai:
    uri = N - (baibai[::-1].index(1))
else:
    uri = -1

for j in range(N):
    if j == uri:
        kane += A[j] * kabu
        print(kane)
        exit()
    elif baibai[j] > 0:
        kabu += (kane//A[j])
        kane -= A[j] * (kane//A[j])
    elif baibai[j] < 0:
        kane += A[j] * kabu
        kabu = 0
        
print(kane)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sin
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
count=0
point=[]
for i in range(n-1):
    if count%2==0 and lis[i+1]-lis[i]>0:
        point.append(lis[i])
        count+=1
    if count%2==1 and lis[i+1]-lis[i]<0:
        point.append(lis[i])
        count+=1
'''if count%2==1 and lis[n-1]-lis[n-2]>=0:
    point.append(lis[n-1])
elif count%2==0 and lis[n-1]-lis[n-2]<=0:
    point.append(lis[n-1])'''
point.append(lis[-1])   
#print(point)
#print(lis[-1])
money=1000
for i in range(len(point)//2):
    x=money//point[2*i]
    y=money%point[2*i]
    money=y+x*point[2*i+1]
print(money)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
input = stdin.readline
#print = stdout.write
n = int(input())
a = list(map(int,input().split()))
yen = 1000
stocks = 0
for i in range(n - 1):
    if a[i]<a[i+1]:
        stocks += yen//a[i]
        yen -= (yen//a[i])*a[i]
    elif a[i]>a[i+1]:
        yen += stocks * a[i]
        stocks = 0
    #print(yen, stocks)
yen += stocks * a[n-1]
print(yen)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
#毎日全売り
#あとに今日より大きいがあるか　ある：買い　ない：やめ
#今日より大きいがくるまでに今日より安いがあるならスルー、ないなら買い

m = 1000
k = 0
flag = False
for i in range(N):

    m += k*A[i]
    k = 0
    low = False
    high = False
    for j in range(i+1, N):
        if A[i] < A[j]:
            high = True
            break
        elif A[i] >= A[j]:
            low = True
    if not low and high:
        k = m // A[i]
        m -= k*A[i]

print(m)

Submission status: Accepted

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

Submission status: Accepted

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

money = 1000
stock = 0

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

print(money)

Submission status: Accepted

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

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

Submission status: Accepted

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

result = 1000
stock = 0

day = 0

dif = []
for i in range(len(a) - 1):
    dif.append(a[i+1]-a[i])

for i in range(len(dif)):
    if dif[i] > 0:
        stock += result // min(a[day:i+1])
        result -= (result // min(a[day:i+1]))*min(a[day:i+1])
        
        result += stock*a[i+1]
        stock = 0
        
        day = i+1
print(result)

Submission status: Accepted

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

for n in range(N-1):
    if A[n] < A[n+1]:
        k = int(m/A[n])
        m -= k*A[n]
        m += k*A[n+1]
        
print(m)

Submission status: Accepted

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

    if bf != f:
        A.append(a[i])

    bf = f
A.append(a[n-1])
m = 1000
c = 0
for i in range(len(A)-1):
    if A[i] < A[i + 1]:
        c = m // A[i]
        m %= A[i]
        if i == len(A) - 2:
            m += c * A[i+1]
            c = 0
    else:
        m += c * A[i]
        c = 0


print(m)

Submission status: Accepted

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

Submission status: Accepted

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

pos = 0 #0ポジなし、1ポジあり
kane = 1000 #所持金
kabu = 0
hi = 0      #現在日

while hi < n:
    if pos == 0:
        if a[hi] < a[hi+1]:
            kabu = kane // a[hi]
            kane = kane % a[hi]
            pos = 1
            hi += 1
        else:
            hi += 1
    else:
        if a[hi] > a[hi+1]:
            kane += a[hi]*kabu
            kabu = 0
            pos = 0
            hi += 1
        else:
            hi += 1

print(kane)

Submission status: Accepted

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

dpMoney = [1000]
dpStock = [(0, 0)]
for A in As:
    money = max([A*s+m for s, m in dpStock])
    m = max(dpMoney)
    s2, m2 = m//A, m%A
    dpMoney.append(money)
    dpStock.append((s2, m2))

print(max(dpMoney))

Submission status: Accepted

Solution code:
n=int(input())
n=1000
a=list(map(int,input().split()))
x=[0]*(len(a)-1)
for i in range(len(a)-1):
    x[i]+=a[i+1]-a[i]

cnt=0

for i in range(len(x)):
    if x[i]>0:
        cnt+=n//a[i]
        n%=a[i]
    elif x[i]==0:
        continue
    elif x[i]<0:
        n+=cnt*a[i]
        cnt=0

n+=cnt*a[-1]

print(n)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力

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

cash = 1000
stock = 0

for i in range(n - 1):
    if stock == 0:
        if all(j < a[i] for j in a[i:]):
            break
        else:
            if a[i] < a[i + 1]:
                stock = int(cash / a[i])
                cash = cash % a[i]

    else:
        if a[i] > a[i + 1]:
            cash += stock * a[i]
            stock = 0

if stock != 0:
    cash += stock * a[n - 1]
    stock = 0
print("{}".format(cash))

Submission status: Accepted

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

# print(up_down)

money = 1000
kabu = 0

for i in range(0, N - 1):
    if up_down[i + 1] == 1:
        can_buy = money // A[i]
        money -= A[i] * (can_buy)
        kabu += can_buy
    elif up_down[i + 1] == -1:
        money += A[i] * kabu
        kabu = 0
    # print(money, kabu)

if kabu > 0:
    money += kabu * A[N - 1]

print(money)

Submission status: Accepted

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

diff = [i < j for i, j in zip(A[0:], A[1:])]

buy = []
sell = []
is_increasing = False
for i, diff_i in enumerate(diff):
    if is_increasing is False and diff_i is True:
        buy.append(i)
    if is_increasing is True and diff_i is False:
        sell.append(i)
    is_increasing = diff_i
else:
    sell.append(N - 1)

money = 1000
stock = 0
for i in range(N):
    if i in buy:
        stock = money // A[i]
        money -= stock * A[i]
    elif i in sell:
        money += stock * A[i]
        stock = 0

print(money)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
d=1
kabu=0
ans=1000
while d<=n-1:
    if a[d]>a[d-1]:
        f=ans//a[d-1]
        kabu+=f
        ans=ans-a[d-1]*f
    if a[d]<a[d-1]:
        ans+=kabu*a[d-1]
        kabu=0
    d+=1
ans+=kabu*a[n-1]
print(ans)

Submission status: Accepted

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

cur = 1000
stock = 0

for ix in range(N-1):
    if A[ix] < A[ix+1]:
        # buy
        stock += cur // A[ix]
        cur %= A[ix]
    else:
        # A[ix] > A[ix+1]
        # sell
        cur += stock * A[ix]
        stock = 0

if stock != 0:
    cur += stock * A[N-1]
    stock = 0

print(cur)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N, *A = map(int, read().split())
    money = 1000
    kabu_no = 0
    status = 0
    for i in range(len(A)-1):
        if A[i]<A[i+1]:
            if status == 1:
                continue
            elif status == 0:
                kabu_no = money // A[i]
                money %= A[i]
                status = 1
        elif A[i]==A[i+1]:
            continue
        else:
            if status == 1:
                money += kabu_no * A[i]
                kabu_no = 0
                status = 0
            elif status == 0:
                continue
    money += kabu_no * A[N-1]
    print(money)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

pos = [1000, 0]

val1 = [lst[0]]

for i in range(1, n):
  if lst[i-1] != lst[i]:
    val1.append(lst[i])

val = []

n = len(val1)
val1.insert(0, 10000)
val1.append(0)

for i in range(1, n+1):
  if val1[i-1] < val1[i] > val1[i+1] or val1[i+1] > val1[i] < val1[i-1]:
    val.append(val1[i])
    

n = len(val)

if val == []:
  print(pos[0])
  exit()
  
for i in range(n):
  if i%2 == 0:
    pos[1] += pos[0]//val[i]
    pos[0] -= pos[1]*val[i]
  
  else:
    pos[0] += pos[1]*val[i]
    pos[1] = 0
    
print(pos[0])

Submission status: Accepted

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

kane=[None]*(N+1)
kabu=[None]*(N+1)
kane[0]=1000
kabu[0]=(0,1000)
for i in range(1,N+1):
    kane[i] = max(kane[i-1],kabu[i-1][0]*A[i-1]+kabu[i-1][1])
    
    cand1 = (kane[i-1]//A[i-1],kane[i-1]%A[i-1])
    if A[i-1]<=kabu[i-1][1]:
        cand2 = (kabu[i-1][0]+1,kabu[i-1][1]-A[i-1])
    else:
        cand2 = (kabu[i-1][0],kabu[i-1][1])
    kabu[i] = max(cand1,cand2)

print(kane[-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
A = list(map(int,input().split()))
sell = [0]*N
buy = [0]*N
hand = [[1000,0] for i in range(N+1)]
for i in range(1,N-1):
    if A[i] >= A[i-1] and A[i] > A[i+1]:
        sell[i] = 1
    if A[i] <= A[i-1] and A[i] < A[i+1]:
        buy[i] = 1
if A[0] < A[1]:
    buy[0] = 1
if A[N-1] > A[N-2]:
    sell[N-1] = 1
for i in range(N-1):
    if buy[i] == 1:
        hand[i+1][0] = hand[i][0] % A[i]
        hand[i+1][1] += hand[i][1] + (hand[i][0] // A[i])
    elif sell[i] == 1:
        hand[i+1][0] = hand[i][0] + A[i]*hand[i][1]
        hand[i+1][1] = 0
    else:
        hand[i+1][0] = hand[i][0]
        hand[i+1][1] = hand[i][1]
if hand[N-1][1] != 0:
    hand[N][0] = hand[N-1][0] + A[N-1]*hand[N-1][1]
else:
    hand[N][0] = hand[N-1][0]
print(hand[N][0])

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
As = np.array(list(map(int, input().split())))
As_diff = np.diff(As)
status = "no"
money = 1000
stock = 0
for i in range(n):
    if status == "no":
        if i == n-1:
            continue
        elif As_diff[i] > 0:
            stock += int(money / As[i])
            money -= As[i]*stock
            status = "yes"
      
    else:
        if i == n-1:
            
            money += As[i] * stock
            stock = 0
    
        elif As_diff[i] < 0:
            
            money += As[i] * stock
            stock = 0
            status = "no"
print(money)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

C = defaultdict(int)
# 売る，買う，何もしないの金額を追う
C[0] = 1000

for i in range(N):
    nc = defaultdict(int)

    for n, c in C.items():
        # 買う
        n0 = n + c // A[i]
        c0 = c - (c // A[i]) * A[i]
        nc[n0] = max(nc[n0], c0)

        # 売る
        c1 = c + n * A[i]
        n1 = 0
        nc[n1] = max(nc[n1], c1)

        # そのまま
        nc[n] = max(c, nc[n])

    C = nc

print(max(C.values()))

Submission status: Accepted

Solution code:
n = int(input())
stock_price = [int(i) for i in input().split()]
stock_num = 0
money = 1000

for i in range(n - 1):
    if stock_price[i] < stock_price[i + 1]:
        num = money // stock_price[i]
        money -= num * stock_price[i]
        stock_num += num
    
    if stock_price[i] > stock_price[i + 1]:
        money += stock_num * stock_price[i]
        stock_num = 0

money += stock_num * stock_price[i + 1]

print(money)

Submission status: Accepted

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

plus_list = []
prev = 0
cum = 0
for i in range(n):
    if prev <= alist[i]:
        cum += 1
    else:
        cum = 0
    prev = alist[i]
    plus_list.append(cum)


stock = 0
money = 1000

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

    if plus_list[i+1] == 0:
        #sell
        money += stock*alist[i]
        stock = 0
    else:
        if stock != 0:
            continue
        #buy
        stock = int(money / alist[i])
        money -= stock*alist[i]

print(money)

Submission status: Accepted

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

ans = 1000
cnt = 0

for i in range(n):
    if a[i] < a[i+1]:
        tmp = ans // a[i]
        cnt += tmp
        ans -= a[i] * tmp
    else:
        ans += a[i] * cnt
        cnt = 0

print(ans)