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:
import math

def solve():
    [D,G] = [int(x) for x in input().split()]
    P = []
    C = []
    for _ in range(D):
        [p,g] = [int(x) for x in input().split()]
        P.append(p)
        C.append(g)

    LIM = 1 << D
    ans = 10**12  # INF 
    for bits in range(LIM):
        score = 0
        count = 0
        for i in range(D):
            maxi = -1
            if (bits >> i) & 1 == 1:
                # use all
                # print("useall", i, P[i])
                score += P[i] * 100 * (i+1) + C[i]
                count += P[i]

        if G <= score:
            # print("ans, count", ans, count)
            ans = min(ans, count)
            continue

        # use 中途半端
        for i in range(D):
            if (bits >> i) & 1 != 1:
                n = (G-score) / ((i+1)*100)
                # print("n", n)
                if n >= P[i]:
                    continue

                n = int(math.ceil(n))
                # print("cn", count + n)
                ans = min(ans, count + n)
    # print(ans)
    return ans


print(solve())

Submission status: Accepted

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

def dfs(g, i):
    if i == 0:
        return 10 ** 12
    
    n = min(g // (100 * i), pc[i][0])
    score = n * 100 * i
    
    if n == pc[i][0]:
        score += pc[i][1]
        
    if g > score:
        n += dfs(g - score, i - 1)
        
    return min(n, dfs(g, i - 1))

print(dfs(g, d))

Submission status: Accepted

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

def dfs(g, i):
    if i == 0:
        return 10 ** 12
    n = min(g // (100 * i), pc[i][0])
    score = 100 * i * n
    if n == pc[i][0]:
        score += pc[i][1]
    if g > score:
        n += dfs(g - score, i - 1)
    return min(n, dfs(g , i - 1))

print(dfs(g, d))

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p = []
c = []
PC = [0] + [list(map(int, input().split())) for _ in range(D)]
 
def dfs(G, i):
    if i == 0:
        return 10**12
    n = min(G // (100 * i), PC[i][0])
    tmp = n*100*i
    if n == PC[i][0]:
        tmp += PC[i][1]
    if tmp < G:
        n += dfs(G-tmp, i-1)
    return min(n, dfs(G, i-1))
 
print(dfs(G, D))

Submission status: Accepted

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

complete=[None]*d
for i in range(d):
  complete[i] = info[i][0]*(100*i+100) + info[i][1]
  #print(complete[i])

ans = 1000

for i in range(2**(d)):
  bin_i = str("0"*(d+2-len(bin(i)))+str(bin(i))[2:])
  #print(bin_i)
  
  summation=0
  count=0
  index_0=-1
  
  for j in range(d):
    if bin_i[j]=="1":
      summation += complete[j]
      count +=info[j][0]
    else:
      index_0 = j
      
  if summation >= g:
    ans = min(ans,count)
  elif summation < g:
    tmp_g = g
    for j in range(info[index_0][0]):
      tmp_g = tmp_g-100*(index_0+1)
      count +=1
      if summation >= tmp_g:
        ans = min(ans,count)
        break
  #print(count)
  
print(ans)

Submission status: Accepted

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

def main():
    na = list(map(int, input().split()))
    D, G = na[0], na[1]
    p = []
    c = []
    ts = []
    for i in range(D):
        na = list(map(int, input().split()))
        p.append(na[0])
        c.append(na[1])
        ts.append(100 * (i + 1) * na[0] + na[1])

    max_i = 2 ** D
    min_q = 1000
    for i in range(max_i):
        q = 0
        s = 0
        max_uc = -1
        for j in range(D):
            if i & (2 ** j) != 0:
                q += p[j]
                s += ts[j]
            else:
                max_uc = j
        if G <= s:
            min_q = min(min_q, q)
        elif G <= s + 100 * (max_uc + 1) * (p[max_uc] - 1):
            min_q = min(min_q, q + math.ceil((G - s) / 100 / (max_uc + 1)))

    print(min_q)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


# mathを使わない切り上げ
def ceil(n, m):
    return -(-n//m)


d, g = LI()
contest = [LI() for _ in range(d)]

ans = INF

# Bit全探索
for bit in range(1 << d):
    score = 0
    cnt = 0
    remain_max = -1

    # 各bitが立っているか確認
    for i in range(d):
        if bit >> i & 1:
            score += contest[i][0] * (i + 1) * 100 + contest[i][1]
            cnt += contest[i][0]
            continue
        # コンプリートしなかった問題の中で最も得点の高い問題をメモ
        remain_max = i

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

    need = ceil((g - score) // 100, remain_max + 1)

    if need >= contest[remain_max][0]:
        continue

    ans = min(ans, cnt + need)

print(ans)

Submission status: Accepted

Solution code:
import math as m
D,G = map(int, input().split())
info = [list(map(int, input().split())) for i in range(D)]
def bfs(list_hoge=[[0,[]]],depth=0):
    queue = []
    for e in list_hoge:
        for b in [0,1]:
            if b == 0:
                score = e[0]
                copy = e[1][:]
                queue.append([score,copy])
            elif b == 1:
                score = e[0] + 100*(depth+1)*info[depth][0] + info[depth][1]
                copy = e[1][:]
                copy.append(depth)
                queue.append([score,copy])
    list_hoge = queue[:]
    if depth == len(info)-1:
        return list_hoge
    return bfs(list_hoge,depth+1)
res = bfs()
ans = float("inf")
for e in res:
    solved = 0
    for i in range(len(e[1])):
        solved += info[e[1][i]][0]
    if e[0] >= G:
        if solved < ans:
            ans = solved
        continue
    for i in range(D-1,-1,-1):
        if not i in e[1]:
            nec = G-e[0]
            haiten = 100*(i+1)
            add_solve = m.ceil(nec/haiten)
            total_solved = solved + m.ceil(nec/haiten)
            if add_solve >= info[i][0]:
                break
            if total_solved < ans:
                ans = total_solved
print(ans)

Submission status: Accepted

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

for j in range(2 ** D):
    check = 0
    con = 0
    rest = -1
    for i in range(D):
        p, c = cp[i]
        if j & (2**i):
            check += p * 100 * (i + 1) + c
            con += p
        else:
            rest = i

    if G <= check:
        ans.append(con)
    else:
        p1 = 100 * (rest + 1)
        pn = cp[rest][0] - 1
        for i in range(pn + 1):
            if G <= check + p1 * i:
                ans.append(con + i)
                break
print(min(ans))

Submission status: Accepted

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

from itertools import product
from math import ceil

INF = 99999999999999999999999999

def main():
    d, g = map(int, input().split())
    pcs = []
    for i in range(d):
        p, c = map(int, input().split())
        pcs.append((p, c))
    comps = product((False, True), repeat=d)
    mi = INF
    for comp in comps:
        so = minimum_solution_g(d, g, pcs, comp)
        mi = min(mi, so)
    print(mi)

def minimum_solution_g(d, g, pcs, comp):
    score = 0
    used = 0
    avail = []
    for i in range(d):
        if comp[i]:
            score += pcs[i][1] + (i + 1) * 100 * pcs[i][0]
            used += pcs[i][0]
            avail.append(0)
        else:
            avail.append(pcs[i][0] - 1)
    for i in reversed(range(d)):
        if score >= g:
            break
        score_one = (i + 1) * 100
        use = min(avail[i], int(ceil((g - score) / score_one)))
        assert use >= 0
        used += use
        score += score_one * use
    if score >= g:
        return used
    else:
        return INF

main()

Submission status: Accepted

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

for i in range(D):
    tmpp,tmpd = (int(i) for i in input().split())
    p.append(tmpp)
    c.append(tmpd)

#まずはコンプ部分の点数を計算する
#コンプ報酬+基本スコア*問題数
comp = [100*(i+1)*p[i]+c[i] for i in range(D)]

#現時点では全問解かないと
#目標達成できないとする
ans = sum(p)

#D桁の2進数bを使ってコンプする問題を指定する
#00001=>100点問題をコンプする
b=[0]*D
while True:
    #コンプ部分のスコア
    score = sum([comp[i]*b[i] for i in range(D)])
    #この時点での問題数
    probCount = sum([p[i]*b[i] for i in range(D)])

    #目標達成までハイスコア問題を加算
    #まずはハイスコア問題はどれか
    hi = 'None' #全部コンプ問題としておく
    for i in range(D):
        k = D-i-1
        if b[k]==0:
            hi = k
            break
    #目標達成まで加算（コンプしても達成しない場合もある
    if hi != 'None':
        for i in range(p[k]):
            if score >=G:
                break
            else:
                score += 100*(hi+1)
                probCount += 1

    #目標達成なら現時点の最小問題数と比較
    if score>=G and ans > probCount:
        ans = probCount

    #全部コンプまでやったら終了
    if all(b):
        break
    
    #bに1を加算
    for i in range(D):
        if b[i]==0:
            for j in range(i):
                b[j]=0
            b[i]=1
            break
    
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
p = []
c = []
ans = 1000000

for i in range(d):
    a, b = map(int, input().split())
    p.append(a)
    c.append(b)

for i in range(1 << d):
    select = []
    for j in range(d):
        if ((i >> j) & 1) == 1:
            select.append(j)

    tans = 0
    npoint = g

    for j in select:
        tans += p[j]
        npoint -= c[j]
        npoint -= (j + 1) * 100 * p[j]

    slv = 0
    slvj = 0
    # selectに入っていない問題の中で得点が最も大きいものを求める
    for j in range(d - 1, -1, -1):
        if j in select:
            continue
        slvj = j
        break

    while npoint > 0:  # 必要なポイントを獲得するまで
        # 1問ずつとく
        slv += 1
        npoint -= (slvj + 1) * 100

    # 存在する100*j点問題の数より解いた問題が多いことになっているとき、
    # この組み合わせはあり得ない
    if slv > p[slvj]:
        continue

    tans += slv
    ans = min(ans, tans)
print(ans)

Submission status: Accepted

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


def dfs(G, i):
    if i == 0:
        return 10**12
    n = min((G-1)//(100*i)+1, PC[i][0])
    #n = min(G//(100*i), PC[i][0])
    tmp = n*100*i
    if n == PC[i][0]:
        tmp += PC[i][1]
    if tmp < G:
        n += dfs(G-tmp, i-1)
    return min(n, dfs(G, i-1))

print(dfs(G, D))

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
P = []
C = []
for i in range(D) :
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)
ans = float("inf")
for bit in range(1 << D) :
    AC = 0
    SCORE = 0
    for k in range(D) :
        if bit & (1 << k) :
            AC += P[k]
            SCORE += (k+1)*100*P[k]+C[k]
    if SCORE >= G :
        ans = min(ans,AC)
    else :
        for k in range(D-1,-1,-1) :
            if bit & (1 << k) :
                continue
            rest = G - SCORE
            if rest > (k+1)*100*P[k]+C[k] :
                AC += P[k]
                SCORE += (k+1)*100*P[k]+C[k]
            else :
                AC += rest//((k+1)*100)
                if rest % ((k+1)*100) :
                    AC += 1
                ans = min(ans,AC)
                break
print(ans)

Submission status: Accepted

Solution code:
ranknum,goal = map(int,input().split())
probnum = [0]*ranknum
bonus = [0]*ranknum
compscore = [0]*ranknum

for i in range(ranknum):
    probnum[i],bonus[i] = map(int,input().split())
    compscore[i] = probnum[i]*100*(i+1)+bonus[i]

from itertools import product
from math import ceil

minprob = 1001

for c in product(range(2),repeat=ranknum):
    score = 0
    solvedprob = 0
    notcompedindex = -1

    for i in range(ranknum):    
        if c[i] == 1:
            score += compscore[i]
            solvedprob += probnum[i]
        else:
            notcompedindex = i
        
    if score < goal and score+100*(notcompedindex+1)*(probnum[notcompedindex]-1) >= goal:
        solvedprob += ceil((goal-score)/(100*(notcompedindex+1)))
        score += ceil((goal-score)/(100*(notcompedindex+1))) * (100*(notcompedindex+1))
    
    if score >= goal:
        minprob = min(minprob,solvedprob)

print(minprob)

Submission status: Accepted

Solution code:
D,G = [int(s) for s in input().split()]
data = [[0 for i in range(3)] for j in range(D)]
s = []
for i in range(D):
    data[i][0] = (i+1)*100
    data[i][1],data[i][2] = [int(s) for s in input().split()]
data.reverse()

for i in range(1 << D):
    fl = False
    seq = 0
    sum = 0
    ##bitで1になるものを探索##
    for j in range(D):
        if ((i >> j) & 1) == 1:
            sum += data[j][0]*data[j][1] + data[j][2]
            seq += data[j][1]
    if sum < G:
        ##bitで0になるものを探索##
        for j in range(D):
            ##0になったらgreedyに解いていく##
            if ((i >> j) & 1) == 0:
                for k in range(data[j][1]):
                    if sum >= G:
                        fl = True
                        break
                    sum += data[j][0]
                    seq += 1
                if fl:break
    s.append(seq)
    
        
    
print(min(s))

Submission status: Accepted

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

k = [list(map(int, input().split())) for i in range(d)]
l = []
for i in range(1, d + 1):
    l.append(k[-i])
k = l
#k.sort(key=lambda x:(-x[1]))
#A = [0, 1, 2, 3]の部分集合を全て出力する
#A = [0, 1, 2, 3]
combined1 = []
for i in range(d):
    combined1.append([k[i][0] * (d - i) * 100 + k[i][1]])
ansli = []
for i in range(1 << d):
    output = []
    ot = []
    for j in range(d):
        if ((i >> j) & 1) == 1:
            output.append(k[j] + combined1[j])
            ot.append(j)
    #print(output)
    sum = 0
    anscnt = 0
    for m in output:
        sum += m[2]
        anscnt += m[0]
    if sum >= g:
        ansli.append(anscnt)
    else:
        for v in range(d):
            if v not in ot:
                diffyen = g - sum
                tmp = (diffyen + 100 * (d - v) - 1) // (100 * (d - v))
                if tmp < k[v][0]:
                    ansli.append(anscnt + tmp)
                break
print(min(ansli))

Submission status: Accepted

Solution code:
import numpy as np
import itertools
import math

D, G = tuple(map(int, input().split()))

p_c_list = np.array([tuple(map(int, [100 * (i + 1)] + input().split())) for i in range(D)])

masks = itertools.product([False, True], repeat=len(p_c_list))

ret = np.inf
for mask in masks:
  maskedarr = p_c_list[np.array(mask), :]
  comp_sum = (maskedarr[:, 0] * maskedarr[:, 1] + maskedarr[:, 2]).sum()
  suc_num = maskedarr[:, 1].sum()
  if comp_sum < G:
    amari = (G - comp_sum) / p_c_list[~np.array(mask), 0][-1]
    if amari < p_c_list[~np.array(mask), 1][-1]:
      if ret > suc_num + amari:
        ret = suc_num + amari
    else:
      continue
  elif suc_num < ret:
    ret = suc_num
  else:
    continue
    
print(int(math.ceil(ret)))

Submission status: Accepted

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

ans = float("inf")
for bit in range(1 << D) :
    AC = 0
    score = 0
    for k in range(D) :
        if bit & (1 << k) :
            score += 100*(k+1)*L[k][0]+L[k][1]
            AC += L[k][0]
    if score >= G :
        ans = min(ans,AC)
        continue
    for k in range(D-1,-1,-1) :
        if bit & (1 << k) :
            continue
        if (score + 100*(k+1)*L[k][0]) < G :
            score += 100*(k+1)*L[k][0]
            AC += L[k][0]
        else :
            res = G - score
            while res > 0 :
                res -= 100*(k+1)
                AC += 1
            ans = min(ans,AC)
            break
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
pc = [list(map(int,input().split())) for _ in range(d)]
res = 10**10
for bit in range(1 << d):
    score = 0
    prob = 0
    used = [False] * d
    for i in range(d):
        if bit & 1:
            used[i] = True
            score += pc[i][1]
            score += (i + 1) * 100 * pc[i][0]
            prob += pc[i][0]
        bit >>= 1
    dd = []
    for i in range(d-1,-1,-1):
        if not used[i]:
            dd.append([(i+1) * 100, pc[i][0]])
    pivot = 0
    flag = True
    while score < g:
        if pivot == len(dd):
            flag = False
            break
        if dd[pivot][1] == 0:
            pivot += 1
            continue
        else:
            score += dd[pivot][0]
            prob += 1
            dd[pivot][1] -= 1
    if not flag:
        continue
    res = min(res, prob)
print(res)

Submission status: Accepted

Solution code:
ranknum, goal = list(map(int, input().split()))
probnum = [0] * ranknum
bonus = [0] * ranknum
compscore = [0] * ranknum

for i in range(ranknum):
    probnum[i], bonus[i] = list(map(int, input().split()))
    # 各ランクをコンプした場合に得られる得点をcompscoreに格納しておく。
    compscore[i] = 100 * (i + 1) * probnum[i] + bonus[i]

from itertools import product
from math import ceil

# 得点Gを達成する最小の問題正解数minprobを初期化。前提により必ず1000以下になるので、1001で初期化しておく。
minprob = 1001

# 各ランクの問題をコンプするか否かの2^ranknum通りをループ処理する。
for c in product(range(2), repeat=ranknum):
    score = 0
    solvedprob = 0
    notcompedindex = -1

    # コンプした問題について、得点をcompscoreに、正解数をsolvedprobnumに格納する。
    for i in range(ranknum):
        if c[i] == 1:
            score += compscore[i]
            solvedprob += probnum[i]
        # コンプされていないランクのインデックスのうち最大のものをnotcompedindexに格納しておく。
        else:
            notcompedindex = i

    # コンプした問題だけでgoalに達さず、かつ、コンプしていない最高ランクの問題をコンプ寸前まで解けばゴールに達する場合、
    # ゴールをぎりぎり達成するところまで正解した状態へと、scoreとsolvedprobを更新する。
    if score < goal and score + 100 * (notcompedindex + 1) * (probnum[notcompedindex] - 1) >= goal:
        solvedprob += ceil((goal - score) / (100 * (notcompedindex + 1)))
        score += ceil((goal - score) / (100 * (notcompedindex + 1))) * 100 * (notcompedindex + 1)

    # 最終的にゴールを達成している場合、正解数が暫定最小ならば、それをminprobに格納しておく。
    if score >= goal:
        minprob = min(minprob, solvedprob)

print(minprob)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
g //= 100
problems = []
for i in range(d):
    p, c = map(int, input().split())
    problems.append((i + 1, p, c // 100))

min_c = float('inf')
for i in range(2**d):
    cnt = 0
    score = 0
    for j in range(d):
        if 1 << j & i:
            cnt += problems[j][1]
            score += problems[j][0] * problems[j][1] + problems[j][2]
    if score >= g:
        min_c = min(min_c, cnt)
    for j in range(d):
        if not (1 << j & i):
            need = max(0, (g - score + problems[j][0] - 1) // problems[j][0])
            if problems[j][1] >= need:
                min_c = min(min_c, cnt + need)
print(min_c)

Submission status: Accepted

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

p = [None] * D
c = [None] * D

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

cnt = 100000
for i in range(1 << D):
    num = -1
    score = 0
    cnt_ = 0
    for j in range(D):
        if (i >> j) % 2 == 1:
            score += p[j] * 100 * (j+1) + c[j]
            cnt_ += p[j]
        else:
            num = j
    if score >= G:
        cnt = min(cnt, cnt_)
    else:
        if num == -1:
            pass
        else:
            n = p[num]
            while n > 0:
                n -= 1
                score += (num+ 1) * 100
                cnt_ += 1
                if score >= G:
                    cnt = min(cnt, cnt_)
                    break
print(cnt)

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(int, input().split())
ans = []
def greedy(count,comp,diff):
    ret = -1
    for i in range(d-1,-1,-1):
        if not(i in comp):
            if (p[i]-1)*(i+1)*100 >= diff:
                ret = count + diff//((i+1)*100) + (diff % ((i+1)*100) != 0)
                break
    return ret

def search(i,score,count,comp):
    if i == d:
        if score >= g:
            ans.append(count)
            return
        res = greedy(count,comp,g - score)
        if res != -1:
            ans.append(res)
    else:
        search(i+1,score,count,comp)
        comp.append(i)
        search(i+1,score+p[i]*(i+1)*100+c[i],count+p[i],comp)
search(0,0,0,[])
print(min(ans))

Submission status: Accepted

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

ans = float("inf")
for bit in range(2 ** D) :
    score = 0
    AC = 0
    for k in range(D) :
        if bit & (1 << k) :
            p,c = L[k]
            score += c
            AC += p
            score += p*(k+1)*100
    if score >= G :
        ans = min(ans,AC)
        continue
    for k in range(D-1,-1,-1) :
        if bit & (1 << k) :
            continue
        p,c = L[k]
        if (score + p*(k+1)*100) < G :
            score += p*(k+1)*100
            AC += p
        else :
            rem = G - score
            AC += rem // ((k+1)*100)
            if rem % ((k+1)*100) != 0 :
                AC += 1
            ans = min(ans,AC)
            break
print(ans)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
P = []
C = []
for i in range(D) :
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)
ans = float("inf")
for i in range(1 << D) : # 2**D
    ct = 0 #cost
    score = 0
    for j in range(D) :
        if (i >> j) & 1 : #bit全探索
            score += C[j] #bonus
            score += P[j] * (j+1) * 100 #normal
            ct += P[j] #cost
    for j in range(D-1,-1,-1) : #降順
        if score >= G : 
            break
        if (i >> j) & 1 : #すでに計算された得点帯を除外
            continue
        g = (j+1)*100
        got = (G-score)//g
        score += min(got,P[j])*g
        ct += min(got,P[j])
    ans = min(ans, ct)
print(ans)

Submission status: Accepted

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

ans = float("inf")
for i in range(1 << D) :
    ct = 0
    score = 0
    for j in range(D) :
        if i >> j&1 :
            score += C[j]
            score += P[j] * (j+1) * 100
            ct += P[j]
    for j in range(D-1, -1, -1) :
        if i >> j&1 :
            continue
        if score >= G :
            break
        g = (j+1)*100
        got = (G-score+g-1)//g
        score += min(got, P[j])*g
        ct += min(got, P[j])
    ans = min(ans, ct)
print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
A=[]
for i in range(D):
    p,c=map(int,input().split())
    A.append([p,c])
a=10**9
for j in range(2**D):
    b=format(j, 'b')
    B="0"*(D-len(b))+str(b)
    S=[]
    N=[]
    for k in range(D):
        S.append((A[k][0]*(k+1)*100+A[k][1])*int(B[-k-1]))
        N.append(A[k][0]*int(B[-k-1]))
        if sum(S)>=G:
            s=sum(N)
            if a>s:
                a=s
        else:
            for l in range(D):
                if B[l]=="0" and (G-sum(S))<=((D-l)*100)*(A[-l-1][0]-1):
                    s=sum(N)+((G-sum(S))//((D-l)*100))+min(1,((G-sum(S))%((D-l)*100)))
                    if a>s:
                        a=s
                    break
print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

N=10**6
dp= [  float("inf") for i in range(N+1) ]
dp[0]=0

for idx, x  in enumerate(P):
	m=idx+1	#money
	p,c=x[0], x[1]/100
	for i in range(N,-1,-1):
		if dp[i]!=float("inf"):
			for j in range(p,-1,-1):	# j= problems count   , idx = index
				if j==p:
					dp[i+m*j+c]=min( dp[i+m*j+c] , dp[i]+j )
				else:
					dp[i+m*j]=min( dp[i+m*j] , dp[i]+j )



ans=float("inf")

for i in range(G/100,N):
	ans=min(ans, dp[i])

print ans

Submission status: Accepted

Solution code:
from collections import defaultdict

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

N=10**6
dp= [  float("inf") for i in range(N+1) ]
dp[0]=0

for idx, x  in enumerate(P):
	m=idx+1	#money
	p,c=x[0], x[1]/100
	for i in range(N,-1,-1):
		if dp[i]!=float("inf"):
			for j in range(p,-1,-1):	# j= problems count   , idx = score of a problem
				if j==p:
					dp[i+m*j+c]=min( dp[i+m*j+c] , dp[i]+j )
				else:
					dp[i+m*j]=min( dp[i+m*j] , dp[i]+j )



ans=float("inf")

for i in range(G/100,N):
	ans=min(ans, dp[i])

print ans

Submission status: Accepted

Solution code:
from collections import defaultdict

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

N=10**6
dp= [   [ float("inf") for i in range(N+1)] for idx in range(D+1)  ]
dp[0][0]=0

for idx, x  in enumerate(P):
	m=idx+1	#money
	p,c=x[0], x[1]/100
	for i in range(N,-1,-1):
		if dp[idx][i]!=float("inf"):
			for j in range(p,-1,-1):	# j= problems count   , idx = score of a problem
				if j==p:
					dp[idx+1][i+m*j+c]=min( dp[idx+1][i+m*j+c] , dp[idx][i]+j )
				else:
					dp[idx+1][i+m*j]=min( dp[idx+1][i+m*j] , dp[idx][i]+j )


ans=float("inf")

for i in range(G/100,N):
	ans=min(ans, dp[-1][i])

print ans

Submission status: Accepted

Solution code:
def lastjudge(L, i, G):
  mi = 1000
  for j in L:
    if j[4] == 0:
      if j[3] < G:
        continue
      elif j[3] - j[1] > G:
        t = -(-G // j[2])
      else:
        t = j[0]
      if mi > t:
        mi = t
  return mi
def judge(L, i, G):
  if i+1 < len(L):
    m = judge(L, i+1, G)
    if L[i][3] >= G:
      if L[i][3] - L[i][1] > G:
        t = -(-G // L[i][2])
      else:
        t = L[i][0]
    else:
      G -= L[i][3]
      L[i][4] = 1
      t = L[i][0] + judge(L, i+1, G)
    return min(t, m)
  else:
    m = lastjudge(L, i, G)
    if L[i][3] < G:
      G -= L[i][3]
      L[i][4] = 1
      t = L[i][0] + lastjudge(L, i, G)
    elif L[i][3] - L[i][1] > G:
      t = -(-G // L[i][2])
    else:
      t = L[i][0]
    return min(t, m)
 
D, G = list(map(int,input().split()))
L = []
for i in range(D):
  L.append(list(map(int, input().split())))
  L[i].append((i+1) * 100)
  L[i].append(L[i][0] * L[i][2] + L[i][1])
  L[i].append(0)
print(judge(L, 0, G))

Submission status: Accepted

Solution code:
import math
d,g = map(int,input().split())
g //= 100
p = [0 for _ in range(d)]
c = [0 for _ in range(d)]
sump = [0 for _ in range(d)]
for i in range(d):
    p[i],c[i] = map(int,input().split())
    c[i] = c[i]//100
    sump[i] = (i+1)*p[i] + c[i]

min = 10000


for i in range(1<<d):
    sum = 0
    qst = 0
    maxq = 1
    for j in range(d):
        if i>>j & 1:
            sum += sump[j]
            qst += p[j]
        elif maxq < j+1:
            maxq = j+1
    if sum + maxq*p[maxq-1] < g:
        continue
    else:
        if min > max(0,math.ceil((g-sum)/maxq)) + qst:
            min = max(0,math.ceil((g-sum)/maxq)) + qst

print(min)

Submission status: Accepted

Solution code:
from itertools import product
import math

D, G = [int(_) for _ in input().split()]

P = [0] * D
C = [0] * D
for i in range(D):
    P[i], C[i] = [int(_) for _ in input().split()]

V = []
for i in range(D):
    v = P[i] * (i + 1) * 100 + C[i]
    V.append(v)

max_P = sum(P)


def func(bit_pattern):
    score = 0
    tmp = 0
    for i in range(D):
        if bit_pattern[i]:
            score += V[i]
            tmp += P[i]

    if score >= G:
        return tmp

    res = G - score

    for i in reversed(range(D)):
        if not bit_pattern[i]:
            x = math.ceil(res / ((i + 1) * 100))
            if x < P[i]:
                return tmp + x

    return max_P


ans = max_P
for bit_pattern in product(range(2), repeat=10):

    tmp = func(bit_pattern)
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 10 ** 10
for mask in itertools.product((0, 1), repeat=D):
    myscore = 0
    soloved_num = 0
    incomplete_index = 0
    for i, j in enumerate(mask):
        if j == 0:
            incomplete_index = i
        else:
            myscore += P[i] * (i + 1) * 100 + C[i]
            soloved_num += P[i]
    if myscore < G:
        for n in range(P[incomplete_index]):
            myscore += (incomplete_index + 1) * 100
            soloved_num += 1
            if myscore >= G:
                break
    if myscore >= G:
        ans = min(ans, soloved_num)

print(ans)