Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

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

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

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

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

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

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

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

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

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

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

Sample Input 4

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

Sample Output 4

66

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



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Accepted

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

def up_f(i,score):
	if i == D+1:
		return 10**9
	n = min(score//(i*100),PC[i-1][0])
	s = n*100*i
	s += PC[i-1][1] if n == PC[i-1][0] else 0
	if s < score:
		n += up_f(i+1,score-s)
	return min(n,up_f(i+1,score))

def down_f(i,score):
	if i == 0:
		return 10**9
	n = min(score//(i*100),PC[i-1][0])
	s = n*100*i
	s += PC[i-1][1] if n == PC[i-1][0] else 0
	if s < score:
		n += down_f(i-1,score-s)
	return min(n,down_f(i-1,score))

print(min(up_f(1,G),down_f(D,G)))

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
a=[]
for i in range(d):a.append(list(map(int,input().split())))
ans=float("inf")
for i in range(2**d):
    i=list(map(int,list(bin(i)[2:].zfill(d))))
    x,y,z=0,0,0
    for j in range(d):
        if i[j]==1:
            x+=a[j][0]
            y+=(j+1)*100*a[j][0]+a[j][1]
        else:z=j
    if g-y>0:
        b=(g-y+z*100)//((z+1)*100)
        if b<a[z][0]:ans=min(ans,x+b)
    else:ans=min(ans,x)
print(ans)

Submission status: Accepted

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

ans = 10000000000
point = 0
for i in range(2 ** D):
    prob = 0
    point = 0
    for j in range(D):
        if (i & (1 << j)):
            prob += prob_list[j][0]
            point += (j+1) * 100 * prob_list[j][0] + prob_list[j][1]
    if point >= G:
        ans = min(ans, prob)
    else:
        for k in reversed(range(D)):
            if (i & (1 << k)):
                continue
            for z in range(prob_list[k][0]):
                point += (k + 1) * 100
                prob += 1
                if point >= G:
                    ans = min(ans,prob)
        ans = min(ans, prob)
print(ans)

Submission status: Accepted

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

ans = 10000000000
point = 0
for i in range(2 ** D):
    prob = 0
    point = 0
    for j in range(D):
        if (1 & (i >> j)):
            prob += prob_list[D - 1 - j][0]
            point += (D - j) * 100 * prob_list[D - 1 - j][0] + prob_list[D - 1 - j][1]
    if point >= G:
        ans = min(ans, prob)
    else:
        for k in reversed(range(D)):
            if bin(i)[2:].zfill(D)[k] == '1':
                continue
            for z in range(prob_list[k][0]):
                point += (k + 1) * 100
                prob += 1
                if point >= G:
                    ans = min(ans,prob)
        ans = min(ans, prob)
print(ans)

Submission status: Accepted

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

import itertools as ite
cmin = 100000000000000000
for cli in ite.product( *([[0,1]]*D) ):
  
  s = 0
  c = 0
  for i in range(D):
    if cli[i]==1:
      s +=  li[i][1] + (i+1)*100*li[i][0]
      c +=  li[i][0]
  
  ds = G-s
  
  for i in range(D-1,-1,-1):
    if (ds<=0):
      break
    if cli[i]==0:
      toku = (ds-1)//((i+1)*100)+1
      toku = min(toku,li[i][0])
      c += toku
      ds -= toku*(i+1)*100
    if (ds<=0):
      break
  if (ds<=0):
    cmin = min(cmin,c)
  else:
    pass
print (cmin)

Submission status: Accepted

Solution code:
import math

n,g=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
comp=[(100*(i+1)*arr[i][0]+arr[i][1]) for i in range(n)]
ans=10**10
for i in range(2**n):
  flag=format(i,'b')
  if len(flag)<n:
    flag='0'*(n-len(flag))+flag
  tsum=0
  tans=0
  for i in range(n):
    if flag[i]=='1':
      tsum+=comp[i]
      tans+=arr[i][0]
  if tsum>=g:
    ans=min(ans,tans)
  else:
    pos=flag[::-1].index('0')
    tq=math.ceil((g-tsum)/(100*(n-pos)))
    if tq<=arr[n-pos-1][0]:
      ans=min(ans,tans+tq)
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(2**d):
  count,pt=0,0
  key=str(bin(i))[2:].zfill(d)
  for j in range(d):
    if key[j]=="1":
      count+=P[j]
      pt+=P[j]*(j+1)*100+C[j]
  if pt>=g:
    ans=min(ans,count)
  else:
    for k in range(d):
      ind=d-(k+1)
      if key[ind]=="0":
        if pt+P[ind]*(ind+1)*100>=g:
          count+=(g-pt-100)//((ind+1)*100)+1
          ans=min(ans,count)
          break
        else:
          count+=P[ind]
          pt+=P[ind]*(ind+1)*100+C[ind]
          if pt>=g:
            ans=min(ans,count)
            break
print(ans)

Submission status: Accepted

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

ans = 10**10

def score(count,sum,q,s):
    global ans
    if count == d+1:
        if s == 0:
            if g <= sum:
                ans = min(ans,sum)
        else:
            for i in range(li[s-1][0]+1):
                a = sum
                q2 = q
                if i == li[s-1][0]:
                    a += s*100*i + li[s-1][1]
                    q2 += i
                else:
                    a += s*100*i
                    q2 += i
                if g <= a:
                    ans = min(ans,q2)
    else:
        score(count+1,sum,q,count)
        score(count+1,sum+count*100*li[count-1][0]+li[count-1][1],q+li[count-1][0],s)

score(1,0,0,0)

print(ans)

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def calc_bitmap(i):
    ret = []
    for j in range(10):
        ret.append((i>>j) & 1)
    return ret


def completes(pclist, bitmap):
    count = 0
    score = 0
    for i, bit in enumerate(bitmap):
        if bit:
            count += pclist[i][0]
            score += ((i+1)*100) * pclist[i][0]
            score += pclist[i][1]
    return count, score


def not_completes(pclist, bitmap, score):
    count = 0
    lbitmap = []
    for i, bit in enumerate(bitmap):
        if not bit:
            lbitmap.append(i)
    if score <= 0:
        return count
    for i in reversed(lbitmap):
        if score <= 0:
            return count
        if pclist[i][0] > 1:
            if score - ((i+1)*100) * (pclist[i][0] - 1) <= 0:
                if score % ((i+1)*100):
                    count += score // ((i+1)*100) + 1
                else:
                    count += score // ((i+1)*100)
                return count
            count += pclist[i][0] - 1
            score -= (pclist[i][0] - 1) * ((i+1)*100)
    return float('inf')


def main():
    d, g = intin()
    pclist = intinl(d)

    while len(pclist) < 10:
        pclist.append((0, 0))
    min_count = float('inf')

    for i in range(2**10):
        bitmap = calc_bitmap(i)
        ccount, score = completes(pclist, bitmap)
        ncount = not_completes(pclist, bitmap, g - score)
        min_count = min(min_count, ccount + ncount)

    print(min_count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
D,G=map(int,input().split())
l=sorted([[(i+1)*100]+list(map(int,input().split())) for i in range(D)],key=lambda x:x[0]*x[1]+x[2])[::-1]
comb=[set(x) for i in range(D+1) for x in itertools.combinations(range(D),r=i)]
setD=set(range(D))
ans=1000
for c in comb:
	res=0
	cnt=0
	if len(setD-c)>0:min_rest=min(setD-c)
	else:min_rest=None
	for i in c:
		res+=l[i][0]*l[i][1]+l[i][2]
		cnt+=l[i][1]
	if res>=G:ans=min(ans,cnt)
	elif res<G and min_rest != None and (G-res-1)//l[min_rest][2]<l[min_rest][1]:
		cnt+=(G-res-1)//l[min_rest][0]+1
		ans=min(ans,cnt)
print(ans)

Submission status: Accepted

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

ans = 10**10
for i in range(2**D):
    s = 0
    num = 0
    rest_max = -1
    for j in range(D):
        if (i >> j) & 1:
            s += 100*(j+1) * pc[j][0] + pc[j][1]
            num += pc[j][0]
        else:
            rest_max = j
    if s < G:
        s1 = 100 * (rest_max + 1)
        need = (G - s + s1 - 1) // s1
        if need >= pc[rest_max][0]:
            continue
        num += need
    ans = min(ans, num)
print(ans)

Submission status: Accepted

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


def solve(G, i):
    if i <= 0:
        return float('inf')
    n = min(G//(100*i), PC[i-1][0])
    score = 100 * i * n
    if n == PC[i-1][0]:
        score += PC[i-1][1]
    if G > score:
        n += solve(G-score, i-1)
    return min(n, solve(G, i-1))
 
 
print(solve(G, D))

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
questions = [list(map(int, input().split())) for _ in range(d)]
ans = 10 ** 9 

for i in range(2 ** d):
    score = 0
    problems = 0
    index = -1
    for j in range(d):
        if i >> j & 1:
            score += 100 * (j+1) * questions[j][0] + questions[j][1]
            problems += questions[j][0]
        else:
            index = j
    if g <= score:
        ans = min(ans, problems)
    elif 0 <= index and  g <= score + questions[index][0] * (index+1)*100:
        problems += -(-(g-score) // ((index+1)*100))
        ans = min(ans, problems)
print(ans)

Submission status: Accepted

Solution code:
d, g=map(int, input().split())
p=[]
c=[]
for i in range(d):
    p_new, c_new=map(int, input().split())
    p.append(p_new)
    c.append(c_new)
t=2**d
bins=[]
for i in range(t):
    p1=bin(i)[2:]
    p2="0"*(d-len(p1))+p1
    bins.append(p2)
ans=sum(p)
for a in bins:
    point=0
    cnt=0
    for b in range(d):
        if a[b]=="1":
            point+=p[b]*100*(b+1)+c[b]
            cnt+=p[b]
    if point>=g and ans>cnt:
        ans=cnt
    elif point<g:
        for e in range(d-1, -1, -1):
            if a[e]=="0":
                for f in range(p[e]-1):
                    point+=100*(e+1)
                    cnt+=1
                    if point>=g:
                        if ans>cnt: ans=cnt
                        break
                else:
                    continue
                break
            else: pass
print(ans)

Submission status: Accepted

Solution code:

D, G =  map(int, input().split())
PCs = [list(map(int, input().split())) for i in range(D)]

arr = []
for i in range(D):
    steps = [0]
    count = PCs[i][0]
    point = 100 * (i + 1)
    bonus = PCs[i][1]
    
    for n in range(count):
        p = (n+1) * point
        if (n+1) == count:
            p += bonus
        steps.append(p)
    arr.append(steps)
# print(arr)

dp = arr[0]
for i in range(1, len(arr)):
    leng = len(dp) + len(arr[i])
    out = [0] * leng
    for x in range(len(dp)):
        for y in range(len(arr[i])):
            v = dp[x] + arr[i][y]
            out[x+y] = max(out[x+y], v)
    dp = out

for i in range(len(dp)):
    if dp[i] >= G:
        print(i)
        break

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))

l = len(bin(2**D-1)[2:])
ans = 10**10
for i in range(0,2**D):
    li = list(bin(i)[2:].zfill(l))
    s = 0
    num = 0
    rest_max = -1
    for j in range(D):
        if li[j] == '1':
            s += 100*(j+1) * pc[j][0] + pc[j][1]
            num += pc[j][0]
        else:
            rest_max = j
    if s < G:
        s1 = 100 * (rest_max + 1)
        need = (G-s+s1-1) // s1
        if need >= pc[rest_max][0]: continue
        num += need
    ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
import statistics
import math
# N = int( input())
D,G = list(map(int,input().split(" ")))

items = []

for i in range(D):
    p,c = list(map(int,input().split(" ")))
    items.append((p,c))

ans = 10e9
for  i in range(2**D):
    # print("--"*20)
    # print("i=",i)
    socre = 0
    co = 0
    notzenkan = []
    for j in range(D):
        if ((i >> j)& 1): #最初に全完する問題を解き終える
            socre += (j + 1 ) * 100 *items[j][0] +  items[j][1]
            co += items[j][0]
        else:
            notzenkan.append(j)
    notzenkan = notzenkan[::-1]
    # print(socre)
    for q in notzenkan:
        if socre >= G:
                break
        question_num = items[q][0]
        for num in range(question_num):
            socre += (q + 1 ) *100
            co += 1
            if socre >= G:
                break
        # print(socre)
    if co < ans and socre >= G:
        # print(co)
        ans = co
print(ans)

Submission status: Accepted

Solution code:
import math
D,G = map(int, input().split())
pclist = [list(map(int, input().split())) for _ in range(D)]
bits=[format(i, '0'+str(D)+'b') for i in range(2**D)]
ans = 10**5
for bit in bits:
    resn = 0
    res = 0
    maxi = bit.rfind('0')+1
    for i, b in enumerate(bit):
        if b == '1':
            resn += pclist[i][0]
            res += pclist[i][0]*100*(i+1)+pclist[i][1]
    if res >= G:
        if resn < ans:
            ans = resn
    elif maxi > 0 and res+(pclist[maxi-1][0]-1)*100*maxi >= G:
        if G-res > 0:
            resn += math.ceil((G-res)/(100*maxi))
        if resn < ans:
            ans = resn
print(ans)

Submission status: Accepted

Solution code:
import math
D,G = map(int, input().split())
pclist = [list(map(int, input().split())) for _ in range(D)] + [[0,0]]
bits=[format(i, '0'+str(D)+'b') for i in range(2**D)]
ans = 10**5
for bit in bits:
    resn = 0
    res = 0
    maxi = bit.rfind('0')+1
    for i, b in enumerate(bit):
        if b == '1':
            resn += pclist[i][0]
            res += pclist[i][0]*100*(i+1)+pclist[i][1]
    if res >= G:
        if resn < ans:
            ans = resn
    elif maxi > 0 and res+(pclist[maxi-1][0]-1)*100*maxi >= G:
        if G-res > 0:
            resn += math.ceil((G-res)/(100*maxi))
        if resn < ans:
            ans = resn
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 f(i,t):
    if i == 0 or i > D:
        return 10**9
    k = min(t//(100*i),PC[i][0])
    s = 100*i*k
    if k == PC[i][0]:
        s += PC[i][1]
    if s<t:
        k += f(i-1,t-s)
        #k += min(f(i-1,t-s),f(i+1,t-s))
    return min(k,f(i-1,t))

print(f(D,G))

Submission status: Accepted

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

#pc = [map(int,input().split()) for i in range(D)]
prob = [list(map(int, input().split())) for i in range(D)]


### piの問題に対して全部解いたと仮定して
### 不足分は配点の大きい問題から解く

min_count = 10000
for i in range(1<<D):
    score = 0
    count = 0
    for j in range(D):
        if (i>>j)&1:
            score += (j+1)*100 * prob[j][0] + prob[j][1] # 全問得点+ボーナス
            count += prob[j][0]

    ## 不足分を配点の大きい問題から一問ずつ加点
    for j in reversed(range(D)):
        if not (i>>j)&1:
            for k in range(0, prob[j][0]-1):
                if score >= G:
                    break
                score += (j+1)*100
                count += 1

    if score >= G:
        min_count = min(count, min_count)

print(min_count)

Submission status: Accepted

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

def dfs(question_num, rquired_point):
    if question_num < 0:
        return 10 ** 9

    point = (question_num+1) * 100
    ans_num = min(rquired_point // point, pc[question_num][0])
    score = ans_num * point

    if ans_num == pc[question_num][0]:
        score += pc[question_num][1]

    if rquired_point > score:
        ans_num += dfs(question_num-1, rquired_point-score)
    
    return min(ans_num, dfs(question_num-1, rquired_point))

print(dfs(D-1, G))

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
p = []
c = []
for i in range(d):
    tp,tc = map(int,input().split())
    p.append(tp)
    c.append(tc)
ans = 1<<50
for i in range(1<<d):#どのコンプリートボーナスを狙うかを決める
    score = 0
    count = 0
    zero_list = []
    for j in range(d):
        if ((i >> j) & 1):
            score += c[j] + p[j]*(j+1)*100 
            count += p[j]
        else:
            zero_list.append(j)
    if score >= g:
        ans = min(ans,count)
    else:#もしまだ点数が届いていないならボーナスを狙わないものから点数が高い問題を解く
        rem = g-score
        if rem <= (p[max(zero_list)]-1)*(max(zero_list)+1)*100:
            for i in range(1,p[max(zero_list)]):
                if rem - i*(max(zero_list)+1)*100 <= 0:
                    count +=  i
                    ans = min(ans,count)
                    break
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc104/tasks/abc104_c

import itertools as it

INF = 100000007

if __name__ == "__main__":
    D, G = map(int, input().split())
    pairs = [[int(s) for s in input().split()] for _ in range(D)]
    p, c = zip(*pairs)
    res = INF

    iterables = it.product([False, True], repeat=D)
    for choice in iterables:
        cnt = 0
        total = 0
        for i in range(D):
            if choice[i]:
                cnt += p[i]
                total += 100 * (i + 1) * p[i] + c[i]

        for j in reversed(range(D)):
            if total >= G:
                break
            if not choice[j]:
                item_value = 100 * (j + 1)
                item_count = min(p[j], (G - total + item_value - 1) // item_value)
                cnt += item_count
                total += item_value * item_count

        if cnt < res:
            res = cnt

    print(res)

Submission status: Accepted

Solution code:
#coding: utf-8
D, G = map(int, input().split())
l = []
P, C = [], []
for _ in range(D):
	p, c = map(int, input().split())
	P.append(p)
	C.append(c)
	#l.append([p, c, i+1])
ans = 10 ** 10
for mask in range(int(bin(1 << D), 0)):
	s = 0
	num = 0
	rest_max = -1
	for i in range(D):
		if mask >> i & 1:
			s += 100 * (i + 1) * P[i] + C[i]
			num += P[i]
		else:
			rest_max = i

	if s < G:
		s1 = 100 * (rest_max + 1)
		need = (G - s + s1 - 1) // s1
		if need >= P[rest_max]:
			continue
		num += need

	ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    w = 2 ** D
    ret = float('inf')
    for i in range(w):
        s = 0
        cc = 0
        ri = 0
        for j in range(D):
            if ((i >> j) & 1) == 1:
                s += 100 * (j + 1) * p[j] + c[j]
                cc += p[j]
            else:
                ri = j
        if s < G:
            for j in range(p[ri] - 1):
                s += 100 * (ri + 1)
                cc += 1
                if G <= s:
                    break
        if G <= s:
            ret = min(ret, cc)
    return ret


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np
import math
import re

a,b=map(int,input().split())
c=[0]+[list(map(int,input().split()))for i in range(a)]

def f(t,s):
    if t==0:
        return 10**9
    l=min(s//(t*100),c[t][0])
    k=100*t*l
    if l==c[t][0]:
        k+=c[t][1]
    if k<s:
        l+=f(t-1,s-k)
    return min(l,f(t-1,s))
print(f(a,b))

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
p = []
c = []
for i in range(d):
    tp,tc = map(int,input().split())
    p.append(tp)
    c.append(tc)
ans = 1<<50
for i in range(1<<d):#どのコンプリートボーナスを狙うかを決める
    score = 0
    count = 0
    zero_list = []
    for j in range(d):
        if ((i >> j) & 1):
            score += c[j] + p[j]*(j+1)*100 
            count += p[j]
        else:
            zero_list.append(j)
    if score >= g:
        ans = min(ans,count)
    else:#もしまだ点数が届いていないならボーナスを狙わないものから点数が高い問題を解く
        rem = g-score
        # if count == 5:#debag
        #     print("dbg")
        #     print(zero_list)
        #     print(rem)
        #     print((p[max(zero_list)]-1)*(max(zero_list)+1)*100)
        #     print(p[max(zero_list)])
        if rem <= (p[max(zero_list)]-1)*(max(zero_list)+1)*100:
            for i in range(1,p[max(zero_list)]):
                # print("dbg2")
                # print(rem - i*(max(zero_list)+1)*100)
                if rem - i*(max(zero_list)+1)*100 <= 0:
                    count +=  i
                    ans = min(ans,count)
                    break
print(ans)

Submission status: Accepted

Solution code:
def getMaxindex(lis, val):
        lis.reverse()
        return len(lis) - 1 - lis.index(val)
#input
d, g = map(int, input().split())
p, c =[], []
ans = []
for i in range(d):
    tmp1, tmp2 = map(int, input().split())
    p.append(tmp1)
    c.append(tmp2)
    
#bit全探索
oplist, op = [], []
for i in range(2**d):
    op = [True] * d
    for j in range(d):
        if (i >> j) & 1:
            op[d - 1 - j] = False
    oplist.append(op)

for i in range(2**d):
    cnt, tmp = 0, 0
    for j in range(d):
        if oplist[i][j]:
            tmp += 100*(j+1)*p[j]+c[j]
            cnt += p[j]
    if tmp < g:
        hnp = getMaxindex(oplist[i], False)
        for k in range(p[hnp]):
            cnt += 1
            tmp += 100*(hnp+1)
            if tmp >= g:
                ans.append(cnt)
                break
    else:
        ans.append(cnt)
print(min(ans))

Submission status: Accepted

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

ans = sum([p for p,c in pc])
for i in range(2**D-1):
    score = 0
    unused_max = D-1
    sum_p = 0
    for j in range(D-1,-1,-1):
        if (i>>j)%2:
            score += pc[j][1] + pc[j][0]*(j+1)*100
            sum_p += pc[j][0]
            if unused_max == j:
                unused_max -= 1
    if G - score <= (pc[unused_max][0]-1)*(unused_max+1)*100:
        ans = min(ans,sum_p+max(0,(G-score-1)//(100*(unused_max+1))+1))
print(ans)

Submission status: Accepted

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

m = []

for i in range(2**d):
    sum = 0
    cnt = 0
    z = [i for i in range(d)]
    for j in range(d):
        if (i>>j)&1:
            sum += (j+1) * 100 * p[j] +c[j]
            cnt += p[j]
            z.remove(j)
    if sum < g:
        for i in range(p[max(z)]):
            sum += (max(z) + 1) *100
            cnt += 1
            if sum >= g:
                m.append(cnt)
                break

    else:
        m.append(cnt)

print(min(m))

Submission status: Accepted

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

def dfs(h, s):
    if h == 0:
        return 10**9
    tmp = min(p[h], s//h)
    score = tmp * h
    if tmp == p[h]:
        score += c[h]
    if score < s:
        tmp += dfs(h-1, s-score)
    return min(tmp, dfs(h-1, s))

print(dfs(d, g))

Submission status: Accepted

Solution code:
from itertools import product


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


ans = 1e9
for selected in product((True, False), repeat=D):
    tmp_score = 0
    tmp_count = 0
    rest_max = 0

    for i, is_select in enumerate(selected):
        if is_select:
            tmp_score += 100 * (i + 1) * pc[i][0] + pc[i][1]
            tmp_count += pc[i][0]
        else:
            rest_max = i

    if tmp_score < G:
        s1 = 100 * (rest_max + 1)
        need = (G - tmp_score + s1 - 1) // s1

        if need >= pc[rest_max][0]:
            continue

        tmp_count += need

    ans = min(ans, tmp_count)

print(ans)

Submission status: Accepted

Solution code:

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

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

ans = 10**18
for i in range(2**D):
    binary = bin(i)[2:].zfill(D)
    tatal = 0
    cnt = 0
    for j in range(D):
        if binary[j]=='1':
            tatal += p_tatal[j][1]
            cnt += p_tatal[j][0]
        else:
            not_use = j
#    print(1tatal,cnt)   
    if tatal >= G:
#        print(cnt)
        ans = min(ans,cnt)
    elif tatal < G <=  tatal +(p_tatal[not_use][0]-1)*(not_use+1)*100:
        cnt += -(-(G - tatal)// ((not_use+1)*100))
#        print(cnt)
        ans = min(ans,cnt)
    else:
        continue
        

print(ans)

Submission status: Accepted

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

min_count = 1e9

for mask in range(1<<D):
    count = 0
    score = 0
    rest = -1
    for i in range(D):
        if((mask>>i) & 1):
            score += prob[i][0]*100*(i+1) + prob[i][1]
            count += prob[i][0]
        else:
            rest = i

    for i in range(prob[rest][0]):
        if (score < G):
            score += (rest+1)*100
            count += 1
        else:
            min_count = min(min_count, count)
            break

print(min_count)

Submission status: Accepted

Solution code:
#人のプログラムの全コピ　TKR18さん

#入力
a,b=map(int,input().split())
c=[0]+[list(map(int,input().split()))for i in range(a)]

#print(c)

def f(t,s): #t:t*100点までリストが存在する s: 目標値
    if t==0: #が0の時、とりあえず大きな数を返す
        return 10**9
    l=min(s//(t*100),c[t][0]) #s//(t*100): 目標を最高基本点で割った時の商、c[t][0]:最高基本点の使える数　これらの小さい方を返す
    k=100*t*l #最高基本点を使って得点できる最高点
    if l==c[t][0]: #最高基本点を使った数が、使える数と同じならボーナス点を加える。
        k+=c[t][1] 
    if k<s: #最高基本点を全て使って得点できる点が、目標点以下なら...
        l+=f(t-1,s-k) #最高気本点を除いたもので、残りの点数を計算する。
    return min(l,f(t-1,s)) #最高気本点を使うもの(l)と最高基本点を使わないもの(f(t-1,s)のうち最小のものを見つける
print(f(a,b))