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:
from math import ceil
from itertools import product

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

ans = 1000
for pat in product(["1", "0"], repeat=d):
    score = 0
    cnt = 0
    not_complete = 0
    for i, bl in enumerate(pat):
        if bl == "1":
            score += 100 * (i + 1) * pc[i][0] + pc[i][1]
            cnt += pc[i][0]
        else:
            not_complete = i

    if score < g:
        add = ceil((g - score) / (100 * (not_complete + 1)))
        if add < pc[not_complete][0]:
            cnt += add
        else:
            continue

    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
# コンプリートボーナスをとる問題をbinで全列挙
# その条件でgreedyすればよい
# O(D*P * 2^D):100*10*1024~10^6

D,G = map(int,input().split())
PC = [tuple(map(int,input().split())) for i in range(D)]
ans = 10**3+19
for i in range(2**D):
    score = 0
    solved = 0
    ps = [PC[j][0] for j in range(D)]
    s = bin(i)[::-1][:-2] # なおしたい
    for j in range(len(s)):
        if s[j] == '1':
            score += PC[j][1]
            score += PC[j][0]*100*(j+1)
            solved += ps[j]
            ps[j] = 0
    i = -1
    while G > score:
        if i < -D:
            solved = 10**3+19
            break
        if ps[i] == 0:
            i -= 1
        else:
            ps[i] -= 1
            score += (D+i+1)*100
            solved += 1
    ans = min(ans,solved)
print(ans)

Submission status: Accepted

Solution code:
import math

# print('input >>')
D, G = map(int, (input().split()))
pc = []
for _ in range(D):
    p, c = map(int, (input().split()))
    pc.append((p, c))

point = 0
ans = []

def dfs(i, count, point):
    # Gまで到達したかどうか確かめる
    c_ = count
    if point >= G:
        ans.append(count)
        return
    # 途中まで解いてGまで届くかどうか試す
    if point + (i + 1) * 100 * (pc[i][0] - 1) >= G:
        count += math.ceil((G - point) / ((i + 1) * 100))
        ans.append(count)
    # 全部解いてGまで届くかどうか試す
    elif point + (i + 1) * 100 * pc[i][0] + pc[i][1] >= G:
        count += pc[i][0]
        ans.append(count)
    if i == 0:
        return
    # 完全に解く
    dfs(i-1, c_+pc[i][0], point + (i+1)*100 * pc[i][0] + pc[i][1])
    # 完全に解かない
    dfs(i-1, c_, point)

dfs(D-1,0,0)

# print('----------output----------')
print(min(ans))

Submission status: Accepted

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

G = G//100

problems = []

for i in range(D):
    p, c = map(int, input().split())
    problems.append((p, c//100))

ans = 10000

for i in range(1 << D):
    score = 0
    num = 0
    for j in range(D):
        comp = 1 << j
        if i & comp:
            score += (j+1) * problems[j][0] + problems[j][1]
            num += problems[j][0]
    if score < G:
        for k in range(D-1, -1, -1):
            comp = 1 << k
            if not i & comp:
                for l in range(problems[k][0]-1):
                    score += k + 1
                    num += 1
                    if score >= G:
                        break
                else:
                    continue
                break
    if score >= G and ans > num:
        ans = num

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)

anslist = []
def dfs(i, total, count, nokori):
    # print("i = {}, total = {}, count = {}, nokori = {}".format(i, total, count, nokori))


    if G <= total:
        anslist.append(count)
        # print("    G: count = {}".format(count))
        return
    if i == D:
        if G > total:
            if len(nokori) == 0:
                return
            for c in sorted(list(nokori), reverse=True):
                for _ in range(P[c]):
                    total += 100*(c+1)
                    count += 1
                    if G <= total:
                        anslist.append(count)
                        # print("        G: count = {}".format(count))
                        return
                # print("    c = {}, total = {}".format(c, total))
        return
    dfs(i+1, total, count, nokori)
    dfs(i+1, total + 100*(i+1)*P[i]+C[i], count + P[i], nokori - {i})

dfs(0, 0, 0, set(range(D)))
print(min(anslist))

Submission status: Accepted

Solution code:
import math
D, G = [int(x) for x in input().split()]
PC = [[int(x) for x in input().split()] for _ in range(D)]
ans = 100100
for i in range(2**D):
    cnt = 0
    point = 0
    for j in range(D):
        if (i >> j) & 1:
            cnt += PC[j][0]
            point += 100 * (j+1) * PC[j][0] + PC[j][1]
    if (point < G):
        rest = G-point
        for j in range(D)[::-1]:
            if (i >> j) & 1 == 0:
                if (rest < 100*(j+1)*PC[j][0]):
                    # 200点問題3問で500点
                    cnt += math.ceil(rest / (100*(j+1)))
                    break 
                else:
                    cnt = 100100
                    break
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
D, G = [int(x) for x in input().split()]
PC = [[int(x) for x in input().split()] for _ in range(D)]
ans = 100100
for i in range(2**D):
    cnt = 0
    point = 0
    for j in range(D):
        if (i >> j) & 1:
            cnt += PC[j][0]
            point += 100 * (j+1) * PC[j][0] + PC[j][1]
    if (point < G):
        rest = G-point
        for j in range(D)[::-1]:
            if (i >> j) & 1 == 0:
                if (rest < 100*(j+1)*PC[j][0]):
                    # 200点問題3問で500点
                    cnt += -(-rest // (100*(j+1)))
                    break 
                else:
                    cnt = 100100
                    break
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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

counts = []
def calc(i, count, total, last):
  if G <= total:
    counts.append(count)
    return
  if i >= D:
    for x in range(PnC[last][0]):
      if G <= total + 100*x*(last+1):
        counts.append(count + x)
        return
    return
  calc(i+1, count, total, i)
  calc(i+1, count+PnC[i][0], total+PnC[i][1]+100*(i+1)*PnC[i][0], last)

calc(0, 0, 0, 0)
print(min(counts))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline

D, G = [int(x) for x in input().strip().split()]
P = [''] * D
for d in range(D):
    p, c = [int(x) for x in input().strip().split()]
    P[d] = [0] + [(d + 1) * 100 * (i + 1) for i in range(p)]
    P[d][-1] += c

d = defaultdict(int)
def f(P, D, qnum, trial, d, flag=False, score=[]):
    if (qnum, trial, sum(score)) in d:
        return d[(qnum, trial, sum(score))]
    #print('qnum={}, trial={}, score={}'.format(qnum,trial,score))
    if qnum == D:
        if sum(score) >= G:
            #print('  OK : {}'.format(trial))
            return trial
        else:
            #print('  NG')
            return 10 ** 9 + 7
    ret = 10 ** 9 + 7
    if flag:
        N = [0, len(P[qnum])-1]
    else:
        N = range(len(P[qnum]))
    for n in N:
        flag2 = flag
        t = score[:]
        t.append(P[qnum][n])
        if not flag and n != len(P[qnum]) - 1 and n != 0:
            flag2 = True
        ret = min(ret, f(P, D, qnum+1, trial+n, d, flag2, t))
    d[(qnum, trial, sum(score))] = ret
    return ret

print(f(P, D, 0, 0, d))

Submission status: Accepted

Solution code:
d, g = map(int,input().split())
p=[0]*d
c=[0]*d
for i in range(d):
    p[i], c[i] = map(int,input().split())
import numpy as np
import math
b = 2**d
pnum = np.array(p)
cnum = np.array(c)
ans = 10**30
score_comp = np.zeros(d)
for di in range(d):
    score_comp[di] = pnum[di]*(100*(di+1))+cnum[di]

for i in range(b):
    comp_str = bin(i)[2:].zfill(len(bin(b-1))-2)
    comp_num = np.array([float(j) for j in list(comp_str)])
    comp_cnt = int((comp_num*pnum).sum())
    total_comp_score = (comp_num*score_comp).sum()
    if total_comp_score >= g:
        if ans > comp_cnt:
            ans = comp_cnt
    else:
        rest = g-total_comp_score
        rest_id = comp_str.rfind('0')
        if rest_id>=0:
            rest_cnt = math.ceil(rest/(rest_id+1)/100)
            if pnum[rest_id] > rest_cnt:
                if (ans > comp_cnt + rest_cnt):
                    ans = comp_cnt + rest_cnt
print(ans)

Submission status: Accepted

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

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

def AccuracyQestionNum(acc_list, count):
    counter = count
    for i in range(len(acc_list)):
        if acc_list[i] == 1:
            counter += p[i]
    return counter

def MaxScoreIndex(acc_list):
    for i in reversed(range(len(acc_list))):
        if acc_list[i] == 0:
            return i
        
def FinalQestionNum(acc_list, score):
    remain_point = G - score
    counter = 0
    max_score_index = MaxScoreIndex(acc_list)
    for i in range(p[max_score_index]):
        remain_point -= (max_score_index+1) * 100
        counter += 1
        if remain_point <= 0:
            break

    if counter == p[max_score_index]:
        return None
    else:
        return counter
        
def ScoreCalculation(acc_list):
    score = 0
    for i in range(len(acc_list)):
        if acc_list[i] == 1:
            score += (i+1) * 100 * p[i]
            score += c[i]
    return score

def DFSQestion(acc_list):
    """先に全探索で得たスコアを計算して, 正解数もカウントしておく"""
    if len(acc_list) == D:
        score = ScoreCalculation(acc_list)
        if score >= G:
            question_num = AccuracyQestionNum(acc_list, 0)
        else:
            count = FinalQestionNum(acc_list, score)
            if count == None:
                return None
            else:
                question_num = AccuracyQestionNum(acc_list, count)
        return question_num
    else:
        question_num1 = DFSQestion(acc_list + [0])
        question_num2 = DFSQestion(acc_list + [1])
        if question_num1 == None:
            return question_num2
        if question_num2 == None:
            return question_num1
        if question_num1 >= question_num2:
            return question_num2
        else:
            return question_num1
        
question_num = DFSQestion([])

print(question_num)



"""
全ての問題に対する全探索(おバカな探索)
sum_question  = 0
for i in range(D):
    sum_question += p[i]

def ScoreCalculation(question_list):
    pre_i = 0
    count = 0
    score = 0
    for p_i in range(len(p)):
        count = sum(question_list[pre_i : pre_i + p[p_i]])
        pre_i += p[p_i]
        score += (p_i+1) * 100 * count
        if count == p[p_i]:
            score += c[p_i]
        
    return score

def DFSAccuracy(question_list):
    if len(question_list) == sum_question:
        score = ScoreCalculation(question_list)
        if score >= G:
            return question_list
        else:
            return None
    else:
        result1 = DFSAccuracy(question_list + [1])
        result2 = DFSAccuracy(question_list + [0])

        if result1 == None:
            return result2
        elif result2 == None:
            return result1
        else:
            que_num1 = sum(result1)
            que_num2 = sum(result2)
            if  que_num1< que_num2:
                return result1
            else:
                return result2

ans_list = DFSAccuracy([])
accuracy_num = sum(ans_list)
print(accuracy_num)
"""

Submission status: Accepted

Solution code:
n,g = map(int, input().split())
standard = []
bonus = []
num_of_problems = []
for i in range(n):
    a,b = map(int, input().split())
    standard.append(a * (i+1) * 100)
    bonus.append(b)
    num_of_problems.append(a)
points_after_completion = []
min_num = 10 * 100
for i in range(2**n):
    point = 0
    num = 0
    li = list(range(n))
    for j in range(n):
        if (i >> j) & 1:
            point += standard[n-j-1] + bonus[n-j-1]
            num += num_of_problems[n-j-1]
            li.remove(n-j-1)
    counter = 0
    if li != []:
        while point < g and counter <= num_of_problems[li[-1]]:
            point += 100 * (li[-1]+1)
            num += 1
            counter += 1
    if num < min_num and point >= g:
        min_num = num
print(min_num)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
P = [0]*D
C = [0]*D
for i in range(D):
    P[i], C[i] = map(int,input().split())
s = sum(P)

#dp[i][j] = i問目まででj枚使った時の点数のmax#
dp = [[0 for i in range(s+1)] for j in range(D+1)]
for i in range(D):
    p = P[i]
    c = C[i]
    t = 100*(i+1)
    for j in range(s+1):
        for k in range(p+1):
            if k == p:
                if j >= k:
                    dp[i+1][j] = max(dp[i+1][j],dp[i][j-k]+c+t*k)
            else:
                if j >= k:
                    dp[i+1][j] = max(dp[i][j-k]+t*k,dp[i+1][j])
                else:
                    break
for i in range(s+1):
    if dp[D][i] >= G:
        ans = i
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from math import ceil
    d,g=map(int,input().split())
    g//=100
    P=[0]*d
    C=[0]*d
    for i in range(d):
        p,c=map(int,input().split())
        c//=100
        P[i],C[i]=p,c

    def check(S):
        comp=[0]*d
        for i in range(d):
            comp[i]=S&1
            S>>=1
        score=0
        cnt=0
        for i in range(d):
            if(comp[i]):
                score+=(i+1)*P[i]+C[i]
                cnt+=P[i]

        # コンプした問題だけでクリアしていれば返す
        if(score>=g):
            return cnt

        # そうでなければ、解いてない問題のうち最大点数のものを何問解くか考える
        idx=-1
        for i in range(d-1,-1,-1):
            if(comp[i]==0):
                idx=i
                break

        if(idx==-1):
            return False


        k=ceil((g-score)/(idx+1))
        if(k<P[idx]):
            return cnt+k
        else:
            return False


    # completeする問題を全て試す
    ans=INF
    for S in range(2**d):
        score=check(S)
        if(score): ans=min(score,ans)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
#ALl green
import math
d,g=map(int,input().split())
lists=[tuple(map(int,input().split())) for i in range(d)]
A=[]
for _ in range(2**d):
    lis=[]
    G=0
    G+=g
    counter=0
    strings=format(_,"0%ib"%d)
    strings=strings[::-1]
    for i in range(d):
        if strings[i]=="1":
            G-=(lists[i][0]*100*(i+1)+lists[i][1])
            counter+=lists[i][0]
        else:
            lis.append((lists[i][0],(i+1)*100))
    if G<=0:
        A.append(counter)
    else:
        lis=sorted(lis,key=lambda x:x[1],reverse=True)
        lis.append("END")
        #Gは0よりも大きく、lisに残ったものからcomplete しないようにしつつ引いていく
        flag=True
        for some in lis:
            if not(G>0 and flag):
                break            
            if some=="END":
                flag=False
            else:
                limit=some[0]-1
                number=some[1]
                if G>limit*number:
                    G=G-number*limit
                    counter+=limit
                else:
                    P=math.ceil(G/number)
                    counter=counter+P
                    A.append(counter)
                    flag=False

        if G<=0:
            A.append(counter)

print(min(A) )

Submission status: Accepted

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

ans=sum(p)
for k in range(1<<D):
    s=[i for i in range(1,D+1) if k>>(i-1)&1]
    t=sorted([j for j in range(1,D+1) if j not in s],reverse=True)

    ac=sum([p[i] for i in s])
    score=sum([100*i*p[i]+c[i] for i in s])

    for j in t:
        if score>=G:
            break
        q=(G-score+(j-1)*100)//(j*100)
        if q>=p[j]:
            ac+=p[j]-1
            score+=(j*100)*(p[j]-1)
        else:
            ac+=q
            score+=(j*100)*q
    if score>=G:
        ans=min(ans,ac)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
d, g = map(int, input().split())
p = []
c = []
for _ in range(d):
    _p, _c = map(int, input().split())
    p.append(_p)
    c.append(_c)

s = np.arange(1, d + 1) * 100
p = np.array(p)

ans_list = []

bool_list = [False] * d

state_list = []

def dfs(i, n, bool_list):
    bool_list = bool_list.copy()
    if i == n:
        state_list.append(bool_list)
    else:
        dfs(i + 1, n, bool_list)
        bool_list[i] = True
        dfs(i + 1, n, bool_list)

dfs(0, d, bool_list)

for state in state_list:
    if np.dot(s * p, state) + np.dot(c, state) >= g:
        ans_list.append(np.dot(p, state))
    else:
        score = max(s * np.array([not i for i in state]))
        for j in range(1, p[score//100 - 1] + 1):
            if np.dot(s * p, state) + np.dot(c, state) + score * j >= g:
                ans_list.append(np.dot(p, state) + j)

print(min(ans_list))

Submission status: Accepted

Solution code:
#ABC104C - All Green
import math
def dfs(i,s,c,r):
    global ans
    if i == d:
        if s < g:
            use = max(r)
            n = min(pc[use -1][0], math.ceil((g-s)/(use*100)))
            c += n
            s += n*use*100
        if s >= g:
            ans = min(ans,c)
    
    else:
        dfs(i+1, s, c, r)
        dfs(i+1, s+ pc[i][0]*(i+1)*100+pc[i][1],c+pc[i][0],r-{i+1})
        
d,g = list(map(int,input().split()))
pc = [list(map(int,input().split())) for i in range(d)]

ans = float("inf")

dfs(0,0,0,set(range(1,d+1)))
print(ans)

Submission status: Accepted

Solution code:
import math
D,G=[int(s) for s in input().split()]
ls=[[int(s) for s in input().split()] for i in range(D)]
maxD=2**D-1
def need(num):
  val=num
  score=0
  prob=0
  for i in range(D):
    if val%2==1:
      score+=ls[i][0]*(i+1)*100+ls[i][1]
      prob+=ls[i][0]
    val//=2
  if score>=G:
    return prob
  else:
 #   print(score)
    k=int(math.log2(num^maxD))
    x=(score-G)//((k+1)*100)
    if -x<=ls[k][0]:
      return -x+prob
    else:
      return 10000
print(min([need(i) for i in range(2**D)]))

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
pc = []
m = 0
for i in range(d):
  pc.append(list(map(int,input().split())))
  m += pc[-1][0]
for i in range(2**d-1):
  cur = bin(i)[2:]
  cur = '0'*(d-len(cur)) + cur
  csum = 0
  cc = 0
  for j in range(d):
    if cur[j] == '0':
      ci = j
    else:
      csum += (j+1)*100*pc[j][0] + pc[j][1]
      cc += pc[j][0]
  if csum >= g:
    m = min(m,cc)
  elif csum + (ci+1) * 100 * pc[ci][0] >= g:
      m = min(m,cc+(g-csum-1)//(100*(ci+1))+1)
print(m)

Submission status: Accepted

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

ans = []
for i in range(2**d):
    score = target
    ans_temp = 0
    for j in range(d-1,-1,-1):
        if score <= 0:
            break
        if (i >> j) & 1:
            for k in range(problem[j][0]):
                score -= 100*(j+1)
                ans_temp += 1
                if score <= 0:
                    break
            score -= problem[j][1]
    if score <= 0:
        ans.append(ans_temp)
print(min(ans))

Submission status: Accepted

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

for i in range(2**D):
    score = 0
    tmp_ans = 0
    used = [0]*D
    for j in range(D):
        if (i>>j) & 1:
            score += pc[j][0]*(100*(j+1)) + pc[j][1]
            tmp_ans += pc[j][0]
            used[j] = 1
    
    if score >= G:
        ans = min(ans, tmp_ans)
    else:
        for j in range(D-1, -1, -1):
            if (used[j] == 0 and 0 <= (G-score-1)//(100*(j+1))+1 <= pc[j][0]):
                tmp_ans += (G-score-1)//(100*(j+1))+1
                score += ((G-score-1)//(100*(j+1))+1)*(100*(j+1))
            if score >= G:
                ans = min(ans, tmp_ans)
                break

print(ans)

Submission status: Accepted

Solution code:
(d,g),*l=[list(map(int,i.split()))for i in open(0)]
def f(i,g):
	if i==0:return 1e9
	n,m=l[i-1];c=min(g//(100*i),n);s=100*i*c+m*(c==n);c+=f(i-1,g-s)*(s<g);return min(c,f(i-1,g))
print(int(f(d,g)))

Submission status: Accepted

Solution code:
from itertools import*
from math import*
d,g=map(int,input().split())
g//=100
xxx=[tuple([i])+tuple(map(int,input().split()))for i in range(1,d+1)]   #問題数 ボーナス
#print(xxx)
yyy=[(score,score*num+bonus//100,num)for score,num,bonus in xxx]
ans=[]
l=[]
for i in range(d+1):
    for j in combinations(yyy,i):
        tmp1=0
        tmp2=0
        tmpl=set()
        for x,y,z in j:
            tmp1+=y
            tmp2+=z
            tmpl.add(x)
        if tmp1>=g:
            ans.append(tmp2)
        else:
            l.append((tmpl,g-tmp1,tmp2))  
#print(ans)
#print(l)
for s,t,r in l:  #使ったもの 必要なスコア そこまでの枚数
    for x,y,_ in xxx[::-1]:  #スコア 枚数
        if x not in s:
            if x*y<=t:
                break
            else:
#                print(r,t,x)
                ans.append(r+ceil(t/x))

print(min(ans))

Submission status: Accepted

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

for i in range(1<<D):
    point = 0
    count = 0
    for j in range(D, 0, -1):
        if i>>j-1&1:
            point += j * 100 * P[j] + C[j]
            count += P[j]
    for k in range(D, 0, -1):
        if not i>>k-1&1 and P[k] > 1:
            for _ in range(P[k]-1):
                if point < G:
                    point += k * 100
                    count += 1
                else:
                    break
            if point >= G:
                ans = min(ans, count)
            break
print(ans)

Submission status: Accepted

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

def calc(k):
    s = G
    a = 0
    for i in range(D):
        if k & (1<<i):
            a += X[i][0]
            s -= X[i][0] * (i+1) * 100 + X[i][1]
    if s <= 0:
        return a
    for i in range(D)[::-1]:
        if k & (1<<i) == 0:
            if s > X[i][0] * (i+1) * 100:
                return 1<<100
            else:
                a += -(-s//((i+1) * 100))
                break
    return a

mi = 1 << 100
for j in range(1<<D):
    mi = min(mi, calc(j))
print(mi)

Submission status: Accepted

Solution code:
d,g= map(int,input().split())
p_c = [input() for i in range(d)]
pc =[]
for j in range(d):
  p,c = map(int,p_c[j].split())
  pc.append([p,c])
ans = []
for x in range(2**d):
  count = 0
  total = 0
  tokanai = []
  for y in range(d):
    if (x >> y) & 1 == 1:
      count += pc[y][0]
      total += pc[y][0] * (y+1)*100 + pc[y][1]
    else:
      tokanai.append([pc[y][0],(y+1)*100])
  if total < g and g-total <= (max(tokanai)[0]-1)*max(tokanai)[1]:
    di = g-total
    for k in range(max(tokanai)[0]):
      if di - ((k+1) * max(tokanai)[1]) <= 0:
        count += k+1
        ans.append(count)
  elif total >= g:
    ans.append(count)
print(min(ans))

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p = []
c = []
ans = 10 ** 9
for i in range(D):
    p_i, c_i = map(int, input().split())
    p.append(p_i)
    c.append(c_i)

for i in range(2 ** D):
    score = 0
    count = 0
    for j in range(D):
        if (i >> j) & 1:
            score += c[j] + p[j] * 100 * (j + 1)
            count += p[j]
    for k in range(D - 1, -1, -1):
        if (i >> k) & 1:
            continue
        if score >= G:
            break
        for l in range(p[k] + 1):
            score += 100 * (k + 1)
            count += 1
            if score >= G:
                break
    ans = min(ans, count)

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(G,i):
  if i==0:
    return 1e9
  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:
import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    d, g = list(map(int, input().rstrip('\n').split()))
    pc = [[(i + 1) * 100, pc[0], pc[1]]for i, pc in enumerate(list(map(int, input().rstrip('\n').split())) for _ in range(d))]
    pc.sort(reverse=True)
    min_cnt = 10 ** 10
    for v in itertools.product([True, False], repeat=d):
        cnt = 0
        t = 0
        max_p = -1
        limit_c = -1
        for i, vv in enumerate(v):
            if vv:
                cnt += pc[i][1]
                t += pc[i][0] * pc[i][1] + pc[i][2]
            else:
                if max_p < pc[i][0]:
                    max_p = pc[i][0]
                    limit_c = pc[i][1]
        if t >= g:
            min_cnt = min(min_cnt, cnt)
        else:
            if 1 <= (g - t + max_p - 1) // max_p <= limit_c:
                min_cnt = min(min_cnt, cnt + (g - t + max_p - 1) // max_p)
    print(min_cnt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import math

d,g = map(int,input().split())
pl = []
cl = []

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

ans = float('inf')
for i in range(2 ** d):
    op = [0] * d
    for j in range(d):
        if ((i >> j) & 1):
            op[j] = 1  # フラグが立っていた箇所を "+" で上書き

    tmp_ans = 0
    tmp_point = 0
    
    for idx, (o,p,c) in enumerate(zip(op, pl, cl)):
        tmp_ans += o*p
        tmp_point += o*c + (idx+1) * 100 * p*o
        
    
    for k in range(d-1, -1, -1):
        if (i >> k) & 1: 
            continue
        if tmp_point >= g:
            break
        for l in range(pl[k] + 1):
            tmp_point += 100 * (k + 1)
            tmp_ans += 1
            if tmp_point >= g:
                break
    if ans > tmp_ans:
        ans = tmp_ans
print(ans)

Submission status: Accepted

Solution code:

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

ans = 10 ** 9
for i in range(2 ** d):
    score = 0
    count = 0
    for j in range(d):
        if (i >> j) & 1: 
            score += p_c[j][1] + p_c[j][0] * 100 * (j + 1)
            count += p_c[j][0]
    for k in range(d - 1, -1, -1):
        if (i >> k) & 1: 
            continue
        if score >= g:
            break
        for l in range(p_c[k][0] + 1):
            score += 100 * (k + 1)
            count += 1
            if score >= g:
                break
    if ans > count:
        ans = count
print(ans)

Submission status: Accepted

Solution code:
import copy
from collections import deque
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = inf

D, G = LI()

P = [0]*D
c = [0]*D
p = [0]*D

for i in range(D):
    P[i], c[i] = LI()

full = [0]*D
for i in range(D):
    full[i] = 100*(i+1)*P[i] + c[i]

for i in range(2**D):
    ansC = int(0)
    p = copy.deepcopy(P)
    candi = [i for i in range(D)]
    cur = int(0)
    for j in range(D):
        if ((i >> j) & 1):
            cur += full[D-j-1]
            ansC += p[D-j-1]
            candi.remove(D-j-1)

    remain = G - cur
#    print(candi,remain,ansC)
    while(candi and remain>0):
        remain -= (candi[-1]+1)*100
        p[candi[-1]] -=1
#        print(p)
        ansC +=1
        if p[candi[-1]]==0:
            candi.remove(candi[-1])

    ans = min(ansC,ans)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
D, G = [int(x) for x in stdin.readline().rstrip().split()]
P = []
C = []
for _ in range(D):
    p, c = [int(x) for x in stdin.readline().rstrip().split()]
    P.append(p)
    C.append(c)
ans = 10**9

for i in range(1 << D):
    score = 0
    cnt = 0

    # 全部解く
    for j in range(D):
        if i >> j & 1:
            score += C[j]
            score += P[j]*(j+1)*100
            cnt += P[j]

    # 一部解く(全て解く場合もある)
    for k in range(D-1, -1, -1):
        if i >> k & 1:
            continue
        if score >= G:
            break
        S = (k+1)*100
        for l in range(P[k]+1):
            score += S
            cnt += 1
            if score >= G:
                break
    ans = min(ans, cnt)
print(ans)