Problem:


Score : 500 points

Problem Statement

Ibis is fighting with a monster.

The health of the monster is H.

Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.

The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.

Ibis wins when the health of the monster becomes 0 or below.

Find the minimum total Magic Points that have to be consumed before winning.

Constraints

1 \leq H \leq 10^4

1 \leq N \leq 10^3

1 \leq A_i \leq 10^4

1 \leq B_i \leq 10^4

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H N
A_1 B_1
:
A_N B_N

Output

Print the minimum total Magic Points that have to be consumed before winning.

Sample Input 1

9 3
8 3
4 2
2 1

Sample Output 1

4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.

Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.

In this way, we can win at the total cost of 4 Magic Points.

Sample Input 2

100 6
1 1
2 3
3 9
4 27
5 81
6 243

Sample Output 2

100

It is optimal to cast the first spell 100 times.

Sample Input 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

Sample Output 3

139815



Sample input:
9 3
8 3
4 2
2 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 26 21:23:36 2020

@author: H_Hoshigi
"""

def damage_cycle(this_now_H, this_total_M, this_magic_list):
    efficient_magic = this_magic_list[0]
    if now_H >= efficient_magic[0]:
        this_total_M += (now_H // efficient_magic[0]) * efficient_magic[1]
        this_now_H = now_H % efficient_magic[0]
        new_magic_list = this_magic_list
    else:
        new_magic_list = [[0, 1, 0]]
        new_overkill_magic = [0, 1, 0]
        for i in this_magic_list:
            if i[0] <= now_H:
                new_magic_list.append(i)
            elif now_H / i[1] > new_overkill_magic[2]:
                new_overkill_magic = [now_H, i[1], now_H / i[1]]
            else:
                pass
        new_efficient_magic = new_magic_list[0]
        if new_efficient_magic[2] > new_overkill_magic[2]:
            this_total_M += (now_H // new_efficient_magic[0]) * new_efficient_magic[1]
            this_now_H = now_H % new_efficient_magic[0]
        else:
            this_total_M += new_overkill_magic[1]
            this_now_H = 0
            new_magic_list = [new_overkill_magic]
    return this_now_H, this_total_M, new_magic_list


H, N = map(int, input().split())

magic_list = []#[ダメージ量Ai, 魔力消費Bi, 単位魔力当たりのダメージ量]のリスト
for i in range(N):
    A, B = map(int, input().split())
    magic_list.append(
        [A, B, A/B]
        )
#単位魔力当たりのダメージ量でソートする。
magic_list.sort(key = lambda x : x[2], reverse = True)

#現在の残りHPをnow_Hｒとする。
now_H = H
#消費した魔力の総量をtotal_Mとする。
total_M = 0
while now_H > 0:
    now_H, total_M, magic_list = damage_cycle(now_H, total_M, magic_list)
    #print(magic_list)
    #print(total_M)
    #print(now_H)

print(total_M)

Submission status: Wrong Answer

Solution code:
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
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 MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    h,n=MI()
    l=[]
    for i in range(n):
        a,b=MI()
        l.append([a,b])
    dp=[[0 for i in range(h)] for j in range(n+1)]
    for i in range(h):
        dp[n][i]=100000000
    for j in range(n):
        for i in range(h):
            a,b=l[j][0],l[j][1]
            if (i+1)<=a:
                dp[j][i]=b
            else:
                x = (i+1)//a
                r = (i+1)%a
                if r!=0:
                    s = x*b + dp[n][r-1]
                else:
                    s = x*b
                dp[j][i]=s
            if dp[j][i]<dp[n][i]:
                dp[n][i]=dp[j][i]
    print(dp[n][h-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
c = [0]*n # 攻撃力/魔力 コスパ
for i in range(n):
    a[i],b[i] = map(int,input().split())
    c[i] = a[i]/b[i]
# DP　使う魔力がk以下 の時の最大攻撃力で漸化式を立てる
# dp[i] = max(dp[i-a[j]]+b[j]) # i-a[j] >= 0となる全てのa[j]に対して
max_magic = b[0]*((h-1)//a[0]+1)
#print(a,b,c)
c,a,b = zip(*sorted(zip(c,a,b)))
#print(a,b,c)
search_limit = h - (h//a[-1]) * a[-1] #コスパ最大の時のあまり体力
if search_limit == 0:
    print((h//a[-1]) * b[-1])
    exit(0)
dp = [0]*(max_magic+6)
dp[0] = 0
ans = 0
for i in range(1,max_magic+5):
    dp[i] = dp[i-1] #上書きされない時、それ以下の魔力で与えられた攻撃はいける
    for j in range(n):#すべての種類の魔法に対してループ
        if i -b[j] >= 0:#魔法が使えるなら
            dp[i] = max(dp[i],dp[i-b[j]]+a[j])
    #print(i,dp[i])
    if dp[i] >= search_limit:
        ans = i + (h//a[-1]) * b[-1]
        print(ans)
        exit(0)

Submission status: Wrong Answer

Solution code:
INF = 10**8

def main():
    h, n = map(int, input().split())

    a_list = [0] * n
    b_list = [0] * n
    for i in range(n):
        a_list[i], b_list[i] = map(int, input().split())
    a_max = max(a_list)

    # dp = [[0] * (h+1+a_max) for _ in range(n+1)]
    length = h+1+a_max
    dp = [INF] * length
    dp[0] = 0
    ans = 0
    while True:
        for i in range(length):
            if dp[i] == INF:
                continue
            for j in range(n):
                idx = i + a_list[j]
                temp = min(dp[idx], dp[i] + b_list[j])
                dp[idx] = temp
            ans = min(dp[h:])
            if ans == INF:
                pass
            else:
                print(ans)
                return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from operator import attrgetter

class Magic:
    def __init__(self, attack, mp):
        self.attack = attack
        self.mp = mp
        self.ratio = float(attack) / float(mp)
    
    def __repr__(self):
        return "%d, %d, %f" % (self.attack, self.mp, self.ratio)

val = input().split(' ')
h = int(val[0])
n = int(val[1])
magics = []
for i in range(n):
    val = input().split(' ')
    magics.append(Magic(int(val[0]), int(val[1])))

magics = sorted(magics, key=attrgetter('mp'))
magics = sorted(magics, key=attrgetter('ratio'), reverse=True)

counter = 0
for i, magic in enumerate(magics):
    counter += h / magic.attack
    h -= magic.attack * counter
    if h < 0:
        break
    
print(counter)

Submission status: Wrong Answer

Solution code:
import math
def A():
    temp = [int(i) for i in input().split()]
    print(int(math.ceil(temp[0]/temp[1])))

def B():
    temp = [int(i) for i in input().split()]
    H = temp[0]
    N = temp[1]
    A = [int(i) for i in input().split()]
    if H <= sum(A):
        print('Yes')
    else:
        print('No')

def C():
    temp = [int(i) for i in input().split()]
    N = temp[0]
    K = temp[1]
    H = [int(i) for i in input().split()]
    if N <= K:
        print(0)
        return
    H.sort(reverse=True)
    print(sum(H[K:]))

def D():
    H = int(input())
    factor = 0
    ans = 0
    while True:
        ans += 2**factor
        if H == 1:
            break
        H = math.floor(H/2)
        factor += 1
    print(ans)

from collections import defaultdict
def E():
    temp = [int(i) for i in input().split()]
    H = temp[0]
    N = temp[1]
    magic = []
    for i in range(N):
        magic.append(tuple([int(i) for i in input().split()]))
    magic.sort(key = lambda x: x[1])
    attack = [k for k, v in magic]
    cost = [v for k,v in magic]

    min_cost = [[0 for i in range(H+1+max(attack))] for j in range(N+1)] 
    
    for i in range(H+1+max(attack)): 
        min_cost[0][i] = float('inf')
  
    for i in range(1, N+1): 
        min_cost[i][0] = 0

    for i in range(1, N+1): 
        for j in range(1, H+1+max(attack)): 

            if (attack[i-1] > j): 
                min_cost[i][j] = min_cost[i-1][j] 
  
            else: 
                min_cost[i][j] = min(min_cost[i-1][j], 
                    min_cost[i][j-attack[i-1]] + cost[i-1]) 
    
    #print(min_cost)
    if(min_cost[N][H] == float('inf')): 
        i = 1
        while H+i < H+1+min(attack):
            if min_cost[N][H+i] < float('inf'):
                print(min_cost[N][H+i])
                return
    else: 
        print(min_cost[N][H])

E()

Submission status: Wrong Answer

Solution code:
H, N = input().split()
H = int(H)
N = int(N)
a = []
b = []
con = 1
while con <= N:
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)
    con += 1

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

    
cost=10**4
base=0
a=[]
b=[]
bet=H

for i in range(N):
    b.append(AB[i][0])
    #print(AB[i][0]/AB[i][1])
    if AB[i][0]/AB[i][1]>cost:
        cost=AB[i][0]/AB[i][1]
        base=i
    else:
        pass
#print(base)
a.append(AB[base][1]*(-(-H//AB[base][0])))
    
for k in range(1,3):
    bet=H-AB[base][0]*((-(-H//AB[base][0]))-k)

    for j in range(N):
        if AB[base][0]*(-(-H//AB[base][0])-k)+b[j]>=H:
            a.append(AB[base][1]*(-(-H//AB[base][0])-k)+AB[j][1]*-(-bet//AB[j][0]))

#print(bet)
print(min(a))
#print(a)

Submission status: Wrong Answer

Solution code:
import sys
def solve():
  INF = 10 ** 12
  H,N = map(int, input().split())
  items =[] * (N-1)
  ans=0
  
  for i in range(N):
    a, b = map(int, input().split())
    c = a / b
    items.append([a,b,c])
  items.append([0.01,INF,0])
  items.sort(key=lambda x: x[2],reverse=True)
  
  att=0
  while H>0:
    if H >= items[att][0]:
      H -= items[att][0]
      ans += items[att][1]
      
    else:# H >= items[att+1][0]:
      aa=items[att][1]*( -(-H//items[att][0]))
      bb=items[att+1][1]*( -(-H//items[att+1][0]) )
      if aa>=bb:
        att+=1
      else:
        H -= items[att][0]
        ans += items[att][1]
        
  
  print(ans)
     
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import math

h, n = map(int, input().split())
ab = []
ans = 0

for i in range(n):
    a, b = [int(i) for i in input().split()]
    ab.append([a, b])

ab = sorted(ab, key=lambda x: x[0])

cosper = 0
idx = 0
for i, j in enumerate(ab):
    a, b = j
    if cosper < a / b:
        cosper = a / b
        idx = i

ab = ab[:idx+1]

atk, cons = ab[-1]
while h > atk:
    ans += cons
    h -= atk

for i in ab:
    a, b = i
    if h > a:
        continue
    ans = min(ans + cons, ans + b)
print(ans)

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
ar=[list(map(int, input().split())) for k in range(N)]
count=0
ans=0
for i in range(N):
    rate=ar[i][1]/ar[i][0]
    ar[i].append(rate)
ar.sort(key=lambda x: x[2])
#print(ar)

while H>=ar[count][0]:
    H-=ar[count][0]
    ans+=ar[count][1]
    """if len(ar)==1:
        while H>0:
            H-ar[count][0]
            count+=1"""
    if H<ar[count][0] and count!=N-1:
        while H/ar[count][1]>ar[count+1][2]:
            count+=1
    if count==N-1:
        ans+=ar[count][1]
print(ans)

Submission status: Wrong Answer

Solution code:
H, N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]

nums=[-1]*30001
for i in range(N):
  if nums[AB[i][0]]<0:
    nums[AB[i][0]]=AB[i][1]
  else:
    nums[AB[i][0]]=min(AB[i][1], nums[AB[i][0]])
  
for i in range(1, H):
  if nums[i]>0:
    for j in range(N):
      if nums[i+AB[j][0]]>0:
        if nums[i+AB[j][0]]>nums[i]+AB[j][1]:
          nums[i+AB[j][0]]=nums[i]+AB[j][1]
      else:
        nums[i+AB[j][0]]=nums[i]+AB[j][1]
      
i=H
while nums[i]<0:
  i+=1
print(nums[i])

Submission status: Wrong Answer

Solution code:
i=list(map(int,input().split()))
h=i[0]
mp=0
mls=[[0,0]]*i[1]
pls=[[0,0]]*i[1]
for k in range(i[1]):
  mls[k]=list(map(int,input().split()))
  pls[k]=[float(mls[k][0])/mls[k][1],k]
pls.sort(reverse=True)
fp=mls[pls[0][1]][0]
fm=mls[pls[0][1]][1]
kaz=h//fp
h=h-(fp*(kaz))
mp=fm*kaz
v=0
for v in range(i[1]):
  sp=mls[v][0]
  sm=mls[v][1]
  if sp>=h and sm<fm:
    fm=sm
mp+=fm
print(mp)

Submission status: Wrong Answer

Solution code:
hn = list(map(int, input().split()))
h = hn[0]
n = hn[1]

magic = []
for i in range(n):
    magic.append(list(map(int, input().split())))

magic = sorted(magic)

c = [[0] * (h + 1) for i in range(n)]

l = 0
while(l < h):
    l += magic[0][0]
    if l > h:
        m = h
    else:
        m = l
    c[0][m] = c[0][l-magic[0][0]] + magic[0][1]

for i in reversed(range(len(c[0]))):
    if c[0][i-1] == 0:
        c[0][i-1] = c[0][i]

for i in range(1, n):
    for j in range(h+1):
        if j + magic[i][0] > h:
            k = h
        else:
            k = j

        if j - magic[i][0] >= 0:   
            if c[i-1][k] > c[i][j-magic[i][0]] + magic[i][1]:
                c[i][k] = c[i][j-magic[i][0]] + magic[i][1]
            else:
                c[i][k] = c[i-1][k]


        else:
            c[i][k] = c[i-1][j]

print(c[-1][-1])

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
magic = []
for _ in range(N):
  A,B = map(int,input().split())
  magic.append([A,B])

best = []
standard = 0
base_A = 0
base_B = 0
for item in magic:
  if item[0]/item[1] >= standard:
    base_A = item[0]
    base_B = item[1]
    standard = item[0]/item[1]
Answer01 = (H//base_A)*base_B
rest = H%base_A
if rest == 0:
  print(Answer01)
  exit()
addition = 0
lcost = rest+1
for item in magic:
  if item[0]>rest:
    if item[1] < lcost:
      lcost = item[1]
  
print(Answer01+lcost)

Submission status: Wrong Answer

Solution code:
h,n = map(int, input().split())
l = []
for _ in range(n):
    a, b = map(int, input().split())
    l.append([a,b])
d = sorted(l, key=lambda x: x[0]/x[1], reverse=True)

res = 0 
cnt = len(d)

while True:
    tt = 10e+10
    ss = 10e+10
    for i in range(cnt):
        if ((h - d[i][0]) >= 0) and (tt > d[i][1]):
            res += d[i][1]
            h -= d[i][0]
            break
        else:
            if tt > d[i][0]:
                tt = d[i][0]
                ss = d[i][1]
                if i == (cnt-1):
                    h -= tt
                    res += ss
    if h <= 0:
        break

Submission status: Wrong Answer

Solution code:
# モンスターの体力H, トキの魔法N種類
H, N = map(int, input().split())

A_B_list= []
efficiency_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_B_list.append([A, B])
    efficiency_list.append(A / B)

best_magic_index = efficiency_list.index(max(efficiency_list))
best_magic = A_B_list[best_magic_index]

at_least_attack_num = H // best_magic[0]
H = H - (at_least_attack_num * best_magic[0])


B_list = []

def dfs(H, i, B_sum):
    if H <= 0:
        B_list.append(B_sum)
        
    else:
        for A_B in A_B_list:
            dfs(H - A_B[0], i + 1, B_sum + A_B[1])

B_ = best_magic[1] * at_least_attack_num

dfs(H, 0, 0)
print(min(B_list) + B_)

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
# ans=1
# for i in range(n):
#     ans+=a[i][0]
M=10**12
dp=[[M for i in range(2*h+2)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(n):
    for j in range(2*h+2):
        if j<a[i][0]:
            dp[i+1][j]=dp[i][j]
        elif dp[i+1][j-a[i][0]]<M and dp[i][j]<M:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i][0]]+a[i][1])
        elif dp[i+1][j-a[i][0]]<M:
            dp[i+1][j]=dp[i+1][j-a[i][0]]+a[i][1]
        elif dp[i][j]<M:
            dp[i+1][j]=dp[i][j]
# for i in range(n+1):
#     print(dp[i])
for i in range(h,2*h+2):
    if dp[n][i]<M:
        print(dp[n][i])
        exit()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
def main():
    dp = defaultdict(lambda: 10**5)
    
    # print(sys.stdin.readline.split())
    h,n = [int(j) for j in sys.stdin.readline().split()]
    l = [] 

    for i in range(n):
        a,b = [int(j) for j in sys.stdin.readline().split()]
        l.append((b,a))
    l.sort()
    # print(l)
    for i in range(n):
        for j in range(1,l[0][1]+1):
            dp[i, j] = l[0][0]
    for i in range(n):
        for j in range(1, h+1):
            # print(i,j, dp[i-1, j])
            dp[i,j] = dp[i-1, j]
            if j>l[i][1]:
                dp[i,j] = min(dp[i-1, j], dp[i, j-l[i][1]]+l[i][0])
            else:
                dp[i,j] = min(dp[i-1, j], l[i][0])
    sys.stdout.write(str(dp[n-1, h]))
    sys.stdout.write('\n')
if __name__ == "__main__": 
    main()     
# print(dp[n-1, h])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A= [(list(map(int, input().split()))) for _ in range(N)]
total_point = 0
 
while H > 0:
	B= [a[0]/a[1] for a in A]
	index = B.index(max(B))
 
	break
	if len(A) == 0:
		num += 1
		H = 0

print(total_point)

Submission status: Wrong Answer

Solution code:
import math
hn = input().split()
h = int(hn[0])

hai = [[0 for i in range(3)] for j in range(int(hn[1]))]
for i in range(int(hn[1])):
 tmp=input().split()
 hai[i][0]=int(tmp[0])
 hai[i][1]=int(tmp[1])
 hai[i][2]=int(tmp[0])/int(tmp[1])
hai =(sorted(hai, reverse=True,key=lambda x: x[2]))
sum=0
for i in range(len(hai)):
 if hai[i][0] <= h:
  sum=sum+ (math.floor(h/hai[i][0]))*hai[i][1]
  h = h - (math.floor(h/hai[i][0]))*hai[i][0]
hai =(sorted(hai, reverse=True,key=lambda x: x[1]))
sum=sum + math.ceil((h/hai[len(hai)-1][0]))*hai[len(hai)-1][1]
print(sum)

Submission status: Wrong Answer

Solution code:
import numpy as np

H, N = map(int, input().split())
X = []

for i in range(N):
    X.append(list(map(int, input().split())))

X = np.array(X).T

A = np.array(X[0])
B = np.array(X[1])

MP = 0

while H > 0:
    if min(B) >= H:
        MP += min(B)
        break

    C = [min(A[i],H) for i in range(N)]
    R = C / B
    max_rate = max(R)
    max_index = list(R).index(max_rate)

    n = int(H/A[max_index])

    MP += n * B[max_index]
    H -= n * A[max_index]

print(MP)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, N = map(int, input().split())
C = []
A = []
B = []
result = 0
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  C.append(a/b)
D = np.argsort(-np.array(C))
i = 0
#print(A,B,C,D)
while(H > 0):
  if( i < N ):
    if(A[D[i]] <= H):
      result += int(H / A[D[i]])*B[D[i]]
      H -= int(H / A[D[i]])*A[D[i]]
    else:
      result += min(B)
      H = 0
  i+=1
  #print(i, H, result)
print(result)

Submission status: Wrong Answer

Solution code:
[H,N] = [int(s) for s in input().rstrip().split(' ')] #HもんすたーのHP,N魔法の種類
L = []
for i in range(N):
    A_i = [int(s) for s in input().rstrip().split(' ')] #[攻撃力,消費魔力]
    A_i.append(A_i[0]/A_i[1]) #魔力の効率
    L.append(A_i)
L.sort(key = lambda x:x[2] ,reverse = True)
#print(L)

def attack(P:int,Q:list):
    for x in Q:
        if len(x) != 3:
            return "Error"
    else:
        Q.sort(key = lambda x:x[2] ,reverse = True) #一番コスパの良い魔法で攻撃
        [l_0,l_1] = [Q[0][0],Q[0][1]]
        s = P // l_0
        if P % l_0 == 0:
            return s * l_1
        else:
            H_new = P - (P * l_0)
            Q.sort(key = lambda x:x[0], reverse = True) #攻撃力が高い順
            t_0 = 100000 #とどめの一撃候補
            L_new = []
            for x in Q:
                if x[0] >= H_new:
                    t_0 = min(t_0,x[1])
                else:
                    L_new.append(x)
            if len(L_new) > 0:
                return s * l_1 + min(t_0,attack(H_new,L_new))
            else:
                return s * l_1 + t_0
print(attack(H,L))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

lines = sys.stdin.readlines()

H, _ = list(map(int, lines[0].split()))
AB = np.array([ np.array(list(map(float, s.split()))) for s in lines[1:] ]).flatten().reshape((-1,2))

ABnorm = AB[:,1] / AB[:, 0]
AB = np.insert(AB, 2, ABnorm, axis=1)
AB = AB[AB[:,0].argsort(), :]
AB = AB[AB[:,2].argsort(), :]


baseAmari = H
minv = -1
syomo = 0
syomo1min = 99999999
for i in range(len(AB)):
  if minv<AB[i, 2]:
    if baseAmari<=int(AB[i,0]):
      syomo += int(AB[i,1])
      break      
    minv = int(AB[i, 2])
    baseAt = baseAmari // int(AB[i,0])
    syomo += baseAt * int(AB[i,1])
    syomo1 = syomo + int(AB[i,1])
    if syomo1min>syomo1:
      syomo1min = syomo1
    baseAmari = baseAmari - baseAt*int(AB[i,0])
    if baseAmari == 0:
      break

if syomo > syomo1min:
  syomo = syomo1min
print(syomo)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

h, n = map(int, input().split())

list = [list(map(int, input().split())) for _ in range(n)]  

for i in range(len(list)):
  cospa = list[i][0] / list[i][1]
  list[i].append(cospa)

list.sort(key=itemgetter(1)) #リスト1は2次元以の配列
list.sort(key=itemgetter(2), reverse = True) #リスト1は2次元以の配列

mp = 0
for i in range(n):
  while h >= list[i][0]:
    count = h // list[i][0]
    h = h - ((count) * list[i][0])
    mp = count * list[i][1]
    if not h ==0:
      mp += list[i+1][0]
print(mp)

Submission status: Wrong Answer

Solution code:
def sol():
    h,n=map(int,input().split())
    l=[]
    ans=0
    for i in range(n):
        a,b=map(int,input().split())
        l.append((a,b))
    d=[0]*20005
    for i in range(10000):
        for j in l:
            a,b=j[0],j[1]
            x=d[i]+b
            if i==0 or (d[i]!=0 and d[i+a]==0):
                d[i+a]=x
            elif d[i]!=0 and d[i+a]!=0:
                d[i+a]=min(d[i+a],x)
    for i in range(h,20005):
        if ans==0:
            ans=d[i]
        elif d[i]!=0:
            ans=min(ans,d[i])
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

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

ans = H

magics = [list(map(int, input().split())) for _ in range(N)]
magics.sort()

h = H
a = 0
b = 0
cnt = 0

while h > 0:
    e = 0
    for i in range(N):
        ai = magics[i][0]
        bi = magics[i][1]
        ei = min(h, ai) / bi
        if ei > e:
            e = ei
            a = ai
            b = bi
    h -= a
    cnt += b

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

lines = sys.stdin.readlines()

H, _ = list(map(int, lines[0].split()))
AB = np.array([ np.array(list(map(float, s.split()))) for s in lines[1:] ]).flatten().reshape((-1,2))

ABnorm = AB[:,1] / AB[:, 0]
AB = np.insert(AB, 2, ABnorm, axis=1)
AB = AB[AB[:,0].argsort(), :]
AB = AB[AB[:,2].argsort(), :]


baseAmari = H
minv = -1
syomo = 0
syomo1min = 99999999
for i in range(len(AB)):
  if minv<AB[i, 2]:
    if baseAmari<=int(AB[i,0]):
      syomo += int(AB[i,1])
      print(AB[i], baseAmari, syomo)
      break      
    minv = int(AB[i, 2])
    baseAt = baseAmari // int(AB[i,0])
    syomo += baseAt * int(AB[i,1])
    syomo1 = syomo + int(AB[i,1])
    if syomo1min>syomo1:
      syomo1min = syomo1
    baseAmari = baseAmari - baseAt*int(AB[i,0])
    print(AB[i], baseAt, baseAmari, syomo, syomo1min)
    if baseAmari == 0:
      break

if syomo > syomo1min:
  syomo = syomo1min
print(syomo)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def dc(n, m):
    return -(-n // m)

# @mt
def slv(H, N, AB):
    ans = 0
    abc = [(a/b, b, a) for a, b in AB]

    abc.sort(key=lambda x: x[1])
    abc.sort(key=lambda x: x[2])
    abc.sort(key=lambda x: x[0], reverse=True)
    ri = set()
    for i in range(1, N):
        if abc[i][1] >= abc[i-1][1]:
            ri.add(i)
    ri = set(ri)
    abc_ = []
    for i in range(N):
        if i not in ri:
            abc_.append(abc[i])
    abc = abc_

    HD = defaultdict(lambda : INF)
    HD[H] = 0
    _, b, a = abc[0]
    for i in range(1, dc(H, a)+1):
        HD[H - i*a] = i*b
    for _, b, a in abc[1:]:
        for k, v in reversed(list(HD.items())):
            for i in range(1, dc(k, a)+1):
                if HD[k - i*a] > v+i*b:
                    HD[k- i*a] = v+i*b
                else:
                    break
    ans = INF
    for k, v in HD.items():
        if k <= 0:
            ans = min(ans, v)


    return ans


def main():
    H, N = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(H, N, AB))
    # H = 10**4
    # N = 1000
    # AB = [[random.randint(1, 100), random.randint(1, 10000)] for _ in range(N)]
    # print(slv(H, N, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

h,n=map(int, input().split())
al=[[0,0,0] for i in range(n)]
for i in range(n):
    a,b=map(int, input().split())
    al[i]=[a,b,a/b]
al.sort(key=lambda x: -x[0])
al.sort(key=lambda x: -x[2]) # 3番目の要素 a/b でソート

if h%al[0][0]==0:
    print(h//al[0][0])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

for i in range(N):
    AB[i].append(AB[i][0] / AB[i][1])

AB.sort(key=lambda x:x[2], reverse=True)

ans = 0
for i in range(N):
    while True:
        if H >= AB[i][0]:
            ans += AB[i][1]
            H -= AB[i][0]
        else:
            break
    
    if H <= 0:
        break

if H > 0:
    AB.sort(key=lambda x:x[1])
    for i in range(N):
        if H - AB[i][0] <= 0:
            ans += AB[i][1]
            break

print(ans)

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
# ans=1
# for i in range(n):
#     ans+=a[i][0]
M=10**9
dp=[[M for i in range(2*h+2)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(n):
    for j in range(2*h+2):
        if j<a[i][0]:
            dp[i+1][j]=dp[i][j]
        elif dp[i+1][j-a[i][0]]<M and dp[i][j]<M:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i][0]]+a[i][1])
        elif dp[i+1][j-a[i][0]]<M:
            dp[i+1][j]=dp[i+1][j-a[i][0]]+a[i][1]
        elif dp[i][j]<M:
            dp[i+1][j]=dp[i][j]
# for i in range(n+1):
#     print(dp[i])
for i in range(h,2*h+2):
    if dp[n][i]<M:
        print(dp[n][i])
        exit()

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache



sys.setrecursionlimit(10000000)

h, n = map(int, input().split())
m_list = []
max_a_b = (0, 0, 0)
for i in range(n):
  a, b = map(int, input().split())
  m_list.append((a, b))
  if a/b > max_a_b[2]:
    max_a_b = (a, b, a/b)
num_attck = h // a + int(a%b>0)

min_b = b * num_attck

@lru_cache(maxsize=100000)
def rec_attack(tmp_h, tmp_b):
  global min_b
  for a, b in m_list:
    use_b = tmp_b + b
    if use_b > min_b:
      continue
    use_h = tmp_h - a
    if use_h <= 0:
      return min(use_b, min_b)
    else:
      return rec_attack(use_h, use_b)

      
res = rec_attack(h, 0)
print(res)

Submission status: Wrong Answer

Solution code:
import math
h, n = map(int,input().split())
a = list()
b = list()
for i in range(n):
    a0, b0 = map(int,input().split())
    a.append(a0)
    b.append(b0)

m = 0
while(0 < h):
    ind = 0
    e = 0
    for i in range(n):
        e0 = min(h, a[i]) / b[i]
        #print(e0,h,a[i],b[i])
        if e < e0:
            e = e0
            ind = i
    m = m + b[ind]
    h = h - a[ind]
    #print(h, m, e, ind, a[ind], b[ind])

print(m)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
import math
import fractions
from heapq import heappush, heappop


sys.setrecursionlimit(10 ** 7)

H, N = map(int, input().split())

MAGIC = []
for _ in range(N):
    a, b = map(int, input().split())
    MAGIC.append((a, b))

dp = [[10**9] * (H+1) for _ in range(N+1)]

for i in range(N):
    dp[i][0] = 0


for i in range(N):
    for h in range(H+1):
        if h < MAGIC[i][0]:
            dp[i+1][h] = dp[i][h]
        elif h == H:
            m = min(dp[i+1][h-MAGIC[i][0]:])
            #print("num", h-MAGIC[i][0], dp[i][h-MAGIC[i][0]:])
            # print(m)
            dp[i+1][h] = min(dp[i][h], m+MAGIC[i][1])
        else:
            #print("ok", h)
            dp[i+1][h] = min(dp[i][h], dp[i+1][h-MAGIC[i][0]]+MAGIC[i][1])

    # print(dp[i+1])

# print(dp)
print(dp[N][H])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A = list()
B = list()
eff = list()
for i in range(N):
  a_, b_ = map(int, input().split())  
  eff_ = a_ / b_
  A.append(a_)
  B.append(b_)
  eff.append(eff_)
  
best_ind = eff.index(max(eff))
num_of_best_attack = H // A[best_ind]
rest = H % A[best_ind]
ret = num_of_best_attack * B[best_ind]
if rest != 0:
  B_sorted = sorted(B)
  i = 0
  for i in range(N):  
    if A[B.index(B_sorted[i])] >= rest:
      ret += B_sorted[i]
      break
print(ret)

Submission status: Wrong Answer

Solution code:
s = input().rstrip().split(' ')
h = int(s[0])
n= int(s[1])

ABs = []

for i in range(n):
    As = list(map(int, input().rstrip().split(' ')))
    ABs.extend([As])

sum = 0

while h > 0:
    max_per = 0
    
    def_A = 0
    def_B = 0

    for AB in ABs:
        A = AB[0]
        if h < A:
            A = h
        per = A / AB[1]
        if max_per < per:
            def_A = AB[0]
            def_B = AB[1]
            max_per = per
    sum = sum + def_B
    h = h - def_A

print(sum)