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())
cnts = []
points = []
for i in range(1,D + 1):
        p,c = map(int,input().split())
        points.append([p, i * 100, i * 100 * p + c, c])

for i in range(1 << D):
        point = 0
        cnt = 0
        not_used = [_ for _ in range(D)]
        for j in range(D):
                if 1 << j & i:
                        many,one,all,bounsu = points[j]
                        cnt += many
                        point += all
                        not_used.remove(j)
        if point < G:
                biggest = points[not_used[len(not_used) - 1]]
                if biggest[2] < G - point:
                        continue
                cnt += (G - point) // biggest[1]
                if (G - point) % biggest[1] != 0:
                        cnt += 1
        cnts.append(cnt)
print(min(cnts))

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
c=[0]+[list(map(int,input().split())) for i in range(D)]
def f(t,s):
	if t==0:
		return 10**9
	#点数が高いものを解けるだけとく
	#問題数or目標点数を満たす数
	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(D,G))

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
import math
pc = []
for i in range(d):
    pc.append(list(map(int,input().split())))
ans = 10000
for i in range(2**d):
    score = 0
    num = 0
    for j in range(d):
        if i>>j & 1 == 1:
            score += pc[j][0]*(j+1)*100+pc[j][1]
            num += pc[j][0]
    for j in range(d-1,-1,-1):
        if i>>j & 1 == 0:
            if g>score:
                so = math.ceil((g-score)/((j+1)*100))
                if so < pc[j][0]:
                    ans = min(ans,num+so)
            else:
                ans = min(ans,num)
        if g<=score:
            ans = min(ans,num)
print(ans)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
c=[0]+[list(map(int,input().split())) for i in range(a)]
print()
def f(t,s):
	if t==0:
		return 10**9
	#点数が高いものを解けるだけとく
	#問題数or目標点数を満たす数
	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())
problems = [tuple(map(int, input().split())) for i in range(D)]

ans = 1000
for i in range(1 << D):
    S = G
    P = 0
    max_j = 0
    for j in range(D):
        if i >> j & 1 == 1:
            P += problems[j][0]
            S -= 100 * (j + 1) * problems[j][0] + problems[j][1]
        else:
            max_j = j
    if S > 0:
        p = 100 * (max_j + 1)
        need = (S + p - 1) // p
        if need >= problems[max_j][0]:
            continue
        P += need
    ans = min(P, ans)
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
l = [list(map(int,input().split())) for i in range(d)]
def f(t,s):
    if t==-1:
        return float('inf')
    num = min(l[t][0],s//((t+1)*100))
    k = num*(t+1)*100
    if num==l[t][0]:
        k += l[t][1]
    if k<s:
        num += f(t-1,s-k)
    return min(num,f(t-1,s))
 
print(f(d-1,g))

Submission status: Accepted

Solution code:
from math import ceil

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

pc_list = [[i]+list(map(int,input().split())) for i in range(D)]
def rindex_zero(l):
    return len(l) - l[::-1].index(0)-1

def func(g,cnt,l):
    if len(l) == D:
        if g <= 0:
            return cnt
        idx = rindex_zero(l)
        i,p,c = pc_list[idx]
        if g <= 100*(i+1)*(p-1):
            cnt += ceil(g/(100*(i+1)))
            return cnt
        return 10**9
    length = len(l)
    i,p,c = pc_list[length]
#     print(i,p,c,l)
    a = func(g-(100*(i+1)*p+c), cnt+p,l+[1])
    b = func(g, cnt,l +[0])
    return min(a,b)
        
print(func(G,0,[]))

Submission status: Accepted

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

lst = [list(map(int, input().split())) for i in range(D)]
ans = []
ref = []
for i,v in enumerate(lst):
	ref.append(v[0]*(i+1)*100 + v[1])
  
for i in range(2 ** D):
	score = 0
	cnt = 0
	for j in range(D):  
		if ((i >> j) & 1):  
			score += ref[j]
			cnt += lst[j][0]
	if (score >= G):
		ans.append(cnt)
	else:
		for l in range(D)[::-1]:
			if ((i >> l) & 1):
				continue
			for _ in range(1,lst[l][0]):
				score += (l+1) * 100
				cnt += 1
                
				if score >= G:
					ans.append(cnt)  
					break
print(min(ans))

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
ans=10000
p=[]
c=[]
for i in range(d):
    a,b=map(int,input().split())
    p.append(a)
    c.append(b)
for i in range(2**d):
    x=0
    cou=0
    l=[]
    for j in range(d):
        if ((i>>j)&1):
            x+=c[j]+p[j]*(j+1)*100
            cou+=p[j]
        else:
            l.append(j)
    l.sort(reverse=True)
    k=0
    while x<g:
        for _ in range(p[l[k]]):
            if x>=g:
                break
            cou+=1
            x+=(100*(l[k]+1))
        k+=1
        if k>=len(l):
            break
    ans=min(ans,cou)
print(ans)

Submission status: Accepted

Solution code:
import math

d, g = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(d)]

l_money = [[(i+1)*100]*(l[i][0]-1) + [(i+1)*100 + l[i][1]] for i in range(d)]
l_sum = [sum(l_money[x]) for x in range(d)]
# print(l)
# print(l_money)
# print(l_sum)

ans = float("inf")
for i in range(2**d):
    cnt = 0
    now = 0
    amari = []
    for j in range(d):
        if ((i>>j) & 1):
            now += l_sum[j]
            cnt += l[j][0]
        else:
            amari.append(l_money[j][:-1])
    amari.sort(reverse=True)

    # print(now, cnt, amari)

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

    cnt_add_min = 1000
    for k in range(len(amari)):
        if amari[k]:
            cnt_add = math.ceil((g-now)/amari[k][0])
            if cnt_add <= len(amari[k]):
                cnt_add_min = min(cnt_add_min, cnt_add)

    if cnt_add_min != 1000:
        cnt += cnt_add_min
        ans = min(ans, cnt)
    else:
        continue

print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
table = []
for i in range(d):
  table.append( [(i+1) * 100] + list(map(int,input().split())) )
time = [0 for _ in range(d)]
#print(table)
def suc(time):
  cnt = 0
  while cnt < d:
    if time[d-1-cnt] == 0:
      time[d-1-cnt] = 1
      return time
      break
    else:
      time[d-1-cnt] = 0
      cnt += 1
  else:
    return 'over'
def here(time):
  cnt = 0
  while time[d-1-cnt] == 1:
    cnt += 1
    if cnt == d+1:
      return 'full'
      break
  else:
    return cnt
ans = []
while time != 'over':
  now = 0
  scr = 0
  hh = here(time)
  if hh == 'full':
    h = 'fuck'
  else:
    h = table[d-1-here(time)]
  for i in range(d):
    now += time[i] * table[i][1]
    scr += time[i] * (table[i][0] * table[i][1] + table[i][2])
  if scr >= g:
    ans.append(now)
  else:
    rest = g - scr
    if rest < h[0] * h[1]:
      now += (rest-1) // h[0] + 1
      ans.append(now)
  time = suc(time)
print(min(ans))

Submission status: Accepted

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

for j in range(2**d):
    total = 0
    count = 0
    for i in range(d):
        if (j >> i) & 1:
            total += 100*(i+1)*q_list[i][0] + q_list[i][1]
            count += q_list[i][0]

    if total >= g:
        count_list.append(count)
        continue

    else:
        for t in range(d):
            digit = str(d)
            if str(format(j, '0'+digit+'b'))[t] == '0':
                for x in range(q_list[d-t-1][0]-1):
                    count += 1
                    total += 100 * (d-t)

                    if total >= g:
                        count_list.append(count)
                        break
                break

print(min(count_list))

Submission status: Accepted

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

num = 2**d

score = 0
ans = 0

use = [0,1]

def nokori(use,score):
    tmp = 0
    for i in range(d):
        #print(use, d-1-i, d-1-i not in use)
        if d-1-i not in use:
            if pc[d-1-i][0] * (d-1-i+1) * 100 >= score:
                tmp += (score +(d-1-i+1) * 100 - 1) // ( (d-1-i+1) * 100 )
                return tmp
            elif pc[d-1-i][0] * (d-1-i+1) * 100 + pc[d-1-i][1] >= score:
                tmp += pc[d-1-i][0]
                return tmp
            else:
                tmp += pc[d-1-i][0]
                score -= pc[d-1-i][0] * (d-1-i+1) * 100 + pc[d-1-i][1]
kouho = []

kouho.append(nokori([-1],g))
#exit()

for i in range(num):
    use = []
    ans = 0
    score = 0
    cur = i
    #print(i)
    for j in range(d):
        if cur == 0:
            continue
        elif cur% 2 == 1:
            #print(i % 2,j)
            score += pc[j][0] * (j+1) * 100 + pc[j][1]
            ans += pc[j][0]
            use.append(j)
            #print(use,j,cur)
        #else:
            #cur -= 1
            #continue
        cur = cur // 2
    #print(use,i)
    if score >= g:
        kouho.append(ans)
    else:
        #print(use)
        #print(ans,score)
        kouho.append(ans+nokori(use,g-score))
        #print(ans+nokori(use,d-score))

#print(kouho)
kouho.sort()
print(kouho[0])

Submission status: Accepted

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

ans = float('inf')
for i in range(2 ** n):
    g_sum = 0
    count = 0
    rest_max = -1
    for j in range(n):
        if (i >> j) & 1:
            g_sum += 100 * (j + 1) * a[j][0] + a[j][1]
            count += a[j][0]
        else:
            rest_max = j

    if g_sum < g:
        s1 = 100 * (rest_max + 1)
        need = (g - g_sum + s1 - 1) // s1
        if need >= a[rest_max][0]:
            continue
        count += need
    ans = min(ans, count)

print(ans)

Submission status: Accepted

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


def solve(D, G, ps, cs):
  ans = 100000000
  for mask in range(1 << D):
    s = 0
    num = 0
    rest_max = -1
    for i in range(D):
      if mask >> i & 1:
        s += 100 * (i+1) * ps[i] + cs[i]
        num += ps[i]
      else:
        rest_max = i
    if s < G:
      s1 = 100 * (rest_max + 1)
      need = int((G - s + s1 - 1) / s1)
      if need >= ps[rest_max]:
        continue
      num += need
    ans = min(ans, num)
  return ans
  

if __name__ == '__main__':
  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)
  print(solve(D, G, ps, cs))

Submission status: Accepted

Solution code:
import itertools


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

P     = [None] * D
C     = [None] * D
count = [None] * D
score = [None] * D

for i in range(D):
    p, c          = map(int, input().split())
    P[i]          = p
    C[i]          = c
    count[i]      = list(range(p+1))
    score[i]      = [100 * (i+1) * j for j in range(p+1)]
    score[i][-1] += c

answer = sum(P)

for is_complete in itertools.product([True, False], repeat=D):
    score_tmp  = 0
    count_tmp  = 0
    score_tmp += sum([score[i][-1] for i in range(D) if is_complete[i]])
    count_tmp += sum([count[i][-1] for i in range(D) if is_complete[i]])
    if score_tmp < G:
        for i in list(range(D))[::-1]:
            if is_complete[i] == False:
                if (G - score_tmp) % (100 * (i+1)) == 0:
                    count_add  = min((G - score_tmp) // (100 * (i+1)),     P[i] - 1)
                else:
                    count_add  = min((G - score_tmp) // (100 * (i+1)) + 1, P[i] - 1)
                score_add      = 100 * (i+1) * count_add
                count_tmp     += count_add
                score_tmp     += score_add
            if score_tmp >= G:
                break
    if score_tmp >= G:
        answer = min(answer, count_tmp)

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    mn = 1e5
    for i in range(1 << D):
        score = 0
        count = 0
        for j in range(D):
            if i >> j & 1 == 1:
                score += p[j] * 100 * (j+1) + c[j]
                count += p[j]
        if score >= G:
            mn = min(mn, count)
            continue
        for k in range(D):
            j = D - k - 1
            if i >> j & 1 == 0:
                if score + 100*(j+1)*(p[j]-1) >= G:
                    count += math.ceil((G - score) / (100*(j+1)))
                    score += 100*(j+1)*count
                    break
                else:
                    score += 100*(j+1)*(p[j]-1)
                    count += p[j] - 1
        # print(score, count)
        if score >= G:
            mn = min(mn, count)
    print(mn)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

p = [] # 問題数の格納
c = [] # ボーナス点の格納
ans = [] #　候補解の格納
ss = 0
cnt = 0

for _ in range(d): #問題数、ボーナス点の入力
    pp,cc = map(int,input().split())
    p.append(pp)
    c.append(cc)

for x in range(2**d): #bit全探索
    ss = 0 # 得点
    cnt = 0 #　問題数
    for i in range(d): #bit探索
        if (x >> i) & 1:
            ss += (i+1)*100*p[i] + c[i]
            cnt += p[i]
    
    if ss >= g: #　既に得点がg以上の時、ansに格納
        ans.append(cnt)
    
    else:
        for l in range(d)[::-1]:
            if ((x>>l)&1):
                continue
            for _ in range(1,p[l]):
                ss += (l+1) * 100
                cnt += 1
                
                if ss >= g:
                    ans.append(cnt)
                    break

print(min(ans))

Submission status: Accepted

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

p = []
c = []
ans = []
cnt = 0
ss = 0
for _ in range(d):
    pp, cc = map(int, input().split())

    p.append(pp)
    c.append(cc)



for x in range(2**d):
    ss = 0
    cnt = 0
    for i in range(d):
        if (x>>i)&1:

            ss += (i+1)*100*p[i] + c[i]
            cnt += p[i]
    if ss>=g:
        ans.append(cnt)

    else:
        for l in range(d)[::-1]:
            if  ((x >> l) & 1):
                continue

            for _ in range(1,p[l]):
                ss += (l+1)*100
                cnt += 1

                if ss>=g:
                    ans.append(cnt)
                    break

print(min(ans))

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
# (問題数,ボーナス)のタプルで保存
p = [tuple(map(int, input().split())) for _ in range(d)]
ans = 1000
#  全完する問題の組み合わせを考える
for i in range(2 ** d):
    cnt = 0
    total = 0
    for j in range(d):
        # 全完する場合
        if (i >> j) & 1:
            # 問題数と得点＆ボーナスを追加
            cnt += p[j][0]
            total += (j + 1) * 100 * p[j][0] + p[j][1]
    #  まだ目標に届かない場合
    if total < g:
        # 得点の高い問題から取り掛かるのか最適
        for j in range(d - 1, -1, -1):
            # 全完しない予定だった問題を考慮する
            if (i >> j) & 1:
                continue
            for k in range(p[j][0]):
                if total >= g:
                    break
                # 得点と問題数を追加
                total += 100 * (j + 1)
                cnt += 1
    # 最小のものを求める
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import math

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

min = 10 ** 9
for i in range(2**(D)):
  count = 0
  p_count = 0
  no_solve = []
  for j in range(D):
    if i>>j&1 == 1:
      count += s_max[j]
      p_count += pn[j]
    else:
      no_solve.append(j)
  if count >= G:
    if min > p_count:
      min = p_count
  else:
    box = math.ceil((G - count) / (100 * (no_solve[-1]+1)))
    if box < pn[no_solve[-1]]:
      p_count += box
      if min > p_count:
        min = p_count
print(min)

Submission status: Accepted

Solution code:
import math
D,G = map(int,input().split())
s_max = []
pn = []
for i in range(1,D+1):
    p,c = map(int,input().split())
    s_max.append(100*i*p+c)
    pn.append(p)
num_all = sum(pn)
for i in range(2<<D):
    a = []
    for j in range(D):
        a.append(i%2)
        i = i//2
    s = sum([s_max[i] for i in range(D) if a[i] == 1])
    if 0 in a:
        m = max([i for i in range(D) if a[i] == 0])
        num = math.ceil((G-s)/(100*(m+1)))
        if G> s and num <= pn[m]:
            num_all = min(num_all,sum([pn[i] for i in range(D) if a[i] == 1])+num)
        elif G <= s:
            num_all = min(num_all,sum([pn[i] for i in range(D) if a[i] == 1]))
print(num_all)

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math

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

total = []
for i in range(D):
	total.append((i+1)*pc[i][0]*100 + pc[i][1])

minn = 100000000
for i in range(2**D):
	sum = 0
	n = 0
	max0 = -1
	for j in range(D):
		x = (i & (2 ** j)) // (2 ** j)
		sum += total[j]*x
		n += pc[j][0]*x
		if x == 0:
			max0 = j

	if sum >= G:
		minn = min(minn, n)
	elif sum < G:
		rest = math.ceil((G - sum) / (100*(max0 + 1)))
		if rest < pc[max0][0]:
			minn = min(minn, n + rest)
print(minn)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
P = list()
for i in range(1, D + 1):
    p, c = map(int, input().split())
    P.append((100 * i, p, c))

ans = float('inf')
for i in range(2 ** D):
    points = 0
    problems = 0
    for d in range(D):
        if (i >> d) & 1:
            i100, p, c = P[d]
            points += i100 * p + c
            problems += p
    if points >= G:
        ans = min(ans, problems)
        continue
    for d in reversed(range(D)):
        if (i >> d) & 1:
            continue
        i100, p, c = P[d]
        for j in range(p):
            if points >= G:
                break
            points += i100
            problems += 1
    ans = min(ans, problems)

print(ans)

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10**7)

# Override `input` function because `stdin.readline()` is 10x faster than built-in `input()`
input = sys.stdin.readline


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h(typ) if m > 1 else typ(input()) for _ in range(n)]


def solve(d, g, pc):
    min_num = 100 * d + 1
    for i in range(2**d):
        num = 0
        score = 0
        offset = -1
        for j in range(d):
            if (i >> j) & 1:
                # Solve full problems
                # print('i = {}, j = {}'.format(i, j))
                p, c = pc[j]
                # print('p = {}, c = {}'.format(p, c))
                num += p
                score += 100 * (j + 1) * p + c
                # print('num = {}, score = {}'.format(num, score))
            else:
                offset = j
                # print('offset:', offset)

        if score < g:
            # Solve incomplete problems
            short = 100 * (offset + 1)
            # print('short:', short)
            need = (g - score + short - 1) // short
            if need >= pc[offset][0]:
                continue
            # print('need:', need)
            num += need
            # print('need added:', num)

        min_num = min(min_num, num)
        # print('min num:', min_num)

    return min_num


def main():
    d, g = read_h()
    pc = read_v(d, m=2)
    # print(pc)

    num = solve(d, g, pc)
    print(num)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
D, G = map(int, input().split())
L = [[int(i) for i in input().split()] for j in range(D)]
p = [L[i][0] for i in range(D)]
q = [L[i][1] for i in range(D)]

#for l in L:
#   l.append(i*l[0]*100+l[1])
#   i += 1

M = [L[i][0]*(i+1)*100+L[i][1] for i in range(D)]
lis = []
for i in range(1 << D):
    s = [0, 0]
    for j in range(D):
        if ((i >> j) & 1) == 1:
            s[0] += p[j]
            s[1] += M[j]
    for j in range(D):
        if ((i >> j) & 1) == 0:
            lis.append(s+[j+1])
        else:
            lis.append(s+[0])
#print(lis)
ans = 1010
for l in lis:
    if G <= l[1]:
        ans = min(ans, l[0])
    elif G - l[1] <= l[2] * 100 * (p[l[2]-1]-1):
        ct = math.ceil((G-l[1]) / (l[2]*100))
        ans = min(ans, l[0]+ct)

print(ans)

Submission status: Accepted

Solution code:
import math
D, G = map(int, input().split())
L = [[int(i) for i in input().split()] for j in range(D)]
p = [L[i][0] for i in range(D)]
q = [L[i][1] for i in range(D)]

#for l in L:
#   l.append(i*l[0]*100+l[1])
#   i += 1

M = [L[i][0]*(i+1)*100+L[i][1] for i in range(D)]
lis = []
for i in range(1 << D):
    s = [0, 0]
    for j in range(D):
        if ((i >> j) & 1) == 1:
            s[0] += p[j]
            s[1] += M[j]
    for j in range(D):
        if ((i >> j) & 1) == 0:
            lis.append(s+[j+1])
        else:
            lis.append(s+[0])

ans = 1010
for l in lis:
    if G <= l[1]:
        ans = min(ans, l[0])
    elif G - l[1] <= l[2] * 100 * (p[l[2]-1]-1):
        ct = ((G-l[1])+(l[2]*100)-1) // (l[2]*100)
        ans = min(ans, l[0]+ct)

print(ans)

Submission status: Accepted

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

ans_min = 10 ** 10
for i in range(2 ** D):
    flag = bin(i)[2:].zfill(D)
    p_max = [0] * D
    score = 0
    ans = 0
    for j in range(D):
        if flag[j] == '1':
            p_max[j] = 0
            ans += prob[j][0]
            score += prob[j][1] + 100 * (j + 1) * prob[j][0]
        else:
            p_max[j] = prob[j][0] - 1
    p_use = D
    while score < G:
        p_use -= 1
        if p_use == -1:
            ans = 10 ** 10
            break
        solve = min((G - score - 1) // (100 * (p_use + 1)) + 1, p_max[p_use])
        ans += solve
        score += solve * 100 * (p_use + 1)
    ans_min = min(ans, ans_min)

print(ans_min)

Submission status: Accepted

Solution code:

D, G = map(int, input().split())  # 与えられる問題数のスコアのレンジD, 目標の点数G
 
PC = []  # 100i点の問題の個数とコンプリートボーナス
ans = 99999999
for i in range(D):
    p, c = map(int, input().split())
    score = (i+1)*100
    PC.append([score, p, c])
 
for mask in range(1 << D):  # D種類の問題について解くか解かないかの二択を考える
    solved_amount = 0
    my_score = 0
    for i in range(D):
        score, p, c = PC[i]  # その問題のscore, 問題数のp, コンプリートしたらc
        if (mask >> i) & 1:  # ビットが立つならその問題を全て解くことにする
            solved_amount += p  # 解いた問題数を増やして
            my_score += score * p + c  # スコアを加算する
 
    for i in range(D-1, -1, -1):  # 目標点Gに達していない時の処理、配点の高い問題から考えている
        if my_score >= G:  # すでに目標点数に到達していたら終了して、解いた問題の量を保持しにいく
            break
 
        if (mask >> i) & 1:  # すでにその問題を解いていたらもう解けないので次の配点の問題へ
            continue
 
        score, p, c = PC[i]  # 今部分的に解こうとしている問題のscore, 問題数のp, コンプリートしたらc
        # 今スコアは超えていない状態
        for _ in range(p):
            # 一問ずつ解いて超えるラインを探す
            solved_amount += 1
            my_score += score
            if my_score >= G:
                break
    if my_score >= G:
        ans = min(ans, solved_amount)
 
print(ans)

Submission status: Accepted

Solution code:
"All Green"

"""
考え方
その点数の問題を全て解く or 1問も解かないをbit全探索で分けて処理を行い、目標点に到達していない
ならば、配点の高い問題から一問ずつ解いて確認していく。
"""

D, G = map(int, input().split())  # 与えられる問題数のスコアのレンジD, 目標の点数G

PC = []  # 100i点の問題の個数とコンプリートボーナス
ans = 99999999
for i in range(D):
    p, c = map(int, input().split())
    score = (i+1)*100
    PC.append([score, p, c])

for mask in range(1 << D):  # D種類の問題について解くか解かないかの二択を考える
    solved_amount = 0
    my_score = 0
    for i in range(D):
        score, p, c = PC[i]  # その問題のscore, 問題数のp, コンプリートしたらc
        if (mask >> i) & 1:  # ビットが立つならその問題を全て解くことにする
            solved_amount += p  # 解いた問題数を増やして
            my_score += score * p + c  # スコアを加算する

    for i in range(D-1, -1, -1):  # 目標点Gに達していない時の処理、配点の高い問題から考えている
        if my_score >= G:  # すでに目標点数に到達していたら終了して、解いた問題の量を保持しにいく
            break

        if (mask >> i) & 1:  # すでにその問題を解いていたらもう解けないので次の配点の問題へ
            continue

        score, p, c = PC[i]  # 今部分的に解こうとしている問題のscore, 問題数のp, コンプリートしたらc
        # 今スコアは超えていない状態
        for _ in range(p):
            # 一問ずつ解いて超えるラインを探す
            solved_amount += 1
            my_score += score
            if my_score >= G:
                break
    if my_score >= G:
        ans = min(ans, solved_amount)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
D, G = [int(_) for _ in stdin.readline().rstrip().split()]
P, C = [], []
for _ in range(D):
    p, c = stdin.readline().rstrip().split()
    P.append(int(p))
    C.append(int(c))
res = 1<<29
for bit in range(1<<D):
    s, num = 0, 0
    for i in range(D):
        if ((bit >> i) & 1):
            s += C[i] + P[i] * 100 * (i+1)
            num += P[i]
    if s >= G:
        res = min(res, num)
    else:
        for i in range(D-1, -1, -1):
            if ((bit >> i) & 1):
                continue
            for j in range(P[i]):
                if s >= G:
                    break
                s += 100 * (i+1)
                num += 1
        res = min(res, num)
print(res)

Submission status: Accepted

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

P = [D-1-i for i in range(D)]
res = INF
for x in range(2**D):
    x = str(format(x,"b"))
    x = x.zfill(D)#1であれば全部解く、0であれば解かない
    c = 0#点数
    cnt = 0#解いた問題数
    solved = []
    for i,num in enumerate(x):
        if num == "0":
            pass
        else:
            cnt += PC[i][0]
            c += (i+1)*PC[i][0]*100 + PC[i][1]
            solved.append(i)
    if c < G:
        for p in P:
            if p not in solved:
                a = min((G-c)//((p+1)*100),PC[p][0]-1)
                cnt += a
                c += a*(p+1)*100
    if c >= G:
        if cnt <= res:
            res = cnt
print(res)

Submission status: Accepted

Solution code:
from itertools import *

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

products = product(range(2), repeat=D)

ans = float("inf")

for prod in products :
    prod = list(prod)
    
    A = []
    
    cost = 0
    score = 0
    
    for i in range(len(prod)) :
        if prod[i] == 1 :
            A.append(i)
            cost += P[i]
            score += (i+1)*100*P[i]+C[i]
    
    if score < G :
        for i in range(len(prod)-1,-1,-1) :
            if prod[i] == 1 :
                continue
            
            if score + (i+1)*100*P[i] >= G :
                if G-score < 0 :
                    continue
                cost += (G-score)//((i+1)*100) + ((G-score) % ((i+1)*100) != 0)
                break
            
            else :
                cost += P[i]
                score += (i+1)*100*P[i]+C[i]
    
    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')


def rec(cur, partially_solved, solve_num, score):
    if cur == d:
        return solve_num if score >= g else inf

    res = rec(cur + 1, partially_solved, solve_num, score)
    res = min(res,
              rec(cur + 1, partially_solved, solve_num + p[cur], score + p[cur] * (cur + 1) * 100 + c[cur]))
    if not partially_solved:
        for i in range(1, p[cur]):
            res = min(res,
                      rec(cur + 1, True, solve_num + i, score + i * (cur + 1) * 100))
    return res


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

p, c = [], []
for _ in range(d):
    tp, tc = map(int, input().split())
    p.append(tp)
    c.append(tc)
print(rec(0, False, 0, 0))