Problem:


Score : 300 points

Problem Statement

A programming competition site AtCode provides algorithmic problems.
Each problem is allocated a score based on its difficulty.
Currently, for each integer i between 1 and D (inclusive), there are p_i problems with a score of 100i points.
These p_1 + … + p_D problems are all of the problems available on AtCode.

A user of AtCode has a value called total score.
The total score of a user is the sum of the following two elements:

Base score: the sum of the scores of all problems solved by the user.

Perfect bonuses: when a user solves all problems with a score of 100i points, he/she earns the perfect bonus of c_i points, aside from the base score (1 ≤ i ≤ D).

Takahashi, who is the new user of AtCode, has not solved any problem.
His objective is to have a total score of G or more points.
At least how many problems does he need to solve for this objective?

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

It is possible to have a total score of G or more points.

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

Print the minimum number of problems that needs to be solved in order to have a total score of G or more points. Note that this objective is always achievable (see Constraints).

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

In this case, there are three problems each with 100 points and five problems each with 200 points. The perfect bonus for solving all the 100-point problems is 500 points, and the perfect bonus for solving all the 200-point problems is 800 points. Takahashi's objective is to have a total score of 700 points or more.

One way to achieve this objective is to solve four 200-point problems and earn a base score of 800 points. However, if we solve three 100-point problems, we can earn the perfect bonus of 500 points in addition to the base score of 300 points, for a total score of 800 points, and we can achieve the objective with fewer problems.

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

This case is similar to Sample Input 1, but the Takahashi's objective this time is 2000 points or more. In this case, we inevitably need to solve all five 200-point problems, and by solving two 100-point problems additionally we have the total score of 2000 points.

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

This case is again similar to Sample Input 1, but the Takahashi's objective this time is 400 points or more. In this case, we only need to solve two 200-point problems to achieve the objective.

Sample Input 4

5 25000
20 1000
40 1000
50 1000
30 1000
1 1000

Sample Output 4

66

There is only one 500-point problem, but the perfect bonus can be earned even in such a case. 



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
PC = [0] + [list(map(int, input().split())) for _ in range(D)]
def dfs(i, g):
  if i == 0:
    return 1e9
  mc = min(g // (100 * i), PC[i][0])
  s = mc * 100 * i
  if mc == PC[i][0]:
    s += PC[i][1]
  if s < g:
    mc += dfs(i - 1, g - s)
  return min(dfs(i - 1, g), mc)
print(dfs(D, G))

Submission status: Accepted

Solution code:
import itertools
import math
import os
import sys

import numpy as np

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


D, G = list(map(int, sys.stdin.buffer.readline().split()))
P, C = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(D)]))
P = np.array(P, dtype=int)
C = np.array(C, dtype=int)

scores = P * np.arange(1, D + 1, dtype=int) * 100 + C
ans = INF
for completes in itertools.product([True, False], repeat=D):
    completes = np.where(completes)[0]

    score = scores[completes].sum()
    cnt = P[completes].sum()
    if score >= G:
        ans = min(ans, cnt)
        continue
    for i in range(D):
        if i in completes:
            continue
        rem = math.ceil((G - score) / ((i + 1) * 100))
        if rem < P[i]:
            ans = min(ans, cnt + rem)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
Q = []
for i in range(D):
    p, c = map(int, input().split())
    Q.append([p, c,(i+1)*100])
ans = 10**18
for i in range(2**D):
    state = format(i,'0%ib'%(D))
    value = 0
    count = 0
    for s,(p,c,v) in zip(state,Q):
        if s == '1':
            value += p*v + c
            count += p
    if value >= G:
        ans = min(ans,count)
    else:
        for s,(p,c,v) in zip(reversed(state),reversed(Q)):
            if s == '1':
                continue
            if (G-value) > v*(p-1):
                value += v*(p-1)
                count += p-1
            else:
                if (G-value)%v == 0:
                    c = (G-value)//v
                else:
                    c = int((G-value)/v)+1
                value += v*c
                count += c
                ans = min(ans,count)
                break
print(ans)

Submission status: Accepted

Solution code:
import itertools


def is_achievable(problems_fully_solved, target):
    score = 0
    n_problems_solved = 0
    for problem in problems_fully_solved:
        score += p_n[problem] * 100 * problem + c_n[problem]
        n_problems_solved += p_n[problem]
    if score >= target:
        return True, n_problems_solved
    problem_partially_solved = max(set(range(1, D+1)) - set(problems_fully_solved))
    for _ in range(1, p_n[problem_partially_solved]):
        score += problem_partially_solved * 100
        n_problems_solved += 1
        if score >= target:
            return True, n_problems_solved
    return False, None


D, G = map(int, input().split(" "))
p_n, c_n = [None, ], [None, ]

for i in range(1, D+1):
    p, c = map(int, input().split(" "))
    p_n.append(p)
    c_n.append(c)

answer = 10000
for combination in itertools.product([True, False], repeat=D):
    l = [i+1 for i in range(D) if combination[i]]
    flag, n_problems_solved = is_achievable(l, G)
    if flag:
        if n_problems_solved < answer:
            answer = n_problems_solved
print(answer)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
PC = [0] + [list(map(int, input().split())) for _ in range(D)]
def dfs(i, g):
  if i == 0:
    return 1e9
  mc = min(g // (i * 100), PC[i][0])
  s = 100 * i * mc
  if mc == PC[i][0]:
    s += PC[i][1]
  if s < g:
    mc += dfs(i - 1, g - s)
  return min(mc, dfs(i - 1, g))
print(dfs(D, G))

Submission status: Accepted

Solution code:
D, G = (int(i) for i in input().split())  
PC = [[int(i) for i in input().split()] for i in range(D)] 

s = 0
Q = []
for i, (p, c) in enumerate(PC):
    s += p
    Q.append((i+1, p, c))
    
dp = [-10**18]*(s+1)
dp[0] = 0

for i, p, c in Q:
  for j in range(s, -1, -1): # 解きうる問題総数をイテレート
    for k in range(1, p+1): # 解く問題数をイテレート
      if k == p:
        cc = 100*i*k + c
      else:
        cc = 100*i*k
      if j - k >= 0:
        dp[j] = max(dp[j], dp[j - k] + cc)

for i, total in enumerate(dp):
  if total >= G:
    print(i)
    break

Submission status: Accepted

Solution code:
from itertools import product

D, G = map(int, input().split())
pc = [tuple(map(int, input().split())) for _ in range(D)]

ans = 10**18
for pair in product(range(2), repeat=D):
    score = 0
    cnt = 0
    for i, solve in enumerate(pair):
        p, c = pc[i]
        if solve:  # ポイント合算
            score += (i + 1) * 100 * p + c
            cnt += p

    if score >= G:
        ans = min(ans, cnt)
        continue

    rest = G - score
    plus = 10**9
    for i, solve in enumerate(pair):
        j = 100*(i+1)
        p, _ = pc[i]
        if not solve:
            need = (rest + j - 1) // j
            if need <= p:
                plus = min(plus, need)
    ans = min(ans, cnt + plus)

print(ans)

Submission status: Accepted

Solution code:
import sys

n, G = map(int, sys.stdin.readline().split())
G //= 100
p = []
t = []
for i in range(1, n+1):
    pi, ci = map(int, sys.stdin.readline().split())
    p.append(pi)
    t.append(i * pi + ci // 100)

def main():
    res = sum(p)
    for i in range(2 ** n - 1):
        s = 0
        cnt = 0
        for j in range(n):
            if i >> j & 1:
                s += t[j]
                cnt += p[j]
            else:
                m = j + 1
        if s < G:
            tmp = (G - s + m - 1) // m
            if tmp < p[m-1]:
                cnt += tmp
            else:
                continue
        res = min(res, cnt)
    
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, G = I[:2]
G //= 100
p, c = I[2:].reshape(-1, 2).T
c //= 100

def main():
    v = np.arange(1, n+1)
    t = v * p + c
    combs = np.arange(2 ** n - 1)[:, None] >> np.arange(n) & 1
    res = p.sum()
    for comb in combs:
        s = t[comb == 1].sum()
        cnt = p[comb == 1].sum()
        if s - G < 0:
            m = np.amax(v[comb == 0])
            tmp = (G - s + m - 1) // m
            if tmp < p[m-1]:
                cnt += tmp
            else:
                continue
        res = min(res, cnt)
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import math, sys
sys.setrecursionlimit(10**7)
d,g = map(int, input().split())
data = []
ans = 10000000
for i in range(1,d+1):
    p, c = map(int, input().split())
    data.append([i*100 , p , c])
def dfs(li):
    if len(li) == d:
        global ans
        total = 0
        candidate = 0
        for i in range(d):
            if li[i]:
                total += data[i][0] * data[i][1] + data[i][2]
                candidate += data[i][1]
        if total >= g:
            ans = min(ans, candidate)
        else:
            max_point = max([data[i] for i in range(d) if not li[i]])
            if max_point[0] * (max_point[1] - 1) + total >= g:
                candidate += math.ceil((g - total) / max_point[0])
                ans = min(ans, candidate)
    else:
        dfs(li + [False])
        dfs(li + [True])
dfs([])
print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
# bit全探索で、全問解く問題の組み合わせをすべて試す

scores=[None]*D
for i in range(D):
  p,c=map(int,input().split())
  # 一問の得点、問題数、ボーナス、全てといたときの得点
  scores[i]=[(i+1)*100,p,c,((i+1)*100)*p+c]

# あとあとのために点数高い順に並べる
scores=sorted(scores,key=lambda x:x[0])[::-1]

# 全問とく組み合わせに対して、最小の問題数
ans=D*100
for i in range(2**D):
  total=0
  solve=0
  for j in range(D):
    if (i>>j)&1:
      # 全問とく問題のボーナスを足していく
      total+=scores[j][3]
      solve+=scores[j][1]
  if total>=G:
    if ans>solve:
      ans=solve
    continue
  rest=G-total
  for j in range(D):
    if (i>>j)&1==0:
      point=scores[j][0]
      num=scores[j][1]-1 # 全問とかないので1減らす
      if point*num<rest:
        rest-=point*num
        solve+=num
      else:
        solve+=(rest//point+(rest%point>0))
        rest=0
    if rest<=0 and ans>solve:
      ans=solve
  
print(ans)

Submission status: Accepted

Solution code:
import itertools


d, g = [int(i) for i in input().split()]
pc = [[int(i) for i in input().split()] for _ in range(d)]

ans = float("inf")
for bit in itertools.product((0, 1), repeat=d):
    score = 0
    solve = 0
    rest = set(range(d))

    for i in range(d):
        if bit[i] == 1:
            score += pc[i][0] * (i+1) * 100 + pc[i][1]
            solve += pc[i][0]
            rest.discard(i)

    if score < g:
        problem = max(rest)
        needs = -((-(g - score)) // ((problem+1)*100))
        n = min(pc[problem][0] - 1, needs)
        score += n * (problem+1) * 100
        solve += n
    if score >= g:
        ans = min(ans, solve)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
pc = [list(map(int,input().split())) for _ in range(d)]
ans = float("inf")
def bfs(i,solve,sum,n):
  if i == d:
    if sum>=g:
      global ans
      ans = min(ans,solve)
    elif (pc[n][0]-1)*(n+1)*100 >= g-sum:
      if (g-sum) % ((n+1)*100) == 0:
        plus = (g-sum) // ((n+1)*100)
      else:
        plus = (g-sum) // ((n+1)*100) + 1 
      ans = min(ans,solve+plus)
  else:
    bfs(i+1,solve+pc[i][0],sum+pc[i][0]*(i+1)*100+pc[i][1],n)
    bfs(i+1,solve,sum,i)
bfs(0,0,0,0)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
li = []

for i in range(d):
    p,c = map(int,input().split())
    li.append([p,c])

ans = 10**9
for i in range(1<<d):
    ttl = 0
    cnt = 0
    memo = [0 for i in range(d)]
    for j in range(d):
        if (i>>j)&1:
            ttl += li[j][1]+(j+1)*li[j][0]*100
            cnt += li[j][0]
            memo[j] = 1
    #print(memo,ttl)
    if ttl < g:
        memo2 = g- ttl
        for j in range(d-1,-1,-1):
            if memo[j] == 0:
                if memo2%(100*(j+1)) == 0:
                    cnt2 = min(memo2//(100*(j+1)),li[j][0]-1)
                    cnt += cnt2
                    ttl += cnt2*(100*(j+1))
                    #print(44444444)
                else:
                    cnt2 = min(((memo2//(100*(j+1)))+1),li[j][0]-1)
                    #print(((memo2//(100*(j+1)))+1))
                    cnt += cnt2
                    ttl += cnt2*(100*(j+1))
                break
    if ttl >= g:
        ans = min(ans,cnt)
"""   
    if ans == cnt:
        print(memo,ttl,111111)
"""   
    

print(ans)

Submission status: Accepted

Solution code:
import math
D, G = map(int, input().split())

P = []
for _ in range(D):
    p, c = map(int, input().split())
    P.append((p, c))

ans = 10000
for i in range(2 ** D):
    score = 0
    solve = 0
    maxj = -1
    for j in range(D):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            score += (j+1)*P[j][0]*100+P[j][1]
            solve += P[j][0]
        else:
            maxj = max(maxj, j)

    if maxj == -1:
        if score >= G:
            ans = min(ans, solve)
    elif score+(maxj+1)*(P[maxj][0]-1)*100 >= G:
        solve += max(0, math.ceil((G-score)/(maxj+1)/100))
        ans = min(ans, solve)
    # print(bin(i), ans, solve, score, maxj, score+(maxj+1)*(P[maxj][0]-1))

print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
ps = [0]*d
cs = [0]*d

for i in range(d):
  p, c = map(int, input().split())
  ps[i] = p
  cs[i] = c

min_count = sum(ps)
for i in range(2**d-1):
  point = 0
  count = 0
  max_other_j = -1
  for j in range(d):
    if (i >> j) & 1:
      point += (j+1)*100*ps[j] + cs[j]
      count += ps[j]
    else:
      max_other_j = max(max_other_j, j)
  if point < g:
    if max_other_j < 0:
      continue
    else:
      if (g - point)%((max_other_j+1)*100) == 0:
        other_count = (g - point)//((max_other_j+1)*100)
      else:
        other_count = (g - point)//((max_other_j+1)*100)+1
      if other_count >= ps[max_other_j]:
        continue
      else:
        count += other_count
  if count <= min_count:
    min_count = count
  
print(min_count)

Submission status: Accepted

Solution code:
D,G=list(map(int,input().split()))
li=[]
P=[]
Bonus=[]
for i in range(D):
   p,c=list(map(int,input().split()))
   P.append(p)
   Bonus.append(c)

for i in range(1<<D):
   E=[d for d in range(D)]
   output=[]
   for j in range(D):
      if((i>>j)&1)==1:
         output.append(j)
   Not_output=list(set(E)-set(output))
   Not_output.sort(reverse=True)

   score=0
   solve_problems=0
   #100i点の問題はすべて解く
   for i in output:
      score+=P[i]*100*(i+1)
      score+=Bonus[i]
      solve_problems+=P[i]
   
   for i in Not_output:
      if score>=G:
         break

      elif score+(P[i]-1)*100*(i+1)<G:
         score+=(P[i]-1)*100*(i+1)
         solve_problems+=(P[i]-1)
      else:
         while(True):
            score+=100*(i+1)
            solve_problems+=1
            if(score>=G):
               break

   if score>=G:
      li.append(solve_problems)
print(min(li))

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]

ans = float("inf")
for b in range(1<<d):
    m = set(range(1, d+1))
    c = 0
    s = 0
    for i in range(d):
        if b & (1<<i):
            c += pc[i][0]
            s += 100*(i+1)*pc[i][0] + pc[i][1]
            m.discard(i+1)
    if s >= g:
        ans = min(ans, c)
        continue
    while s < g and m:
        p = pc[max(m)-1][0]
        for _ in range(p):
            c += 1
            s += 100*max(m)
            if s >= g:
                break
        m.discard(max(m))
    ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
arr = []
n = 0
for i in range(D):
    arr.append([int(c) for c in input().split()])
    n += arr[i][0]

ans = 1e9

for bit in range(1 << D):
    sum = 0
    num = 0
    rest_max = -1
    for i in range(D):
        if bit & 1 << i:
            sum += 100 * (i + 1) * arr[i][0] + arr[i][1]
            num += arr[i][0]
        else:
            rest_max = i

    if sum < G:
        p = 100 * (rest_max + 1)
        need = (G - sum + p - 1) // p
        if need >= arr[rest_max][0]:
            continue
        num += need
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
G=G//100
p=[]
c=[]
for i in range(D):
    pp,cc=map(int,input().split())
    p.append(pp)
    c.append(cc//100)

ans=float("INF")
for i in range(1<<D):
    cnt=0
    toku=0
    for j in range(D):
        if 1&i>>j:
            toku+=p[j]*(j+1)+c[j]
            cnt+=p[j]
    #print(i,toku,cnt)
    if toku>=G:
        ans=min(ans,cnt)
        #sprint(i,toku,cnt)
    else:
        for j in range(D-1,-1,-1):
            if 1&i>>j==False:
                for k in range(p[j]-1):
                    toku+=j+1
                    cnt+=1
                    if toku>=G:
                        ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
G=G//100
p=[]
c=[]
for i in range(D):
    pp,cc=map(int,input().split())
    p.append(pp)
    c.append(cc//100)

ans=float("INF")
for i in range(1<<D):
    cnt=0
    toku=0
    for j in range(D):
        if 1&i>>j:
            toku+=p[j]*(j+1)+c[j]
            cnt+=p[j]
    #print(i,toku,cnt)
    if toku>=G:
        ans=min(ans,cnt)
        #sprint(i,toku,cnt)
    else:
        for j in range(D-1,-1,-1):
            if 1&i>>j:
                continue
            for k in range(p[j]-1):
                toku+=j+1
                cnt+=1
                if toku>=G:
                    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

d,g = LI()
pc = [LI() for _ in range(d)]
ans = inf
for i in range(2**d):
    b = [0]*d
    for j in range(d):
        if (i >> j) & 1:
            b[j] = 1
    tmp = 0
    cnt = 0
    for j in range(d):
        if b[j]:
            tmp += pc[j][0]*(j+1)*100 + pc[j][1]
            cnt += pc[j][0]
    if tmp >= g:
        ans = min(ans,cnt)
        continue
    tmp2 = 0
    for j in range(d):
        if not b[j]:
            tmp2 = max(tmp2,j)
    x,y = divmod((g-tmp),(tmp2+1)*100)
    if x > pc[tmp2][0]:
        continue
    cnt += x + (y != 0)
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math


D, G = map(int, input().split())
basic = []
bonus = {}
p_c_list = []
for i in range(1, D+1):
    p, c = map(int, input().split())
    p_c_list.append([p, c])


min_count = float("inf")
for ans in itertools.product([0, 1], repeat=D):
    point = 0
    count = 0
    for idx, a in enumerate(ans):
        point += (p_c_list[idx][0]*(100*(idx + 1)) + p_c_list[idx][1])*a
        count += p_c_list[idx][0]*a

    if point < G:
        for idx, a in enumerate(reversed(ans)):
            if a == 0:
                plus_count = math.ceil((G - point) / ((D-idx)*100))
                # print(idx, D-idx, p_c_list[D-idx-1], G - point, plus_count)
                if plus_count >=  p_c_list[D-idx-1][0]:
                    count = float("inf")
                    point = 0
                else:
                    count += plus_count
                    point = G
                break
    # print(G, point, count)
    if point >= G:
        min_count = min(min_count, count)

print(min_count)

Submission status: Accepted

Solution code:
import math

d,g = map(int,input().split())

l = [list(map(int,input().split())) for i in range(d)]
ans = float("inf")

for bit in range(1<<d):
  sum = 0
  count = 0
  f = set(range(1,d+1))
  
  for i in range(d):
    if bit & (1<<i):
      sum += (i+1)*l[i][0]*100 + l[i][1]
      count += l[i][0]
      f.discard(i+1)
      
  if sum < g:
    x = max(f)
    n = min(l[x-1][0], math.ceil((g-sum)/(x*100)))
    sum += n*100*x
    count += n
    
  if sum >= g:
    ans = min(ans,count)
    
print(ans)

Submission status: Accepted

Solution code:
D,G = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(D)]
mincount = 1000
for i in range(2**D):
	Tcount = 0
	Tscore = 0
	for j in range(D):
		if((i>>j)&1):
			Tscore += l[j][0]*(j+1)*100 + l[j][1]
			Tcount += l[j][0]
	if Tscore >= G:
		if Tcount <= mincount:
			mincount = Tcount
	else:
		for j in range(D):
			AFcount = 0
			if(((~i)>>(D-j-1))&1):
				while Tscore < G and AFcount<=l[D-j-1][0]:
					Tscore += (D-j)*100
					Tcount += 1
					AFcount += 1
			if Tscore >= G:
				if Tcount <= mincount:
					mincount = Tcount
				break
print(mincount)

Submission status: Accepted

Solution code:

def calc(i):
    sum_problems = 0
    for j in range(D):
        if i & (1 << j):
            sum_problems += p[j]
    num_problems[i] = sum_problems

nums=list(map(int,input().split()))
D = nums[0]
G = nums[1]
p = []
c = []

num_problems = [1000] * (1 << D)

for i in range(D):
    nums=list(map(int,input().split()))
    p.append(nums[0])
    c.append(nums[1])


for i in range(1 << D):
    sum_tmp = 0
    
    for j in range(D):
        if i & (1 << j):
            sum_tmp += p[j] * (j + 1) * 100 + c[j]
    
    if sum_tmp >= G:
        calc(i)
        
    else:
        j = D-1
        sum_res = 0
        while j > -1:
            if not (i & (1 << j)):
                for k in range(p[j]):
                    sum_tmp += 100 * (j + 1)
                    sum_res += 1
                    if sum_tmp >= G:
                        break
            j -= 1
            if sum_tmp >= G:
                calc(i)
                num_problems[i] += sum_res
                break
            
print(min(num_problems))

Submission status: Accepted

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

def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    answer = 1000
    ## どの問題を全部解くか全探索
    for i in range(2**D):
        tmpans = 0
        score = 0
        com_problem = []

        for j in range(D):
            if i & 1<<j:
                score += p[j]*100*(j+1)+c[j]
                tmpans += p[j]
                com_problem.append(j)
        if score >= G:
            answer = min(answer,tmpans)
        else:

            for probrem_index in range(D-1,-1,-1):
                if probrem_index in com_problem:
                    continue

                if (G-score)>100*(probrem_index+1)*(p[probrem_index]-1):
                    break
                else:
                    tmpans += ceil((G-score) / (100*(probrem_index+1)))
                    answer = min(answer,tmpans)
                    break

    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]"
    c = [int()] * (D)  # type: "List[int]"
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
table = []
for i in range(D):
    p,c = map(int, input().split())
    table.append((i+1,p,c))
ans = 10**3
for i in range(1<<D):
    count = 0
    score = 0
    remain = []
    for j in range(D):
        d,p,c = table[j]
        if i & (1<<j):
            score += 100*(d)*p+c
            count += p
        else:
            remain.append((d,p,c))
    if score < G:
        remain.sort(reverse=True)
        d,p,c = remain[0]
        while score < G and p > 0:
            score += 100*d
            count += 1
            p -= 1
    if score >= G:
        ans = min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p = [0 for _ in range(D)]
c = [0 for _ in range(D)]
for i in range(D):
    p[i], c[i] = map(int, input().split())

score_sum = [0 for _ in range(D)]
for i in range(D):
    score_sum[i] = (i + 1) * 100 * p[i] + c[i]


def calc(i, g):
    if g <= 0:
        return 0
    if i == D:
        return 10 ** 7
    
    x = calc(i + 1, g)
    y = p[i] + calc(i + 1, g - score_sum[i])
    upper_sum = sum(score_sum[i + 1:])
    if 100 * (i + 1) * p[i] + upper_sum < g:
        z = 10 ** 7
    else:
        z = sum(p[i + 1:]) + max(0, (g - upper_sum + 100 * (i + 1) - 1) // (100 * (i + 1)))
    return min(x, y, z)


def solve():
    ans = calc(0, G)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
table = []
for i in range(D):
    p,c = map(int, input().split())
    table.append((i+1,p,c))

ans = 10**3
for i in range(1<<D):
    score = 0
    count = 0
    remain = []
    for j in range(D):
        a,p,c = table[j]
        if i & (1<<j):
            score += a*100*p+c
            count += p
        else:
            remain.append((a,p,c))
    if score >= G:
        ans = min(count,ans)
    else:
        remain.sort(reverse=True)
        a,p,c = remain[0]
        for k in range(p):
            score += a*100
            count += 1
            if score >= G:
                ans = min(count,ans)
print(ans)

Submission status: Accepted

Solution code:
import math

D, G = [int(x) for x in input().split()]
P = [[int(x) for x in input().split()] for i in range(D)]

min_ = 1e+8
for bit in range(2**D):
  score = 0
  n_solved = 0
  rest = -1
  for i in range(D):
    if bit >> i & 1: 
      score += (i + 1) * 100 * P[i][0] + P[i][1]
      n_solved += P[i][0]
    else:
      rest = i
  if G > score:
    s1 = 100 * (rest + 1)
    need = (G - score + s1 - 1) // s1
    if need >= P[rest][0]:
      continue
    n_solved += need
  min_ = min(min_, n_solved)
print(min_)

Submission status: Accepted

Solution code:

def dfs(i, total, S, remain):
    global ans
    if i == D:
        if S < G:
           use = max(remain)
           N = min(L[use-1][0], -(-(G-S)//(100*use)))
           S += 100 * N * use
           total += N
           
        if S >= G:
           ans = min(ans, total)
    else:
        dfs(i+1, total, S, remain)
        dfs(i+1, total + L[i][0], S + 100 * (i+1) * L[i][0] + L[i][1], remain - {i+1})

D, G = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(D)]
ans = 10 ** 9

dfs(0, 0, 0, set(range(1, D+1)))

print(ans)

Submission status: Accepted

Solution code:
D,G=map(int, input().split())
PC=[0]+[list(map(int,input().split())) for _ in range(D)]
PC

def dfs(i,g):
    if i ==0:
        return 1e9
    m =min(g//(i*100),PC[i][0])
    s=100*i*m
    if m ==PC[i][0]:
        s+=PC[i][1]
    if s<g:
        m+=dfs(i-1,g-s)
    return min(m, dfs(i-1,g))
print(dfs(D,G))

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
PC = [0] + [list(map(int, input().split())) for _ in range(D)]
#print(PC)
def dfs(i, g):
  if i == 0:
    return 1e9
  m = min(g // (i * 100), PC[i][0])
  #print("m: " + str(m))
  s = 100 * i * m
  #print("s: " + str(s))
  if m == PC[i][0]:
    s += PC[i][1]
  if s < g:
    m += dfs(i - 1, g - s)
  return min(m, dfs(i - 1, g))
print(dfs(D, G))

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(D)]
plst = [0] * D
ans = 0
for i in range(D):
    ans += p[i][0]

def dfs(n):
    global ans
    if n == D:
        cnt = 0
        total = 0
        for i in range(D):
            if plst[i] == 0:
                continue
            elif plst[i] == 1:
                cnt += p[i][0]
                total += (100 * (i + 1) * p[i][0]) + p[i][1]
        if total < G:
            for j in range(D - 1, -1, -1):
                if plst[j] == 0:
                    for k in range(p[j][0] - 1):
                        total += (100 * (j + 1))
                        cnt += 1
                        if total >= G:
                            break
                    break
            if total >= G:
                ans = min(ans, cnt)
        else:
            ans = min(ans, cnt)
        return

    for i in range(2):
        plst[n] = i
        dfs(n + 1)
    return

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int, input().split())
p = [0] * d
c = [0] * d
for i in range(d):
    p[i], c[i] = map(float, input().split())
    
ans = 0

    
for i in range(2**d):
    score = 0
    count = 0
    for j in range(d):
        if (i >> j) & 1:
            score += p[j]*100*(j+1) + c[j]
            count += p[j]
            
    if g > score:
        for k in range(d-1,-1,-1):
            if (i >> k) & 1 == 0 :
                if (g - score) <= p[k]*100*(k+1):
                    count += (g - score -1)//((k+1)*100) +1
                    break
                else:
                    count = 1145141919
                    break
                    
    if ans == 0 or count<ans:
        ans = count

print(int(ans))

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
pc = []
for i in range(D):
    p,c = map(int,input().split())
    pc.append([i+1,p,c])
pc.sort(reverse = True)
ansc = []
for i in range(2**D):
    count = 0
    sumb = 0
    pc2 = []
    for j in range(D):
        if (i >> j) & 1 == 1:
            sumb += 100*pc[j][0]*pc[j][1] + pc[j][2]
            count += pc[j][1]
        else:
            pc2.append(pc[j])
    pc2 = sorted(pc2,reverse = True)
    c2 = 0
    if sumb < G:
        c2 = (G - sumb)//(100*pc2[0][0])
        if (G - sumb)%(100*pc2[0][0]) != 0:
            c2 += 1
        if c2 >= pc2[0][1]:
            count = 10**9
        else:
            count += c2
    ansc.append(count)
print(min(ansc))