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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

# 目標700点
D, G = getNM()
query = []
for i in range(D):
    p, c = getNM()
    query.append([i + 1, p, c])

ans_cnt = float('inf')

for bit in range(1 << D):
    sum = 0
    cnt = 0
    for i in range(D):
        if bit & (1 << i):
            sum += query[i][0] * query[i][1] * 100 + query[i][2]
            cnt += query[i][1]

    if sum < G:
        for j in range(D - 1, -1, -1):
            if not bit & (1 << j):
                left = G - sum
                fire = query[j][0] * 100
                opt = min(query[j][1], (left + fire - 1) // fire)
                sum += opt * query[j][0] * 100
                cnt += opt
                break

    if sum >= G:
        ans_cnt = min(ans_cnt, cnt)

print(ans_cnt)

Submission status: Accepted

Solution code:
def solve(D, G, P, C):
    ret = float('inf')
    for i in range(pow(2, D)):
        tmp_score = 0
        tmp_counter = 0
        not_selected = -1

        for j in range(D):
            if i >> j & 1:
                tmp_counter += P[j]
                tmp_score += P[j] * 100 * (j + 1) + C[j]
            else:
                not_selected = j

        if G <= tmp_score:
            ret = min(ret, tmp_counter)
            continue

        for _ in range(1, P[not_selected]):
            tmp_score += 100 * (not_selected + 1)
            tmp_counter += 1
            if G <= tmp_score:
                ret = min(ret, tmp_counter)
                break

    print(ret)

if __name__ == "__main__":
    D, G = map(int, input().split())
    P = []
    C = []

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

    solve(D, G, P, C)

Submission status: Accepted

Solution code:
def solve(D, G, P, C):
    ret = float('inf')
    for i in range(pow(2, D)):
        selected = []
        tmp_score = 0
        tmp_counter = 0
        not_selected = -1

        for j in range(D):
            if i >> j & 1:
                selected.append(j)
                tmp_counter += P[j]
                tmp_score += P[j] * 100 * (j + 1) + C[j]
            else:
                not_selected = j

        if G <= tmp_score:
            ret = min(ret, tmp_counter)
            continue

        for _ in range(1, P[not_selected]):
            tmp_score += 100 * (not_selected + 1)
            tmp_counter += 1
            if G <= tmp_score:
                ret = min(ret, tmp_counter)
                break

    print(ret)

if __name__ == "__main__":
    D, G = map(int, input().split())
    P = []
    C = []

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

    solve(D, G, P, C)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    D, G = map(int, input().split())
    question = []
    bonus = []
    for i in range(D):
        p, c = map(int, input().split())
        question.append(p)
        bonus.append(c)

    """
    決め打ち二分探索と思い込んで「x問解いて得られる最大得点」を出そうとして撃沈。。。
    結局その発想をしたところで、肝は
        ・どのボーナスを得るか
        ・ボーナスを取らない「唯一の」得点群はどれか
    なので、それなら初めからこれに着目して問題を解いたうえで、それが得点Gを超えるかどうか
    確かめた方が早い。
    """ 

    ans = sum(question)
    for state in range(1 << D):
        # ビットが立ってたら全完
        score = 0
        num = 0
        solved = set([])
        for i in range(D):
            if state & (1 << i):
                solved.add(i)
                num += question[i]
                score += 100 * (i + 1) * question[i] + bonus[i]
        if score >= G:
            ans = min(ans, num)
            continue

        # G点未満の場合は解いてない問題のうち最高得点のものを追加で解く
        last_idx = D - 1
        while last_idx in solved: last_idx -= 1
        for i in range(question[last_idx]):
            score += 100 * (last_idx + 1)
            num += 1
            if score >= G:
                ans = min(ans, num)
                break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
a,b=map(int,input().split())
l=[list(map(int,input().split())) for i in range(a)]
ans=10**20
for i in range(2**a):
  s=0
  count=0
  keep1=0
  keep2=0
  t=True
  for j in range(a):
    if i>>j &1:
      s+=l[a-1-j][0]*100*(a-j)+l[a-1-j][1]
      count+=l[a-1-j][0]
    else:
      if t:
        keep1=100*(a-j)
        keep2=l[a-1-j][0]-1
        t=False
  if s+keep1*keep2>=b:
    if s>=b:
      if ans>count:
        ans=count
    else:
      p=count+math.ceil((b-s)/keep1)
      if p<ans:
        ans=p
print(ans)

Submission status: Accepted

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

ans =  float('inf')


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

    for i in range(D):
        # if bit & (1 << D)で、bitにiが含まれているか（フラグが立っているか）を判定してくれるらしい
        #今回は、i×100点の問題を全て解く場合の処理を書く
        if bit & (1 << i):
            sum +=  100 * (i + 1) * pi[i] + ci[i]
            count += pi[i]
            nokori.discard(i + 1)

    if (sum < G ):
        use = max(nokori)
        n = min(pi[use-1], (G- sum )// (use * 100) )
        if n < 1:
            n = 1
        count += n
        sum   += n * 100 * use 

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

print(ans)

Submission status: Accepted

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

ans =  float('inf')


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

    for i in range(D):
        # if bit & (1 << D)で、bitにiが含まれているか（フラグが立っているか）を判定してくれるらしい
        #今回は、i×100点の問題を全て解く場合の処理を書く
        if bit & (1 << i):
            sum +=  100 * (i + 1) * pi[i] + ci[i]
            count += pi[i]
            nokori.discard(i + 1)

    if (sum < G ):
        use = max(nokori)
        n = min(pi[use-1], -(-(G- sum )// (use * 100) ) )
        count += n
        sum   += n * 100 * use 

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

print(ans)

Submission status: Accepted

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
d, g = ri_()
p, c = [0] * d, [0] * d
for i in range(d):
    p[i], c[i] = ri_()
ans = 1000
for bit in range(1 << d):
    pro = 0
    poi = 0
    L = []
    for i in range(d):
        if bit & (1 << i):
            pro += p[i]
            poi += p[i] * (i + 1) * 100 + c[i]
        else:
            L.append(i)
    for i in L[::-1]:
        if poi < g:
            tmp = min(p[i], -(-(g - poi) // (100 * (i + 1))))
            pro += tmp
            poi += tmp * 100 * (i + 1)
        else:
            break
    if poi >= g:
        ans = min(ans, pro)
print(ans)

Submission status: Accepted

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

ans = 1 << 60
for S in range(1 << D):
    score = 0
    num = 0
    for i in range(D):
        if (S >> i) & 1:
            score += cs[i] + ps[i] * 100 * (i + 1)
            num += ps[i]
    for i in reversed(range(D)):
        if not (S >> i) & 1:
            index = 0
            while score < G and index < ps[i]:
                score += 100 * (i + 1)
                num += 1
                index += 1
    if score >= G:
        ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
# completeするsetを決め打って考える。

from itertools import product

d, g = map(int, input().split())
ans = 10 ** 10
PC = [list(map(int, input().split())) for _ in range(d)]
kumiawase = list(product([1, 0], repeat=d))
for kumi in kumiawase:
    cnt = 0
    temp = 0
    unused = []
    for i in range(d):
        p, c = PC[i]
        if kumi[i] == 1:
            temp += (i + 1) * 100 * p
            temp += c
            cnt += p
        else:
            unused.append(((i + 1) * 100, p))
    if temp >= g:
        ans = min(ans, cnt)
    else:
        if not unused:
            continue
        remain = g - temp
        unused.sort(reverse=True)
        saidai, kaisu = unused[0]
        if remain <= (kaisu - 1) * saidai:
            cnt += (remain + saidai - 1) // (saidai)
            ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import math
# N = int(input())
D, G = [int(i) for i in input().split()]
problems = []
for i in range(D):
    p, c = [int(_) for _ in input().split()]
    bit = 0
    problems.append([p, c])

ans = 1001
for i in range(2**D):
    score = 0
    p_num = 0
    for j, p in enumerate(problems):
        if i >> j & 1:
            score += p[0] * 100 * (j + 1) + p[1]
            p_num += p[0]
    if score < G:
        rest = G - score
        for j in range(D-1, -1, -1):
            if i >> j & 1:
                continue
            n = math.ceil(rest / (100 * (j + 1)))
            if n <= problems[j][0] - 1:
                rest -= n * 100 * (j + 1)
                p_num += n
                break
            rest -= problems[j][0] * 100 * (j + 1)
            p_num += problems[j][0]
        if rest <= 0:
            ans = min(ans, p_num)
    else:
        ans = min(ans, p_num)
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
pc_=[list(map(int,input().split())) for _ in range(d)]
pc=[[(i+1)*100,pc[0],pc[1]] for i,pc in enumerate(pc_)]
n=d
ans=1000
for i in range(2**n):
  all_ac=[]
  no_ac=[]
  for j in range(n):
    if ((i>>j) & 1):#立っているビットのところで処理が走る
      all_ac.append(j)
    else:
      no_ac.append(j)
  score=sum([pc[j][2]+pc[j][0]*pc[j][1] for j in all_ac])
  n_ac=sum([pc[j][1] for j in all_ac])
  tmp=g-score
  while no_ac and tmp>0:
    a=no_ac.pop()
    i,p,c=pc[a]
    if tmp<=i*(p-1):
      n_ac+=(tmp+i-1)//i
      tmp=0
    else:
      n_ac+=p-1
      tmp-=i*(p-1)
  if tmp<=0:
    ans=min(n_ac,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    D, G = MI()
    P = []
    C = []
    for _ in range(D):
        p, c = MI()
        P.append(p)
        C.append(c)

    ans = INF
    for i in range(1 << D):
        bag = []
        cag = []
        for j in range(D):
            if (i >> j) & 1:
                bag.append(j)
            else:
                cag.append(j)
        # print(bag, cag)
        score = 0
        cnt = 0
        for b in bag:
            score += (b+1) * 100 * P[b] + C[b]
            cnt += P[b]
        # print(score, cnt, G)
        if score >= G:
            ans = min(ans, cnt)
            # print('a', ans)
        else:
            c = cag[-1]
            for i in range(P[c]):
                score += (c+1) * 100
                cnt += 1
                if score >= G:
                    ans = min(ans, cnt)
                    # print(ans)
                    break

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def resolve():
    d,g = map(int,input().split())
    pc = [list(map(int, input().split())) for _ in range(d)]
    ans = 10**9
    for i in range(2**d):
        count = 0
        total = 0
        nokori = [1 for _ in range(d)]
        for j in range(d):
            if (i>>j & 1):
                total += pc[j][0] * (j+1)* 100 + pc[j][1]
                count += pc[j][0]
                nokori[j] = 0
        if total >= g:
            ans = min(ans, count)
        else:
            for k in reversed(range(len(nokori))):
                if nokori[k] == 0:
                    continue
                else:
                    if total + (pc[k][0]-1) * (k+1) *100 >= g:
                        count += (((g-total) + (k+1)*100)-1)//((k+1)*100)
                        ans = min(ans, count)
                        break
                    else:
                        total += (pc[k][0]-1) * (k+1) *100
                        count += (pc[k][1]-1)
    print(ans)
resolve()

Submission status: Accepted

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

p, c = [], []

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

ans = 10 ** 18

for bit in range(1 << d):
    solve = 0
    score = 0
    for i in range(d):
        if bit & (1 << i):
            score += 100 * (i + 1) * p[i]
            score += c[i]
            solve += p[i]
        if score >= g:
            ans = min(ans, solve)
    else:
        if score < g:
            tmp = (1 << d) - 1
            not_bit = bit ^ tmp
            digit = 0
            while not_bit != 0:
                digit += 1
                not_bit = not_bit >> 1
            for j in range(p[digit - 1]):
                score += digit * 100
                solve += 1
                if score >= g:
                    ans = min(ans, solve)
                    break

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import math
import re
import numpy as np
import copy

S = input().split(" ")
D = int(S[0])
G = int(S[1])

p_n = []
c_n = []

for i in range(D):
    line = input().split(" ")
    p = int(line[0])
    c = int(line[1])
    p_n.append(p)
    c_n.append(c)

#十分大きい数で初期化
ans = 1000000

#ボーナス取得の有無を分配する関数（2^D通り）
def CombiBonus(flag):
    #最後まで到達した場合
    if len(flag) == D:
        #最小値の計算関数へ
        CalcMin(flag)

    else:
        #次のボーナスを取得するか否か
        non_use = flag + "0"
        use = flag + "1"
        CombiBonus(non_use)
        CombiBonus(use)

#最小回数を計算する関数
def CalcMin(flag):
    global ans

    #print(flag)

    #未回答問題数を格納するリスト
    unsolved = copy.copy(p_n)
    #現在のスコア
    score = 0
    #現在解いた問題数
    cnt = 0

    #ボーナス獲得している場合、全て解いているので反映
    for i in range(D):
        if flag[i] == "1":
            unsolved[i] = 0
            score += (i+1)*p_n[i]*100
            score += c_n[i]
            cnt += p_n[i]

    #これから解く問題の難易度
    current_d = D-1
    #スコアがG以上になるまで、難しい問題から優先して解き続ける
    while score < G:
        #2問以上残っている場合、同じ難易度のものを解く
        if unsolved[current_d] > 1:
            unsolved[current_d] -= 1
            score += (current_d+1)*100
            cnt += 1

        #そうでない場合、次の難易度へ
        else:
            current_d -= 1
            #0を下回る場合、終了
            if current_d < 0:
                return

    #print(cnt, score)

    #問題数が最小値かを判定
    if cnt < ans:
        ans = cnt

#探索
flag = ""
CombiBonus(flag)

print(ans)

Submission status: Accepted

Solution code:
import math
D,G=map(int,input().split())
PC=[list(map(int,input().split())) for i in range(D)]
zenkan=[]
def saiki(A):
    if len(A)==D:
        ans=0
        count=0
        toita=[]
        for i in range(D):
            if A[i]==1:
                ans+=PC[i][0]*(i+1)*100+PC[i][1]
                count+=PC[i][0]
                toita.append(i)
        zenkan.append([ans,count,toita])
        return ans
    for i in range(2):
        A.append(i)
        saiki(A)
        A.pop()
saiki([])
ans=[]
zenkan.sort()
for i in range(len(zenkan)):
    cost=zenkan[i][1]
    hituyo=G-zenkan[i][0]
    if zenkan[i][0]>=G:
        ans.append(cost)
        continue
    cost_kari=[]
    for j in range(D):
        if j not in zenkan[i][2]:
            if PC[j][0]*100*(j+1)>=hituyo:
                cost_kari.append(math.ceil(hituyo/(100*(j+1))))
            #print(math.ceil(hituyo/100*(j+1)),j)
    cost_kari.sort()
    if len(cost_kari)!=0:
        ans.append(cost+cost_kari[0])
    elif hituyo<=0:
        ans.append(cost)
    #print(cost_kari)
#print(zenkan)
#print(ans)
print(min(ans))

Submission status: Accepted

Solution code:
from math import ceil
from itertools import product


def main():
    d, g = map(int, input().split())
    g //= 100
    p = [0] * d
    c = [0] * d
    r = [0] * d
    for i in range(d):
        _p, _c = map(int, input().split())
        _c //= 100
        p[i] = _p
        c[i] = _c
    ans = sum(p)
    for m in product((0, 1), repeat=d):
        t = 0
        a = 0
        for i in range(d):
            if m[i] == 1:
                t += p[i] * (i + 1) + c[i]
                a += p[i]
        for i in range(d - 1, -1, -1):
            if m[i] == 1:
                continue
            pi = p[i] * (i + 1)
            if t + pi >= g:
                a += ceil(max(g - t, 0) / (i + 1))
                break
            t += pi + c[i]
            a += p[i]
        ans = min(a, ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil
def main():
    d, g = map(int, input().split())
    scoremax_set = []
    numq_set = []
    for i1 in range(1, d + 1):
        kazu, bonus = map(int, input().split())
        scoremax_set.append(i1 * 100 * kazu + bonus)
        numq_set.append(kazu)
    score_get_pat = tuple(product((1,0), repeat=d))

    inf = float('inf')
    r = inf

    for sgpe in score_get_pat:
        score = 0
        q_num = 0
        for j1, s in zip(sgpe, scoremax_set):
            score += j1 * s
        for j2, num in zip(sgpe, numq_set):
            q_num += j2 * num
        if score >= g:
            r = min(r, q_num)
        else:
            sgpe_l = [i for i, x in enumerate(sgpe) if x == 0]
            score_plus = (sgpe_l[-1]+1)*100 * (numq_set[sgpe_l[-1]] - 1)
            if score + score_plus >= g:
                q_num += ceil((g - score) / ((sgpe_l[-1]+1)*100))
                r = min(r, q_num)
    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 基本的に配点の高い問題を解いていく方が効率が良いはず
# ビット全探索、D行目の問題を全部解く場合を1, そうでないものを0とする。
ans = 10**18
from itertools import product

for bit in product((0,1), repeat=D):
    point = 0
    mondai = 0
    # (0,0) (0,1)などのビット列を生成
    for i in range(D):
        point += bit[i]*p_list[i][0]*100*(i+1)
        if bit[i] == 1:
            mondai +=p_list[i][0]
            point += p_list[i][1]
    # G-point > 0ならば、配点の高い問題を順に解いていってその時の問題数をカウントする
    if G - point > 0:
        # 最後に0となっているbitを取得
        a = [i for i, x in enumerate(bit) if x == 0]
        lastbit = int(a[-1])
        for j in range(p_list[lastbit][0]):
            point += (lastbit+1) * 100
            mondai += 1
            if (G - point <= 0):
                ans = min(ans, mondai)
                break
        # まだ G - pointが正ならば解なしで次のビット探索へ
        if G - point > 0:
            mondai = 10 ** 18

    ans = min(ans, mondai)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
import sys
import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

d,g=MI()
lis=[LI() for i in range(d)]
answers=[]
for i in product([0,1],repeat=d):
    new_lis=deepcopy(lis)
    point=0
    problems=0
    for j in range(d):
        if i[j]==1:
            point+=lis[j][1]+100*(j+1)*(lis[j][0])
            problems+=lis[j][0]
            new_lis[j][0]=0
        else:
            if new_lis[j][0]>0:
                new_lis[j][0]-=1
    #print(new_lis)
    flag=True
    for j in range(d):
        k=d-j-1
        if point>=g:
            answers.append(problems)
            flag=False
            break
        else:
            req=(g-point)//(100*(k+1))
            #print(req)
            if new_lis[k][0]>=req:
                problems+=req
                point+=req*100*(k+1)
            else:
                problems+=new_lis[k][0]
                point+=new_lis[k][0]*100*(k+1)
    if point>=g and flag==True:
        answers.append(problems)
#print(answers)
print(min(answers))

Submission status: Accepted

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

comp = [pc[i][0]*(i+1)*100+pc[i][1] for i in range(D)]

ans = 1000
for bit in range(2**D):
  solved = []
  for j in range(D):
    if 1&(bit>>j):
      solved.append(j)
  now = 0
  ps = 0
  for i in solved:
    now += comp[i]
    ps += pc[i][0]
  if now >= G:
    ans = min(ans, ps)
  else:
    for k in range(D):
      if D-k-1 in solved:
        continue
      if now + (D-k)*100*(pc[k][0]-1) >= G:
        ps += (G-now-100)//((D-k)*100) + 1
        ans = min(ans, ps)
      else:
        break
        
print(ans)

Submission status: Accepted

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

import math
ans = float('inf')
for i in range(1 << d):
    point = 0
    solved = 0

    for j in range(d):
        if (i >> j) & 1:
            point += pc[j][1] + pc[j][0] * 100 * (j + 1)
            solved += pc[j][0]

    if point >= g:
        f = True
    else:
        f = False
        for j in reversed(range(d)):
            if not ((i >> j) & 1):
                if point + (j + 1) * 100 * (pc[j][0] - 1) >= g:
                    _solved = math.ceil((g - point) / ((j + 1) * 100))
                    solved += _solved
                    point += _solved * 100 * (j + 1)
                    f = True
                    break
                else:
                    _solved = pc[j][0] - 1
                    solved += _solved
                    point += _solved * 100 * (j + 1)

    if f:
        ans = min(ans, solved)

print(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([p,c])
ans = 10 ** 18
for bit in range(2**d):
    count = 0
    sump = 0
    se = set()
    for i in range(d):
        if bit >> i & 1:
            sump += pc[i][0]*(i+1)*100 + pc[i][1]
            count += pc[i][0]
        else:
            se.add(i+1)
    if sump >=g:
        ans=min(ans,count)
    else:
        s = max(se)
        tmp = min(pc[s-1][0],((g-sump+100*s-1)//(100*s)))
        count += tmp
        sump+=tmp*s*100
        if sump>=g:
            ans=min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(d)]
from itertools import product
ans=10000
for b in product([0,1],repeat=d):
  t=0
  sc=0
  mi=0
  for i in range(d):
    if b[i]:
      t+=s[i][0]
      sc+=(s[i][1]+(i+1)*100*s[i][0])
    else:
      mi=i
  z=-(-max(0,g-sc)//((mi+1)*100))
  if z>s[mi][0]-1:
    continue
  ans=min(ans,t+z)
print(ans)

Submission status: Accepted

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

N = 10 ** 9
for bit in range(2 ** D):
    S = 0
    c = 0
    A = True
    a = -1
    for i in range(D - 1, -1, -1):
        if bit & (1 << i):
            S += (i + 1) * pc[i][0] + int(pc[i][1] / 100)
            c += pc[i][0]
        elif A:
            a = i
            A = False
    if a != -1:
        for i in range(1, pc[a][0]):
            if S >= G:
                break
            S += a + 1
            c += 1
    if S >= G:
        N = min(N, c)

print(N)

Submission status: Accepted

Solution code:
d,g=list(map(int,input().split()))
p=[list(map(int,input().split()))for i 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+=p[i][0]*(i+1)*100+p[i][1]
            count+=p[i][0]
            nokori.discard(i+1)
    if sum>=g:
        ans=min(ans,count)
    else:
        use=max(nokori)
        n=min(p[use-1][0],-(-(g-sum)//(100*use)))
        count+=n
        sum+=n*use*100
        if sum>=g:
            ans=min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
D, G = map(int, input().split())
P, C = zip(*[map(int, input().split()) for _ in range(D)])
INF = 10**18
ans = INF
for bit in product((0, 1), repeat=D):
    p = list(P)
    cnt = 0
    score = 0
    for i in range(D):
        if bit[i]:
            score += C[i]
            score += P[i]*100*(i+1)
            cnt += P[i]
            p[i] = 0
 
    if score+sum(p[i]*100*(i+1) for i in range(D)) < G:
        continue
 
    idx = D-1
    while score < G:
        while not p[idx]:
            idx -= 1
        score += 100*(idx+1)
        p[idx] -= 1
        cnt += 1
    if cnt < ans:
        ans = cnt
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import math

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

pattern = 2
ite = product(range(pattern),repeat=D)

ans = 10**5
for comb in ite:

    curr_ipcl = ipcl[:]
    curr_sum = 0
    curr_prob = 0
    for i, comp in enumerate(comb):
        if comp:
            pi, p,c = ipcl[i]
            curr_sum += (i+1)*p*100
            curr_sum += c
            curr_prob += p
            curr_ipcl[i] = [pi,0,0]
    
    for ipc in reversed(curr_ipcl):
        i,p,c = ipc
        if curr_sum + p*i*100 <= G:
            curr_sum += p*i*100
            curr_prob += p
        else:
            remain = max(0, G-curr_sum)
            curr_prob += math.ceil( remain/(i*100) )
            break

    ans = min(ans, curr_prob)


print(ans)