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:
#!/usr/bin/env python
# coding: utf-8

# In[37]:


d, g = map(int, input().split())
pcs = [list(map(int, input().split()))for _ in range(d)]
"""
2 700
3 500
5 800

2 2000
3 500
5 800
"""


# In[ ]:


"""
完全に解くか、全くとかないかを総当たり
完全に解く問題の総score

総scoreが目標scoreを上回っている
 -> 手数を保存
scoreを下回っている
 -> 全く解いていない問題の中から 一つ選び、中途半端に解く
    scoreを上回る場合
     -> 手数に数える
    scoreを下回る場合
     -> continue
"""


# In[35]:


import math


# In[68]:


temp_str = ''
min_nb = float('inf')
# 完全、完全じゃない、全探索
for i in range(2**d):
    #print(i)
    score = 0
    solved_nb = 0
    # j桁目が1の時、j番目のpをscoreに加算
    for j in range(d):
        if (i>>j) & 1:
            score += (j+1) * 100 * pcs[j][0] + pcs[j][1]
            #temp_str += '{}ten {}mon {}perf : total {}\n'.format((j+1)*100, pcs[j][0], pcs[j][1], score)
            solved_nb += pcs[j][0]
    
    # この時点で目標scoreを超えていれば、solved_nbを保存してcontinue
    if score >= g:
        min_nb = min(min_nb, solved_nb)
        #print(temp_str)
        continue
    
    # j桁目が0の中から一つ選び、
    
    #temp_score = score
    #temp_solved_nb = solved_nb
    #print(i)
    for j in range(d):
        
        if bin(i>>j)[-1] == '0':
            #print('a', j, score)
            j_nb = math.ceil((g-score)/((j+1)*100))
            #score_judge = score + pcs[j][1]*j_nb 
            #print('b', j_nb, pcs[j][0])
            if j_nb <= pcs[j][0]-1:
                min_nb = min(min_nb, solved_nb+j_nb)
                #temp_str += '{}ten {}mon: total {}\n'.format((j+1)*100, j_nb, (j+1)*100*j_nb)
                #print(temp_str)
    #print(temp_str)
print(min_nb)


# In[ ]:

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[37]:


d, g = map(int, input().split())
pcs = [list(map(int, input().split()))for _ in range(d)]
"""
2 700
3 500
5 800

2 2000
3 500
5 800
"""


# In[ ]:


"""
完全に解くか、全くとかないかを総当たり
完全に解く問題の総score

総scoreが目標scoreを上回っている
 -> 手数を保存
scoreを下回っている
 -> 全く解いていない問題の中から 一つ選び、中途半端に解く
    scoreを上回る場合
     -> 手数に数える
    scoreを下回る場合
     -> continue
"""


# In[35]:


import math


# In[68]:


temp_str = ''
min_nb = float('inf')
# 完全、完全じゃない、全探索
for i in range(2**d):
    #print(i)
    score = 0
    solved_nb = 0
    # j桁目が1の時、j番目のpをscoreに加算
    for j in range(d):
        if (i>>j) & 1:
            score += (j+1) * 100 * pcs[j][0] + pcs[j][1]
            temp_str += '{}ten {}mon {}perf : total {}\n'.format((j+1)*100, pcs[j][0], pcs[j][1], score)
            solved_nb += pcs[j][0]
    
    # この時点で目標scoreを超えていれば、solved_nbを保存してcontinue
    if score >= g:
        min_nb = min(min_nb, solved_nb)
        #print(temp_str)
        continue
    
    # j桁目が0の中から一つ選び、
    
    #temp_score = score
    #temp_solved_nb = solved_nb
    #print(i)
    for j in range(d):
        
        if bin(i>>j)[-1] == '0':
            #print('a', j, score)
            j_nb = math.ceil((g-score)/((j+1)*100))
            score_judge = score + pcs[j][1]*j_nb 
            #print('b', j_nb, pcs[j][0])
            if j_nb <= pcs[j][0]-1 and score_judge > score:
                min_nb = min(min_nb, solved_nb+j_nb)
                temp_str += '{}ten {}mon: total {}\n'.format((j+1)*100, j_nb, (j+1)*100*j_nb)
                #print(temp_str)
    #print(temp_str)
print(min_nb)


# In[ ]:

Submission status: Accepted

Solution code:
import itertools
D, G = map(int,input().split())
PC = [list(map(int,input().split())) for _ in range(D)]
result = 10**18
for s in itertools.product(range(3), repeat = D):
    s = list(s)
    t = sorted(s, reverse=True)
    idx = 0
    SUM = 0
    ans = 0
    while True:
        if G <= SUM:
            break
        if idx == D:
            ans = 10**18
            break
        if t[idx] == 2:
            SUM += PC[s.index(2)][0] * 100 * (s.index(2)+1) + PC[s.index(2)][1]
            ans += PC[s.index(2)][0]
            s[s.index(2)] = 4
        elif t[idx] == 1:
            if G-SUM >= PC[s.index(1)][0] * 100 * (s.index(1)+1):
                SUM += (PC[s.index(1)][0]-1) * 100 * (s.index(1)+1)
                ans += PC[s.index(1)][0]-1
                s[s.index(1)] == 4
            else:
                if (G-SUM) % (100*(s.index(1)+1)) == 0:
                    ans += (G-SUM) // (100 * (s.index(1)+1))
                    break
                else:
                    ans += ((G-SUM) // (100 * (s.index(1)+1))) + 1
                    break
        idx += 1
    result = min(result, ans)
print(result)

Submission status: Accepted

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

# f(g,i) :　残りG点で、i番目の問題を最大いくつ選べるか
# i番目の問題をn問解いて、
# その得点sがGより小さかったら、f(G-s,i-1)をnに加える。
# ここでiをデクリメントするのは、完全に解く問題より高い得点の問題を
# 中途半端に解くことが最適な問題の選び方ではないため。
# i == 0 の時は float('inf') を返す。（解けない場合）
def f(G,i):
    if i == 0:
        return float("inf")
    n = min(G//(i * 100),po[i])
    s = 100 * i * n 
    if n == po[i]:
        s += co[i]
    if s < G:
        n += f(G-s,i-1)
    return min(n,f(G,i-1))

print(f(g,d))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


d, g = LI()
g //= 100
p, c = list(zip(*LIR(d)))
c = [c[i] // 100 for i in range(d)]



ans = INF
for i in range(2 ** d):
    cnt = 0
    score = 0
    for j in range(d):
        if 1 << j & i:
            cnt += p[j]
            score += (j + 1) * p[j]
            score += c[j]


    max_score = -INF
    for k in range(d):
        if not (1 << k) & i:
            max_score = max(max_score, k + 1)
    if score < g:
        remain_num = (g - score) // max_score + bool((g - score) % max_score)
        if remain_num >= p[max_score - 1]:
            continue
        cnt += remain_num
    ans = min(ans, cnt)


print(ans)

Submission status: Accepted

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

p = [0] * (D+1)
c = [0] * (D+1)

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

#print(p,c)
can = []
for k in range(2 ** D):
    x = [0] * (D+1)
    kk = k
    score = [0] * (D+1)
    count = 0
    for j in range(1,D+1):
        x[j] = kk % 2
        kk //= 2
        score[j] = x[j] * (j * p[j] + c[j]//100)
        count += x[j] * p[j]
    s = sum(score)
    deffer = G//100 - s
    num = D
    left = p[:]
    while deffer > 0 and num > 0:
        if x[num] == 1 or left[num] == 1:
            num -= 1
        else:
            deffer -= num
            left[num] -= 1
            count += 1
    if deffer <= 0:
        #print(x,count,score)
        can.append(count)

print(min(can))

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    D, G = map(int, input().split())
    problems = [[None] * 2 for _ in range(D)]
    ans = float('inf')

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

    for bit in range(1 << D):
        score = 0
        solved = 0
        unsolved = set(range(D))
        for j in range(D):
            if bit & (1 << j):
                score += problems[j][0] * (j+1) * 100 + problems[j][1]
                solved += problems[j][0]
                unsolved.discard(j)

        if score < G:
            use = max(unsolved)
            n = min(problems[use][0]-1, -(-(G - score) // ((use + 1) * 100)))
            score += n * (use + 1) * 100
            solved += n

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=float("inf")

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

    for i in range(D):
        if bit & (1 << i):
            sum=sum+pc[i][0]*(i+1)*100+pc[i][1]
            count=count+pc[i][0]
            nokori.discard(i+1)
    
    #G点に満たなければnokoriのうち一番大きいものをとく
    if sum<G:
        use=max(nokori)
        n=min(pc[use-1][0], -(-(G-sum)//(use*100)))
        count=count+n
        sum=sum+n*(use*100)
    
    if sum>=G:
        ans=min(ans, count)

print(ans)

Submission status: Accepted

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

ans = 10000
for i in range(2**D):
    s = 0
    cnt = 0
    b = [0] * D
    
    #各問題についてボーナスまで解くか手を付けないかでbit全探索
    for j in range(D):
        if (i >> j) & 1:
            s += 100 * (j + 1) * pc[j][0] + pc[j][1]
            cnt += pc[j][0]
            b[j] = 1

    #足りない点数分を解く
    flag1 = False
    flag2 = True
    if s < G:
        for k in range(D)[::-1]:
            if b[k] == 0:
                for x in range(pc[k][0]):
                    s += 100 * (k + 1)
                    cnt += 1
                    if s >= G:
                        flag1 = True
                        break
                else:
                    flag2 = False
                    break
            if flag1:
                break

    if flag2:
        ans = min(ans, cnt)


print(ans)

Submission status: Accepted

Solution code:
def solve(D, G):
    p, c = [], []

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

    each_total = []
    ans = float('inf')

    for i in range(D):
        each_total.append((p[i])*(i+1)*100+c[i])

    for j in range(1 << D):
        total_ope, total_score = 0, 0
        for k in range(D):
            if j >> k & 1:
                total_score += each_total[k]
                total_ope += p[k]
            else:
                solve_half = k

        for _ in range(p[solve_half]-1):
            if total_score >= G:
                break
            else:
                total_score += 100*(solve_half+1)
                total_ope += 1
        if total_score < G:
            continue

        ans = min(ans, total_ope)

    return ans


if __name__ == '__main__':
    D, G = map(int, input().split())
    print(solve(D, G))

Submission status: Accepted

Solution code:
from itertools import combinations

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


ans=100*10

for i in range(0,D+1):
	for v in combinations(range(D), i):
		t=0
		s=0
		for j in v:
			t+=p[j]
			s+=p[j]*(j+1)*100 + c[j]
		
		if s<G:
			for j in range(D)[::-1]:
				if j in v:
					pass
				else:
					k=(G-s)//((j+1)*100)
					t+=min(p[j]-1,k)
					s+=min(p[j]-1,k)*(j+1)*100
					
					if s>=G:break
		
		if s>=G:
			ans=min(ans,t)
		
print(ans)

Submission status: Accepted

Solution code:
#ABC 104 C - All Green

#ビット総当たりでやる

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

p=[]
c=[]

for i in range(d):
  pk, ck = map(int, input().split())
  p.append(pk)
  c.append(ck)
#print(p)
#print(c)
  
ans = 10000#仮の答え

#2^d通り試す
for i in range(2 ** d):
  #右からn番目の桁が1→n+1の配点の問題を完全に解く
  ten = 0
  mondaisu = 0
  for j in range(d):
    if (i>>j)&1 == 1:
      #p[j]個あるj+1の配点の問題を完全に解く
      ten += (j+1)*100*p[j] + c[j]
      mondaisu += p[j]
    else:
      #p[j]個あるj+1の配点の問題は完全にとかない
      k = j
  #フラグの立った配点の問題を全部といた
  if ten > g:
    if ans > mondaisu:
      ans = mondaisu
  else:
    #中途半端に解かないと行けない場合p[k]の問題を中途半端に解く
    if g-ten <= (k+1)*100*p[k] :
      mondaisu += (g-ten-1)//((k+1)*100) +1
      if ans > mondaisu:
        ans = mondaisu
      #中途半端に解いて届かない場合スルー
#  print(mondaisu)    
print(ans)

Submission status: Accepted

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

def f(G, i):
  if i == 0:
    return float('inf')
  n = min(G//(i*100), pc[i][0])
  s = n*i*100
  if n == pc[i][0]:
    s += pc[i][1]
  if s < G:
    n += f(G-s, i-1)
  return min(n, f(G,i-1))
 
print(f(G, D))

Submission status: Accepted

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

#bit全探索
ans = float('inf')
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)*p[j] + c[j]
            num += p[j]
        else:
            rest_max = j #全完でない最高得点の問題
    if s<g and rest_max >= 0:
        r = 100*(rest_max+1)
        need = ((g-s)+r-1)//r #(g-s)/rの繰り上げ
        if need >= p[rest_max]:
            continue
        num += need
    ans = min(ans,num)
print(ans)

Submission status: Accepted

Solution code:
def func():
    D, G = map(int, input().split())
    p = [0] * D 
    bonus = [0] * D
    for i in range(D):
        p[i], bonus[i] = map(int, input().split())
    
    ans = 10000
    for i in range(2 ** D):
        chosen = []
        for j in range(D):
            if ((i >> j) & 1) == 1:
                chosen.append(j)
        
        pointSum = 0
        Nsolved = 0
        for idx in chosen:
            pointSum += (idx + 1) * 100 * p[idx] + bonus[idx]
            Nsolved += p[idx]
        
        if pointSum >= G:
            ans = min(ans, Nsolved)
        else:
            notChosen = list(filter(lambda x: x not in chosen, list(range(D))))
            highestDimIdx = notChosen[-1]
            # if pointSum + (highestDimIdx + 1) * 100 * (p[highestDimIdx]-1) >= G:
            #     rest = G - pointSum
            #     Nsolved += -(-(rest // ((highestDimIdx + 1) * 100)))
            #     ans = min(ans, Nsolved)

            Nsolved += min(p[highestDimIdx] - 1, -(-(G - pointSum) // ((highestDimIdx + 1) * 100)))
            pointSum += min(p[highestDimIdx] - 1, -(-(G - pointSum) // (highestDimIdx + 1 * 100))) * (highestDimIdx + 1) * 100
            
            if pointSum >= G:
                ans = min(ans, Nsolved)
            

    print(ans)
        
if __name__ == '__main__':
    func()

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
li = []
for i in range(1,d+1):
	p,c = map(int,input().split())
	li.append([p,i*100*p+c])
ans = 10**5
for i in range(2**d):
	s = t = u =0
	for j in range(d):
		if 1&(i>>j):
			s += li[j][1]
			u += li[j][0]
		else:
			t = max(t,j+1)
	if g <= s:
		ans = min(ans,u)
	elif g <= s + t*100*(li[t-1][0]-1):
		u -= (g-s)//-(100*t)
		ans = min(ans,u)
print(ans)

Submission status: Accepted

Solution code:
import math

d, g = map(int, input().split())
ls = [[100 * (i + 1)] + list(map(int,
                                 input().split())) for i in range(d)][::-1]
l0 = [a * p + c for a, p, c in ls]

res = float('inf')
for index in range(2**d):
    cs = '{:b}'.format(index)
    cs = '0' * (d - len(cs)) + cs
    count = 0
    s = 0
    for i, c in enumerate(cs):
        if c == '1':
            count += ls[i][1]
            s += l0[i]
    if s < g:
        for i, c in enumerate(cs):
            if c == '0' and s + ls[i][0] * ls[i][1] >= g:
                n = math.ceil((g - s) / ls[i][0])
                count += n
                s += ls[i][0] * n
                break
    if s >= g:
        res = min(res, count)
print(res)

Submission status: Accepted

Solution code:
from itertools import product
import math

d, g = map(int, input().split())
ps = []
cs = []

for i in range(d):
    pi, ci = map(int, input().split())
    ps.append(pi)
    cs.append(ci)

min_count = 10000000
for pro in product([0,1,2], repeat=d):
    if len([_ for _ in pro if _ == 2]) <= 1:
        tmp_count = 0
        tmp_total = 0
        for i in range(len(pro)):
            if pro[i] == 1:
                tmp_count += ps[i]
                tmp_total += ps[i] * (i+1) * 100 + cs[i]
        if tmp_total >= g:
            min_count = min(min_count, tmp_count)
            continue
        elif 2 in pro and ps[pro.index(2)] * (pro.index(2)+1) * 100 >= g-tmp_total:
            tmp_count += -(-(g-tmp_total) // ((pro.index(2)+1) * 100))
            tmp_total += tmp_count * (pro.index(2)+1) * 100
            min_count = min(min_count, tmp_count)
            continue

print(min_count)

Submission status: Accepted

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


def function(g, i):
    if i == 0:
        return 1e9
    n = min(g // (i * 100), p_c[i][0])
    s = n * i * 100
    if n == p_c[i][0]:
        s += p_c[i][1]
    if s < g:
        n += function(g-s, i-1)
    return min(n, function(g, i-1))


print(function(g, d))

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
score_list = []
for i in range(D):
    p, c = map(int, input().split())
    score_list.append([(i + 1) * 100] * (p - 1) + [c + (i + 1) * 100])
full_score = [sum(i) for i in score_list]
sol = [format(i, 'b').zfill(D) for i in range(2 ** D)]
ans = []

for i in sol:
    problem = 0
    score = 0
    for j in range(D):
        if i[j] == '1':
            score += full_score[j]
            problem += len(score_list[j])
        else:
            continue
    if score >= G:
        ans.append(problem)
    else:
        if score + full_score[i.rfind('0')] < G:
            continue
        else:
            while score < G:
                score += score_list[i.rfind('0')][0]
                problem += 1
            ans.append(problem)

print(min(ans))

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
P,C = map(list,zip(*[list(map(int,input().split())) for i in range(D)]))
Solved = []
for i in range(2**D):
    bit = bin(i)[2:].zfill(D)
    solved = 0
    score = 0
    for j in range(D):
        if bit[j] == '1':
            score += (j+1)*100*P[j]+C[j]
            solved += P[j]
    if G-score > 0:
        for j in range(D):
            if bit[-j-1] == '0':
                for k in range(P[-j-1]-1):
                    score += (D-j)*100
                    solved += 1
                    if G-score <= 0:
                        break
            if G-score <= 0:
                break
    if G-score <= 0:
        Solved += [solved]
print(min(Solved))

Submission status: Accepted

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

def recursive(d, g):
    if d == 0:
        return 10 ** 9
    n = min(g // (100 * d), p[d][0])
    t = 100 * d * n
    # Full
    if n == p[d][0]:
        t += p[d][1]
    # Partial
    if t < g:
        n += recursive(d-1, g-t)
    return min(n, recursive(d-1, g))

def bit(d, g):
    ans = 10 ** 9
    for i in range(2 ** d):
        b = '-' + format(i, '0{}b'.format(d))
        last_zero_index = 0
        tmp_ans = 0
        total_score = 0
        for j in range(1, d+1):
            if b[j] == '1':
                total_score += p[j][0] * (100 * (j))
                total_score += p[j][1]
                tmp_ans += p[j][0]
            else:
                last_zero_index = j
        if total_score < g:
            diff = g - total_score
            q = diff // (100 * last_zero_index)
            r = diff % (100 * last_zero_index)
            if r != 0:
                q += 1
            if q > p[last_zero_index][0]:
                continue
            else:
                tmp_ans += q
        ans = min(ans, tmp_ans)
    return ans

solve = recursive
#solve = bit
print(solve(d, g))

Submission status: Accepted

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

def recursive(d, g):
    if d == 0:
        return 10 ** 9
    n = min(g // (100 * d), p[d][0])
    t = 100 * d * n
    # Full
    if n == p[d][0]:
        t += p[d][1]
    # Partial
    if t < g:
        n += recursive(d-1, g-t)
    return min(n, recursive(d-1, g))

def bit(d, g):
    ans = 10 ** 9
    for i in range(2 ** d):
        b = '-' + format(i, '0{}b'.format(d))
        last_zero_index = 0
        tmp_ans = 0
        total_score = 0
        for j in range(1, d+1):
            if b[j] == '1':
                total_score += p[j][0] * (100 * (j))
                total_score += p[j][1]
                tmp_ans += p[j][0]
            else:
                last_zero_index = j
        if total_score < g:
            diff = g - total_score
            q = diff // (100 * last_zero_index)
            r = diff % (100 * last_zero_index)
            if r != 0:
                q += 1
            if q > p[last_zero_index][0]:
                continue
            else:
                tmp_ans += q
        ans = min(ans, tmp_ans)
    return ans

#solve = recursive
solve = bit
print(solve(d, g))

Submission status: Accepted

Solution code:
d, g = list(map(int, input().split()))
pc = [list(map(int, input().split())) for i in range(d)]
ans = float("INF")

for i in range(2**d):
  num = 0
  score = 0
  for j in range(d):
    if i&(1<<j):
      num += pc[j][0]
      score += (j+1)*100*pc[j][0] + pc[j][1]
  j = d-1
  while score<g and j>=0:
    if i&(1<<j) == 0:
      rem = g-score
      tmax = (j+1)*100*pc[j][0]
      if rem>=tmax:
        num += pc[j][0]
        score += tmax
      else:
        for k in range(1, pc[j][0]):
          num += 1
          score += (j+1)*100
          if score>=g:
            break
    j -= 1
  if score>=g:
    ans = min(ans, num)
print(ans)

Submission status: Accepted

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

def solve(goal, d):
  if d == 0:
    return 10**9
  n = min(goal//(100*d), pc[d][0])
  t = n * d * 100
  if n == pc[d][0]:
    t += pc[d][1]
  if t < goal:
    n += solve(goal-t, d-1)
  return min(n, solve(goal,d-1))

print(solve(goal,d))

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
p,c = [],[]
for i in range(D):
  tmp0 ,tmp1 = map(int,input().split())
  p.append(tmp0)
  c.append(tmp1)
  
min_ans = float('inf')

for bit in range(1<<D):
  dont_solved = [i for i in range(D)]
  ans = 0
  sum_point = 0
  for i in range(D):
    if bit & 1<<i:
      ans += p[i]
      sum_point += (i+1)*100*p[i]+c[i]
      dont_solved.remove(i)
  if sum_point < G:
    for i in  dont_solved[::-1]:
      for j in range(p[i]):
        ans += 1
        sum_point += (i+1)*100
        if sum_point >= G:
          break
      else:
        continue
      break
  
  if ans <= min_ans:
    min_ans = ans
print(min_ans)

Submission status: Accepted

Solution code:
import copy
n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
b = [((i+1)*100*name[0] + name[1]) for i, name in enumerate(a)]

ans = []
pat = []
for i in range(2**n):
    pat_c = []
    sum1 = 0
    count1 = 0
    for j in range(n):
        t = (i // 2 ** j) % 2
        pat_c.append(t)
        if  t == 1:
            sum1 += b[j]
            count1 += a[j][0]

    if sum1 < m and 0 in pat_c:
        tyuu1_index = len(pat_c) - pat_c[::-1].index(0) - 1
        tyuu1 = a[tyuu1_index]
        if (tyuu1_index + 1)*100*tyuu1[0] < (m - sum1):
            continue
        else:
            count1 += (m-sum1) // ((tyuu1_index + 1)*100)
            if (m-sum1) % ((tyuu1_index + 1)*100) != 0:
                count1 += 1
        ans.append(count1)
        pat.append(pat_c)
    else:
        ans.append(count1)
        pat.append(pat_c)

print(min(ans))

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    D,G = map(int, input().split())
    qs = [list(map(int, input().split())) for _ in range(D)]
    q_totals = [100*(i+1)*q[0]+q[1] for i,q in enumerate(qs)]

    ans = float('inf')
    for bit in range(1<<D):
        total = 0
        target_qs = []
        another_q_idx = 0
        for i in range(D):
            if bit & 1<<i:
                total += q_totals[i]
                target_qs.append(qs[i])
            else:
                another_q_idx = i
        tmp_ans = sum([q[0] for q in target_qs])

        if total < G and G <= total + 100*(another_q_idx+1)*(qs[another_q_idx][0]-1):
            tmp_ans += ceil((G-total)/(100*(another_q_idx+1)))
        elif total + 100*(another_q_idx+1)*(qs[another_q_idx][0]-1) < G:
            tmp_ans = float('inf')

        ans = min(ans, tmp_ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    d, g = map(int, input().split())
    lp, lc = [], []
    while True:
        try:
            p, c = map(int, input().split())
            lp.append(p)
            lc.append(c)
        except EOFError:
            break

    num = sum(lp)
    for i in range(2**d):
        cnt = 0
        scr = 0
        lcn = [0]*d
        for j in range(d):
            if (i // 2**j)%2 == 1:
                cnt += lp[j]
                scr += 100*(j+1)*lp[j]+lc[j]
                lcn[j] += 1
        for j in range(d-1, -1, -1):
            if cnt < num and scr >= g:
                num = cnt
                break
            if lcn[j] == 0:
                for k in range(lp[j]):
                    cnt += 1
                    scr += 100*(j+1)
                    if cnt < num and scr >= g:
                        num = cnt
                        break
                break
    print(num)
resolve()

Submission status: Accepted

Solution code:
from itertools import product
 
D, G = map(int, input().split())
score = []
for i in range(D):
    p, c = map(int, input().split())
    s = (i + 1) * 100
    score.append([s, p, c, s * p + c])
 
ans = float('inf')
for ptn in product([0, 1], repeat=D):
    total = 0
    cnt = 0
    for i in range(D):
        total += score[i][3] * ptn[i]
        cnt += score[i][1] * ptn[i]
 
    if 0 in ptn[::-1]:
        i = D - 1 - ptn[::-1].index(0)
        x = score[i]
    else:
        x = score[-1]
 
    for i in range(x[1]):
        if total >= G:
            break
        total += x[0]
        cnt += 1
 
    if total < G:
        cnt = float('inf')
    ans = min(ans, cnt)
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 bit in range(2**D):
	wa = 0
	cnt = 0
	for i in range(D):
		if (bit & (1<<i)):
			wa += (i+1)*100*P[i]+C[i]
			cnt += P[i]
		
	for i in range(D-1,-1,-1):
		if wa >= G:
			break
		if bit & (1<<i):
			continue
		s = (i+1)*100
		need = (G-wa+s-1)//s
		wa += min(need,P[i])*s
		cnt += min(need,P[i])

	if wa >= G:
		ans  = min(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
def main():
    D, G = [int(i) for i in input().split()]
    p = []
    c = []
    for i in range(D):
        pp, cc = [int(i) for i in input().split()]
        p.append(pp); c.append(cc)
    ans = 1e9
    for mask in range(1<<D):
        s = 0; num = 0; rest_max = -1
        for i in range(D):
            # どのビットが立っているか確認する
            if mask >> i & 1:
                # i 番目の問題を全完した時の点数を追加する
                s += 100 * (i+1) * p[i] + c[i]
                num += p[i]
            else:
                # ビットが立っていない点数が一番高い問題のメモ
                # 足りなかったらここから解いて点数を追加する
                # 残ったやつ 1 つだけを見ればばいい
                # なぜなら、bit全探索で、他のパターンは自動的に出るから
                rest_max = i
        if s < G:
            # rest_max 番目の点数をあらかじめ計算しておく
            s1 = 100 * (rest_max+1)
            # 目標 - 今まで解いた問題の得点 + rest_max 番目の問題の得点 - 1
            need = (G - s + s1 - 1) // s1 # max になってはいけない
            if need >= p[rest_max]:
                continue
            num += need
        ans = min(ans, num)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = float("inf")
bi = [0,1]
import itertools

for i in list(itertools.product(bi, repeat=D)):
    tmp = 0
    p = 0
    for j in range(D):
        if i[j] == 1:
            p += PC[j][1]
            p += PC[j][0]*100*(j+1)
            tmp += PC[j][0]
    for j in range(D):
        k = D-1-j
        if p >= G:
            break
        if i[k] == 0:
            tmp += min(PC[k][0]-1,-(-(G-p)//(100*(k+1))))
            p += min(PC[k][0]-1,-(-(G-p)//(100*(k+1)))) * (100*(k+1))
            
    if ans > tmp and p>=G:
        ans = tmp


print(ans)