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:
from collections import Counter,defaultdict,deque
from heapq import heappop, heappush
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

d,g = inpl()
p = [0] * d
c = [0] * d
for i in range(d):
    p[i], c[i] = inpl()
res = float('inf')

for flag in itertools.product((0,1),repeat=d):
    sco = 0
    cnt = 0
    for i,j in enumerate(flag):
        if j:
            sco += (i+1)*100*p[i] + c[i]
            cnt += p[i]
    # print(flag,sco,cnt)
    if sco >= g:
        res = min(res, cnt)
    else:
        rem = g - sco #残り
        for i,j in enumerate(flag):
            if not j:
                tmp = -(-rem//((i+1)*100))
                # print(flag,tmp)
                if tmp < p[i]:
                    res = min(res, cnt+tmp)
print(res)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop, heappush
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

d,g = inpl()
p = [0] * d
c = [0] * d
for i in range(d):
    p[i], c[i] = inpl()
res = float('inf')

for flag in itertools.product((0,1),repeat=d):
    sco = 0
    cnt = 0
    for i,j in enumerate(flag):
        if j:
            sco += (i+1)*100*p[i] + c[i]
            cnt += p[i]
    # print(flag,sco,cnt)
    if sco >= g:
        res = min(res, cnt)
    else:
        rem = g - sco #残り
        for i,j in enumerate(flag):
            if not j:
                tmp = rem/((i+1)*100)
                # print(flag,tmp)
                if tmp < p[i]:
                    res = max(min(res, cnt+tmp),1)
print(int(res))

Submission status: Accepted

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

ans = []

for i in range(2**D):
  x = bin(i).replace("0b","")
  x = x.zfill(D)
  
  point,cnt = 0,0
  
  for l,st in enumerate(x):
    if st == "1":
      cnt += int(pc[l][0])
      point += int(pc[l][1]) + (((l + 1)*100) * int(pc[l][0]))
      
  if point >= G:
    ans.append(cnt)
  else:
    for n,st2 in enumerate(x[::-1]):
      if st2 == "0":
        for z in range(int(pc[D-(n+1)][0])):
          point += ((D-n)*100)
          cnt += 1
          if point >= G:
            ans.append(cnt)

print(min(ans))

Submission status: Accepted

Solution code:
import itertools
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

D, G = inpl()
G //= 100
pc = [inpl() for _ in range(D)]
p = [x[0] for x in pc]
c = [x[1]//100 for x in pc]
total = [(i+1)*p[i]+c[i] for i in range(D)]

ans = sum(p)
for complete in itertools.product(range(2),repeat=D):
    n = 0
    g = G
    for i in range(D):
        if complete[i]:
            g -= total[i]
            n += p[i]
    for i in range(D-1,-1,-1):
        if complete[i]:
            continue
        else:
            if g <= 0:
                break
            elif g > (p[i]-1)*(i+1):
                g -= (p[i]-1)*(i+1)
                n += p[i]-1
            else:
                n += g//(i+1) + int(bool(g%(i+1)))
                g = 0
                break
    if g <= 0 and n < ans:
        ans = n
print(ans)

Submission status: Accepted

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

scr_comp=[0]*d
scr_no_comp=[0]*d
for i in range(d):
    scr_comp[i]=p[i]*(i+1)*100+c[i]
    scr_no_comp[i]=(p[i]-1)*(i+1)*100

ans=sum(p)
for i in range(2**d):
    scr_tmp=0
    num_tmp=0
    for j in range(d):
        if i&(2**j):
            scr_tmp+=scr_comp[j]
            num_tmp+=p[j]
    if scr_tmp >= g:
        ans=min(ans, num_tmp)
        continue
    for j in range(d-1, -1, -1):
        if i&(2**j):
            continue
        if scr_tmp + scr_no_comp[j] >= g:
            num_tmp+=(g-scr_tmp)//((j+1)*100)
            num_tmp+=1 if ((g-scr_tmp)%((j+1)*100)!=0) else 0
            ans=min(ans, num_tmp)
        else:
            scr_tmp+=scr_no_comp[j]
            num_tmp+=p[j]-1
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
pc=[list(map(int,input().split())) for i in range(d)]
dp=[[-1]*(1001) for i in range(d)]
for i in range(d):
    dp[i][0]=0
lst=[]
for i in range(d):
    p,c=pc[i]
    h=[0]
    for j in range(1,p):
        h.append(100*(i+1)*j)
    h.append(100*(i+1)*p+c)
    lst.append(h)
for i in range(d):
    p,c=pc[i]
    h=lst[i]
    if i==0:
        for j in range(1,p+1):
            dp[0][j]=h[j]
    else:
        for j in range(1,p+1):
            for k in range(j,1001):
                if dp[i-1][k-j]!=-1:
                    dp[i][k]=max(dp[i-1][k-j]+h[j],dp[i-1][k])
                else:
                    break
for i in range(1,1001):
    if dp[d-1][i]>=g:
        print(i)
        break

Submission status: Accepted

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

INF = 1001001001
ans = INF
for bit in range(2**d):
    total_comp = 0
    q_total = 0
    for i in range(d):
        if (1 << i) & bit:
            total_comp += pt_ls[i][0] * 100 * (i+1) + pt_ls[i][1]
            q_total += pt_ls[i][0]

    if total_comp >= g:
        ans = min(ans, q_total)
    else:
        for i in reversed(range(d)):
            if not (1<<i) & bit:
                a = g - total_comp
                b = 100 * (i+1)
                need_q = (a + b - 1) // b
                if need_q < pt_ls[i][0]:
                    q_total += need_q
                    ans = min(ans, q_total)
                    break

print(ans)

Submission status: Accepted

Solution code:
d,g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]
 
ans = float("inf")
 
for bit in range(1 << d):
    count = 0
    sum = 0
    L=[]
 
    for i in range(d):
        if bit & (1 << i):
            sum += pc[i][0] * (i + 1) * 100 + pc[i][1]
            count += pc[i][0]
        else:
            L.append(i+1)
            
    if sum < g:
        n = min(pc[max(L)-1][0], -(-(g - sum) // (max(L) * 100)))
        count += n
        sum += n * max(L) * 100
 
    if sum >= g:
        ans = min(ans, count)
print(ans)

Submission status: Accepted

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

def function(G, i):
    if i == 0:
        return 10**9
    n = min(G // (i *100), pc[i][0])
    s = n * i * 100
    if n == pc[i][0]:
        s += pc[i][1]
    if s < G:
        n += function(G-s, i - 1)
    return min(n, function(G, i-1))

print(function(G, D))

Submission status: Accepted

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

ans = float("inf")
for bit in range(2 ** D):
    tmp_ans = 0
    tmp_sum = 0
    for j in range(D):
        if bit >> j & 1:
            tmp_sum += questions[j][0] * 100 * (j + 1) + questions[j][1]
            tmp_ans += questions[j][0]
    if tmp_sum < G:
        for j in range(D - 1 , -1 , -1):
            if bit >> j & 1:
                continue
            else:
                for k in range(questions[j][0]):
                    tmp_ans += 1
                    tmp_sum += 100 * (j + 1)
                    if tmp_sum >= G:
                        break
                if tmp_sum >= G:
                    break
    if tmp_ans < ans and tmp_sum >= G:
        ans = tmp_ans
print(ans)

Submission status: Accepted

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

ans = 10 ** 4

for bits in range(2 ** D + 1):
    num, score = 0, 0
    # ここはただBitが立ってる箇所の完全に解き切ることをしているだけ
    for i in range(D):
        if (0x01 << i) & bits:
            score += PC[i][0] * (i + 1) * 100 + PC[i][1]
            num += PC[i][0]

    i = D - 1
    pnum = 0
    #while score < G and i >= 0:
    #     # bitが立っていない、つまり完全に解き切っていない問題の時
    #     if not (0x01 << i) & bits:
    #         score += (i + 1) * 100
    #         num += 1
    #         pnum += 1
    #         # これである点数の
    #         if pnum >= PC[i][0]:
    #             pnum = 0
    #             i -= 1
    #     else:
    #         i -= 1
    while score < G and i >= 0:
        # bitが立っていない、つまり完全に解き切っていない問題の時
        if not (0x01 << i) & bits:
            for t in range(PC[i][0]):
                # これである点数の
                if score < G:
                    score += (i + 1) * 100
                    num += 1
            break
        else:
            i -= 1


    if score >= G:
        ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce


# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

basecost = 100

##saiki
def dfs(i, total, cnt, nokori):
    global ans
    if i == d:
        if total < g:
            use = max(nokori)
            n = min(data[use - 1][0], -(-(g - total) // (use * basecost)))
            cnt += n
            total += n * use * basecost + data[use - 1][1]
        if total >= g:
            ans = min(ans, cnt)
    else:
        dfs(i + 1, total, cnt, nokori)
        dfs(i + 1, total + (i + 1) * data[i][0] * basecost + data[i][1], cnt + data[i][0], nokori - {i+1})


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

ans = sys.maxsize

dfs(0, 0, 0, set(range(1, d + 1)))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil
D, G = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(D)]

a = [True, False]
ss = product(a, repeat=D)

li = []
for i in ss:
  lii = []
  for itr, val in enumerate(i):
    if val:
      lii.append(itr)
  li.append(lii)

oneD = set([i for i in range(D)])
    
# print(li)

ans = 10**9
for i in li:
  psum = 0
  cnt = 0
  for j in i:
    psum += (j + 1) * pc[j][0] * 100 + pc[j][1]
    cnt += pc[j][0]
  if psum >= G:
    ans = min(ans, cnt)
  else:
    hoge = max(oneD - set(i))
    if pc[hoge][0] >= ceil((G - psum)/((hoge+1)*100)):
      cnt += ceil((G - psum)/((hoge+1)*100))
      ans = min(ans, cnt)
    
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
p = [list(map(int,input().split())) for i in range(d)]
ans = float('inf')
for i in range(2**d):
  solved = 0
  point = 0
  luck = -1
  for j in range(d):
    if i >> j & 1:
      # pi問題をすべてといた場合の得点を加算
      point += 100 * (j+1) * p[j][0] + p[j][1]
      solved += p[j][0]
    #elif luck < 0:
    else:
      luck = j
  #全問とかないようにするため
  k = 0
  # 不完全解答するのは最も配点が高い大問1第のみ
  while k < p[luck][0] and point < g:
    point += 100 * (luck + 1)
    k += 1
    solved += 1
  if point >= g and solved < ans:
    ans = solved
print(ans)

Submission status: Accepted

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

ans = 10 ** 4

for bits in range(2 ** D + 1):
    num, score = 0, 0
    for i in range(D):
        if (0x01 << i) & bits:
            score += PC[i][0] * (i + 1) * 100 + PC[i][1]
            num += PC[i][0]
    
    i = D - 1
    pnum = 0
    while score < G and i >= 0:
        if not (0x01 << i) & bits:
            score += (i + 1) * 100
            num += 1
            pnum += 1
            if pnum >= PC[i][0]:
                pnum = 0
                i -= 1
        else:
            i -= 1
    
    if score >= G:
        ans = min(ans, num)

print(ans)

Submission status: Accepted

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

question_list = []

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

ans = 10 ** 5

for i in range(2 ** D):
    bit = format(i, "0" + str(D) + "b") # 完全に解く問題にビットを立てる

    total = 0
    num_q = 0
    for j in range(D):
        if bit[j] == "1":
            total += question_list[j][0] * 100 * (j + 1) + question_list[j][1]
            num_q += question_list[j][0]
    
    res = max(0, G - total)

    if res > 0:
        ind = bit.rfind("0") ##完全に解かないものの数
        res_q = res // (100 * (ind + 1)) + (1 if (res % (100 * (ind + 1)) != 0) else 0)
        if res_q > question_list[ind][0]:
            continue
        num_q += res_q
    
    ans = min(ans, num_q)

print(ans)

Submission status: Accepted

Solution code:
dg = input().split(' ');
d = int(dg[0]);
g = int(dg[1]);
p = [0]*d;
c = [0]*d;
for i in range(d) :
    s = input().split(' ');
    p[i] = int(s[0]);
    c[i] = int(s[1]);

ans = sum(p);
for i in range(2**d) :
    sumpoint = 0;
    luck = -1;
    point = 0;
    for j in range(d-1,-1,-1) :
        if((i & 2**j)>>j) :
            sumpoint += (j+1)*100*p[j] + c[j];
            point += p[j];
        elif(luck<0) :
            luck = j
    k = 0;
    while k < p[luck] and sumpoint < g :
        sumpoint += (luck+1)*100;
        point += 1;
        k+= 1;
    if sumpoint >= g and point < ans :
        ans = point;

print(ans);

Submission status: Accepted

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

question_list = []

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


ans = 10 ** 5

for i in range(2 ** D):
    bit = format(i, "0" + str(D) + "b") # 完全に解く問題にビットを立てる

    total = 0
    num_q = 0
    for j in range(len(bit)):
        if bit[j] == "1":
            total += question_list[j][0] * 100 * (j + 1) + question_list[j][1]
            num_q += question_list[j][0]
    
    res = max(0, G - total)

    if res > 0:
        ind = bit.rfind("0")
        res_q = res // (100 * (ind + 1)) + (1 if (res % (100 * (ind + 1)) != 0) else 0)
        if res_q > question_list[ind][0]:
            continue
        num_q += res_q
    
    ans = min(ans, num_q)

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int,input().split())
PC = [list(map(int, input().split())) for _ in range(D)]
comp_ans_ll = [0 for _ in range(D) ]
n_ans=float("inf")

def main():
  global n_ans
  for i in range(1<<D):
    comp_ans_l = [0 for _ in range(D) ]
    score = 0
    tmp_n_ans = 0
    for j in range(D):
      if (i>>j)&1:
        score += (j+1)*100*PC[j][0] + PC[j][1]
        tmp_n_ans+=PC[j][0]
        comp_ans_l[j] = 1
    if G <= score:
      n_ans = min(n_ans, tmp_n_ans)
    else:
      for k in range(D-1,-1,-1):
        if comp_ans_l[k]==0:
          for l in range(1,PC[k][0]):
            score += 100*(k+1)
            tmp_n_ans+=1
            if G <= score:
              n_ans = min(n_ans, tmp_n_ans)
              break
        if score>=G:
          break
  print(n_ans)

if __name__=="__main__":
  main()

Submission status: Accepted

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

ans = 10**12

for i in range(2**D):
    ten = 0
    mon = 0
    keta = format(i, "0"+str(D)+"b")
    for j in range(D):
        if keta[j] == "1":
            ten += pc[j][0]*(j+1)*100 + pc[j][1]
            mon += pc[j][0]
    if ten < G:
        for j in range(D-1, -1, -1):
            if keta[j] == "0":
                for k in range(pc[j][0]):
                    ten += (j+1) * 100
                    mon += 1
                    if ten >= G:
                        break
                if ten >= G:
                    break
    if ten >= G:
        ans = min(ans, mon)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

D, G = map(int, input().split())
PC = []
for i in range(D):
    p, c = map(int, input().split())
    total = ((i + 1) * 100) * p + c
    PC.append([p, c, total])

A = []
B = {i for i in range(D)}
for i in range(D+1):
    A += list(combinations(B, i))

# print(A)

ans = []
for ai in A:
    p = 0  # ポイント
    c = 0  # 問題数
    for aii in ai:
        p += PC[aii][2]
        c += PC[aii][0]
    if p < G:
        x = B.difference(ai)
        max_x = max(x)
        cnt = 0
        while p < G and cnt < PC[max_x][0] - 1:
            p += (max_x + 1) * 100
            cnt += 1
            c += 1
        if p >= G:
            # ans.append([p, c])
            ans.append(c)
    else:
        # ans.append([p, c])
        ans.append(c)

print(min(ans))

Submission status: Accepted

Solution code:
from itertools import combinations

D, G = map(int, input().split())
PC = []
for i in range(D):
    p, c = map(int, input().split())
    total = ((i + 1) * 100) * p + c
    PC.append([p, c, total])

A = []
B = {i for i in range(D)}
for i in range(D+1):
    A += list(combinations(B, i))

# print(A)

ans = []
for ai in A:
    p = 0  # ポイント
    c = 0  # 問題数
    for aii in ai:
        p += PC[aii][2]
        c += PC[aii][0]
    if p < G:
        x = B.difference(ai)
        max_x = max(x)
        cnt = 0
        while p < G and cnt < PC[max_x][0]:
            p += (max_x + 1) * 100
            cnt += 1
            c += 1
        if p >= G:
            # ans.append([p, c])
            ans.append(c)
    else:
        # ans.append([p, c])
        ans.append(c)

print(min(ans))

Submission status: Accepted

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

answer = float('inf')
# bit全検索
for bit in range(2 ** D):
    score = 0
    count = 0
    remain = set(range(D))
    for i in range(D):
        if (bit >> i) & 1:
            # フラグが立っている時、その問題を全て解く
            score += PC[i][1] + PC[i][0]*100*(i+1)
            count += PC[i][0]
            remain -= {i}
    
    if score < G :
        use = max(remain)
        # nは難問解くか
        n = min(-(-(G-score)//((use+1)*100)), PC[use][0])
        count += n
        score += n * (use+1) * 100
    if score >= G:
        answer = min(answer, count)

print(answer)

Submission status: Accepted

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

def dfs(i, count, score, remain):
    global answer
    if i == D:
        if score < G:
            use = max(remain)
            n = min(-(-(G-score)//((use+1)*100)), PC[use][0])
            score += 100*n*(use+1)
            count += n
        if score >= G:
            answer = min(answer, count)
    else:
        dfs(i+1, count, score, remain)
        dfs(i+1, count+PC[i][0], score+PC[i][0]*100*(i+1) + PC[i][1], remain-{i})

answer = float('inf')
dfs(0, 0, 0, set(range(D)))
print(answer)

Submission status: Accepted

Solution code:
import sys
from math import ceil
inputs = sys.stdin.readlines()

d, g = map(int, inputs[0].split())
P = list(map(int, map(lambda x: x.split()[0], inputs[1:])))
C = list(map(int, map(lambda x: x.split()[1], inputs[1:])))

ans = float('inf')
for bit in range(1 << d):
    count, total, rest = 0, 0, set(range(1, d+1))
    for i in range(d):
        if bit & (1 << i):
            total += P[i] * (i + 1) * 100 + C[i]
            count += P[i]
            rest.discard(i + 1)

    if total < g:
        use = max(rest)
        n = ceil((g - total) / (use * 100))
        if P[use-1]-1 < n:
            continue
        count += n
        total += n * use * 100
        
    if total >= g:
        ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import ceil
inputs = sys.stdin.readlines()

d, g = map(int, inputs[0].split())
P = list(map(int, map(lambda x: x.split()[0], inputs[1:])))
C = list(map(int, map(lambda x: x.split()[1], inputs[1:])))

ans = float('inf')
for bit in range(1 << d):
    count, total, rest = 0, 0, set(range(1, d+1))
    for i in range(d):
        if bit & (1 << i):
            total += P[i] * (i + 1) * 100 + C[i]
            count += P[i]
            rest.discard(i + 1)

    if total < g:
        use = max(rest)
        n = min(P[use-1], ceil((g - total) / (use * 100)))
        count += n
        total += n * use * 100
    if total >= g:
        ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
p_and_c = [list(map(int, input().split())) for _ in range(d)]
min_number = 1000
for i in range(2**d):
    score = 0
    number = 0
    p_and_c_copy = p_and_c.copy()
    rest_num = set(range(1, d+1))
    for j in range(d):
        if i & (1 << j):
            number += p_and_c_copy[j-d][0]
            score += p_and_c_copy[j-d][1] + 100 * (j+1) * p_and_c_copy.pop(j-d)[0]
            rest_num.discard(j+1)
    if p_and_c_copy:
        for k in range(p_and_c_copy[-1][0]):
            if score >= g:
                break
            score += 100 * max(rest_num)
            number += 1
        else:
            continue
    min_number = min(min_number, number)
print(min_number)

Submission status: Accepted

Solution code:
import math

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

# あるグループの問題をコンプすると、1問あたりの得点が実質100i+ci/pi点となる
# 各グループの問題について、コンプするかしないか全通り試す
# このボーナス込みの1問あたりの得点が大きい所から貪欲に解けばよい

point_per_q_including_bonus = [(100*idx + c[idx])/p[idx] for idx in range(D)]

sum_n_solve_list = []

for bit in range(2**D):
    comp_group_flag = []
    for idx in range(D):
        if ((bit>>idx) & 1):
            comp_group_flag.append(1)
        else:
            comp_group_flag.append(0)
    point_per_q = [100*(idx+1) + c[idx]/p[idx] if comp_group_flag[idx] == 1 else 100*(idx+1) for idx in range(D)]
    pointIDX = zip(point_per_q, comp_group_flag, p)
    pointIDX = sorted(pointIDX, reverse = True, key = lambda x: x[0])
    score = 0
    sum_n_solve = 0
    group = 0
    while score < G and group < D:
        if pointIDX[group][1] == 1:
            n_solve = pointIDX[group][2]
            sum_n_solve += n_solve
            score += pointIDX[group][0] * n_solve
            group += 1
        else:
            # コンプしないので最大でもグループに含まれる問題の数-1までしか解けないことに注意
            n_solve = min(math.ceil((G-score)/pointIDX[group][0]), pointIDX[group][2]-1)
            sum_n_solve += n_solve
            score += pointIDX[group][0] * n_solve
            group += 1
    if score >= G:
        sum_n_solve_list.append(sum_n_solve)

print(min(sum_n_solve_list))

Submission status: Accepted

Solution code:
def main():
    D, G = (int(i) for i in input().split())
    pc = [[int(i) for i in input().split()] for j in range(D)]
    ans = 10**6
    for bit in range(1<<D):
        completed = []
        for i in range(D):
            if bit & (1<<i):
                completed.append(i)
        score = 0
        solve = 0
        for c in completed:
            score += 100*(c+1)*pc[c][0] + pc[c][1]
            solve += pc[c][0]
        for i in range(D)[::-1]:
            if i in completed:
                continue
            less = max(G - score,0)
            if 100*(i+1)*pc[i][0] < less:
                break
            from math import ceil
            solve += ceil(less / (100*(i+1)))
            score += 100*(i+1)*solve
        else:
            ans = min(ans, solve)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ret = float('inf')
for i in range(2 ** D) :
    g = G
    last = 0
    count = 0
    for j in range(D) :
        if i % 2 == 0 :
            last = j
        else :
            g -= pc[j][0] * (j + 1) * 100 + pc[j][1]
            count += pc[j][0]
        i //= 2
    
    if pc[last][0] * (last + 1) * 100 <= g :
        continue
        
    if g <= 0 :
        ret = min(ret, count)
    else :
        count += -(-g // ((last + 1) * 100))
        ret = min(ret, count)
        
print(ret)

Submission status: Accepted

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

df = [[df[i][0], i+1, (df[i][1]//100)+(i+1)*df[i][0]] for i in range(d)]
result = 10**9
for i in range(2**d):
    counter = [0, 0, [0]]
    bin_i = format(i, 'b').zfill(d)
    for j in range(1, len(bin_i)+1):
        if bin_i[-j] == '1':
            counter[0] += df[j-1][0]
            counter[1] += df[j-1][2]
        else:
            counter[2].append(j)
    if counter[1] < g:
        j = max(counter[2])
        if g - counter[1] <= df[j-1][0]*j:
            counter[0] -= ((-1)*(g - counter[1]))//j
        else:
            counter[0] = 10**9
    result = min(counter[0], result)
print(result)

Submission status: Accepted

Solution code:
import math

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

ans = float('inf')
for bit in range(1 << D):
    count = 0
    num = 0
    rest_num = set(range(1, D+1))

    for i in range(D):
        if bit & (1 << i):
            num += P[i] * (i+1) * 100 + C[i]
            count += P[i]
            rest_num.discard(i+1)

    if num < G:
        max_num = max(rest_num)
        n = min(P[max_num-1], math.ceil((G-num)/(max_num*100)))
        count += n
        num += n * max_num * 100

    if num >= G:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

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

ans = float("inf")

for bit in range(1 << d):
    count = 0
    sum = 0
    nokori = set(range(1, d + 1))

    for i in range(d):
        if bit & (1 << i):
            sum += pc[i][0] * (i + 1) * 100 + pc[i][1]
            count += pc[i][0]
            nokori.discard(i + 1)
    
    if sum < g:
        use = max(nokori)
        n = min(pc[use-1][0], -(-(g - sum) // (use * 100)))
        count += n
        sum += n * use * 100

    if sum >= g:
        ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
probs = []
ans = float('inf')
for i in range(d):
    p,c =map(int,input().split())
    probs.append(((i+1)*100,p,c))

for i in range(2**d):
    count = 0
    score = 0
    yet = []
    for j in range(d):
        if ((i >>j) & 1):
            count +=probs[j][1]
            score +=probs[j][2] +probs[j][0]*probs[j][1]
        else:
            yet.append((probs[j][0],probs[j][1]-1))
    if ans <= count:
        continue
    elif score>=g:
        ans = count
        continue
    yet.sort(reverse=True)
    if score+sum([x*y for x,y in yet]) <g:
        continue
    for point,num in yet:
        solve = min((g - score-0.1)//point +1,num)
        count += solve
        score += solve*point
        if count >= ans:
            break
        if score >=g:
            ans = count
            break
    
print(int(ans))

Submission status: Accepted

Solution code:
import math


def dfs(sc, i=0, qn=0, used=set()):
    if sc <= 0:
        return qn
    if i == d:
        i -= 1
        while i in used:
            i -= 1
        hanpa = math.ceil(sc / (100 * (i + 1)))
        if hanpa >= pc[i][0]:
            return inf
        return qn + hanpa
    p, c = pc[i]
    zenbu = (i + 1) * 100 * p + c
    used.add(i)
    re1 = dfs(sc - zenbu, i + 1, qn + p, used)
    used.remove(i)
    re2 = dfs(sc, i + 1, qn, used)
    return min(re1, re2)


inf = 10 ** 9
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
print(dfs(g))