Problem:

A: four tea

問題

プログラミングコンテストにはお茶が欠かせない。お茶にはコンテスタントの緊張を和らげる作用があるのだ [要出典]

コンテストに参加する選手が N 人いるので、この人数分のお茶を用意したいと考えている。お茶のパッケージは A, B, C, D の 4 種類あり、どれも同じ品種であるが内容量が異なる。あるパッケージ X について、そのパッケージ 1 つ分の値段は p_X 円であり、1 つ買うと t_X 杯分のお茶を作れることがわかっている。

N 人分のお茶を作るために必要な金額の最小値を求めよ。なお、全く購入しないパッケージがあってもよく、ちょうど N 人分になるようにパッケージを購入する必要もない (N 人分以上作れれば良い)。

入力形式

入力は以下の形式で与えられる。

N
p_A p_B p_C p_D
t_A t_B t_C t_D

1 行目ではコンテストに参加する選手の人数が与えられる。

2 行目では、パッケージ A, B, C, D のお茶の価格が空白区切りで与えられる。

3 行目では、パッケージ A, B, C, D からお茶が何杯作ることができるか空白区切りで与えられる。

制約

1 \leq N \leq 100

1 \leq p_X \leq 100

1 \leq t_X \leq 100

全ての入力は整数として与えられる。

出力形式

N 人分のお茶を作るために必要な金額の最小値を 1 行で出力せよ。

入力例1

10
1 2 3 4
1 2 4 8

出力例1

6

パッケージ B を 1 つ、D を 1 つ買うのが最適である。

入力例2

5
2 9 9 8
1 4 5 100

出力例2

8

必要な量の 20 倍のお茶を用意することになるが、パッケージ D を 1 つ買う場合が最も安く 5 杯以上のお茶を用意できる。

入力例3

24
2 3 4 7
7 9 11 20

出力例3

8

パッケージ A を 2 つと C を 1 つ買うのが最適である。このケースのように人数分のお茶をちょうど作ることが出来ないこともある。



Sample input:
10
1 2 3 4
1 2 4 8


Sample output:
6

Submission status: Accepted

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

dp = [1 << 29] * 10001
dp[0] = 0

for i in range(4):
    for j in range(1, t[i]):
        if dp[j] > P[i]:
            dp[j] = P[i]
    for j in range(t[i], 10001):
        dp[j] = min(dp[j], dp[j - t[i]] + P[i])

print(min(dp[N:]))

Submission status: Accepted

Solution code:
n,pa,pb,pc,pd,ta,tb,tc,td=map(int,open(0).read().split())
r=range(n+1)
m=1e9
for i in r:
    for j in r:
        for k in r:
            l=0--(n-ta*i-tb*j-tc*k)//td
            m=min(m,pa*i+pb*j+pc*k+pd*l*(l>=0))
print(m)

Submission status: Accepted

Solution code:
from math import ceil
N = int(input())
P = tuple(map(int, input().split()))
T = tuple(map(int, input().split()))
ans = 10**10
for i in range(1+ceil(N/T[0])):
    for j in range(1+ceil(N/T[1])):
        for k in range(1+ceil(N/T[2])):
            l = max(0, ceil((N-i*T[0]-j*T[1]-k*T[2])/T[3]))
            ans = min(ans, P[0]*i + P[1]*j + P[2]*k + P[3]*l)
print(ans)

Submission status: Accepted

Solution code:
# from sys import exit

N = int(input())
P = [int(n) for n in input().split()]
t = [int(n) for n in input().split()]
Pt = sorted([(p, t) for p, t in zip(P,t)])

memo = [0 for _ in range(N)]
def rec(n):
    if n >= N:
        return 0
    elif memo[n] != 0:
        return memo[n]
    else:
        memo[n] = min([rec(n+t[i]) + P[i] for i in range(4)])
        return memo[n]
print(rec(0))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



def main():
  N = int(input())
  Pn = list(map(int, input().split()))
  Tn = list(map(int, input().split()))
  dp = [int(10001) for _ in range(N+1)]
  dp[0] = 0

  for i in range(1,N+1):
    for j in range(4):
      if Tn[j] > i:
        dp[i] = min(dp[i],Pn[j])
      else:
        dp[i] = min(dp[i],dp[i-Tn[j]]+Pn[j])
  print(dp[N])

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
N=int(input())
#p=[int(i) for i in input().split()]
#t=[int(i) for i in input().split()]
pa,pb,pc,pd=map(int,input().split())
ta,tb,tc,td=map(int,input().split())
#M=(1+((N-1)//t[0]))*p[0]
M=10**9
ans=M
for a in range(101):
    for b in range(101):
        for c in range(101):
            #t*x>=N
            #d*td=>N-a*ta-b*tb-c*tc
            d=max(0,-((N-a*ta-b*tb-c*tc)//(-td)))
            ans=min(ans,a*pa+b*pb+c*pc+d*pd)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
p = list(map(int, input().split()))
t = list(map(int, input().split()))
res = 100000

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if N < t[0] * i + t[1] * j + t[2] * k:
                if res > p[0]*i + p[1]*j + p[2]*k:
                    res = p[0]*i + p[1]*j + p[2]*k
            else:
                d = (N-t[0]*i-t[1]*j-t[2]*k + t[3] - 1) // t[3]
                if res > p[0]*i + p[1]*j + p[2]*k + p[3]*d:
                    res = p[0]*i + p[1]*j + p[2]*k + p[3]*d
print(res)

Submission status: Accepted

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

ans = 10 ** 10
#aの最大個数
A = max(0, (N + t[0] - 1)// t[0])
for a in range(A+1):
    #aの個数が決まったときのbの最大個数
    B = max(0, (N - a * t[0] + t[1] - 1)//t[1])
    for b in range(B+1):
        #a,bの個数が決まったときのcの最大個数
        C = max(0, (N - a * t[0] - b * t[1] + t[2] - 1)//t[2])
        for c in range(C+1):
            #a,b,cの個数が決まったときのdの個数(残りは全てdとする)
            D = max(0, (N - a * t[0] - b * t[1] - c * t[2] + t[3] - 1)//t[3])
            cost = a * p[0] + b *p[1] + c * p[2] + D * p[3]
            # print (a, b, c, D, cost)
            ans = min(ans, cost)

print (ans)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    p1, p2, p3, p4 = list( map( int, input().split()))
    t1, t2, t3, t4 = list( map( int, input().split()))
    
    ans = 10000
    for i in range(N+1):
        if i*p1 >= ans:
            break
        if i*t1 >= N:
            ans = i*p1
            break
        for j in range(N+1-i):
            if i*p1 + j*p2 >= ans:
                break
            if i*t1 + j*t2 >= N:
                ans = i*p1 + j*p2
                break
            for k in range(N+1-i-j):
                if i*t1 + j*t2 + k*t3 >= N:
                    if i*p1 + j*p2 + k*p3 < ans:
                        ans = i*p1 + j*p2 + k*p3
                    break
                else:
                    g = (N-i*t1-j*t2-k*t3 + t4-1)//t4
                    if i*p1 + j*p2 + k*p3 + g*p4 < ans:
                        ans = i*p1 + j*p2 + k*p3 + g*p4
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

N = int(input())
P = inpl()
T = inpl()

cost = 10**9
for a in range(-(-N//T[0]) + 1):
    costa = P[0]*a
    teaa = T[0]*a
    rema = N - teaa
    for b in range(max(1, -(-rema//T[1]) + 1)):
        costb = P[1] * b
        teab = T[1]*b
        remb = max(rema - teab, 0)
        for c in range(max(1, -(-remb//T[2]) + 1)):
            costc = P[2] * c
            teac = T[2] * c
            remc = max(remb - teac, 0)
            
            d = max(-(-remc//T[3]), 0)
            costd = P[3] * d
            tead = T[3] * d

            cost = min(cost, costa + costb + costc + costd)
print(cost)

Submission status: Accepted

Solution code:
import math
N = int(input())
p = list(map(int,input().split()))
t = list(map(int,input().split()))
ans = [[0]*4 for i in range(4)]
for i in range(4):
    for j in range(4):
        ans[i][j] = (N//t[i])*p[i] + math.ceil((N%t[i])/t[j])*p[j]
ou = min(ans[0])
for i in ans:
    ou = min(ou,min(i))
print(ou)

Submission status: Accepted

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

money = [10**7+9]*(n+1)
money[0] = 0
for price,num in zip(lis1,lis2):
    i = 0
    while(i<n+1):
        if i-num < 0:
            money[i] = min(price,money[i])
        else:
            money[i] = min(money[i],price+money[i-num])
        i += 1
print(money[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template




def main():
    N = ii()
    p = lmi()
    t = lmi()
    n = len(p)
    v = [(i, p[i] / t[i]) for i in range(n)]
    v.sort(key=itemgetter(1))
    m = v[0][0]
    # print(v)
    ans = ceil(N / t[m]) * p[m]
    for i in range(4):
        if i != m:
            # print(ceil((N - t[i]) // t[m]))
            ans = min(ans, ceil((N - t[i]) / t[m]) * p[m] + p[i])
            # print(ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    p = LI()
    t = LI()
    dp = [inf] * (10**5)
    dp[0] = 0
    for i in range(10**5):
        for num,ti in enumerate(t):
            if i - ti >= 0:
                dp[i] = min(dp[i], dp[i - ti] + p[num])
    for i in range(10**5-1, 0, -1):
        dp[i - 1] = min(dp[i], dp[i - 1])
    print(dp[n])
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()

Submission status: Accepted

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

DP=[float("inf")]*(N+1+max(T))
DP[0]=0

for i in range(N+1+max(T)):
    for k in range(4):
        if i-T[k]>=0:
            DP[i]=min(DP[i],DP[i-T[k]]+P[k])

print(min(DP[N:]))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    p = LI()
    t = LI()
    ans = float("inf")
    for i in range(n+1):
        x0 = t[0]*i
        m0 = p[0]*i
        for j in range(n+1):
            x1 = x0+t[1]*j
            m1 = m0+p[1]*j
            for k in range(n+1):
                x2 = x1+t[2]*k
                m2 = m1+p[2]*k
                rest = max(0,math.ceil((n-x2)/t[3]))
                m3 = m2+p[3]*rest
                if m3 < ans:
                    ans = m3
    print(ans)
    return

#B
def B():
    n = I()

    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#Solve
if __name__ == "__main__":
    A()