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())
plist = [list(map(int,input().split())) for i in range(d)]

basiclist = []

problem = [i for i in range(d)]

# print(problem)

for i in range(len(plist)):
    tmplist = [plist[i][0], (plist[i][0])*(i+1)*100+plist[i][1]]
    # problem.append(plist[i][0])
    basiclist.append(tmplist)

# print(basiclist)

import itertools

combs = []

for i in range(1, len(problem)+1):
    els = [list(x) for x in itertools.combinations(problem, i)]
    # print(els)
    combs.extend(els)

# print(combs)

mincount = 2**10+1


for i in range (d):
    for j in range (1, basiclist[i][0]):
        if j*(i+1)*100 >= g:
            mincount = min(mincount, j)


for comb in combs:
    best_remaining_num = -1
    for a in range(d):
        if a not in comb:
            best_remaining_num = max(a, best_remaining_num)
    best_remaining_score = (best_remaining_num+1)*100
    # print(best_remaining_score)
    total_ps = 0
    total_ps_count = 0
    for com in comb:
        total_ps += basiclist[com][1]
        total_ps_count += basiclist[com][0]
    # print(total_ps)
    if best_remaining_num == -1:
        mincount = min(mincount, total_ps_count)
        continue
    for i in range(basiclist[best_remaining_num][0]):
        if total_ps + best_remaining_score*i >= g:
            # print(comb, total_ps_count, total_ps, best_remaining_score, i, total_ps + best_remaining_score * i)
            mincount = min(mincount, i + total_ps_count)
            # print(mincount)
            break

print(mincount)

Submission status: Accepted

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

ans = sum(pc[:][0])
for i in range(2 ** D):
    temp = 0
    numberProb = 0
    box = ["-"] * D
    for j in range(D):
        if ((i >> j) & 1):
            box[D - j - 1] = "+"
    for k, l in enumerate(box):
        if l == "+":
            temp += pc[k][2]
            numberProb += pc[k][0]

    if temp >= G:
        ans = min(ans, numberProb)
    else:
        lisind = max( [i for i, x in enumerate(box) if x == '-'])
        for m in range(pc[lisind][0]):
            temp += (lisind + 1) * 100
            numberProb += 1
            if temp >= G:
                ans = min(ans, numberProb)
                break

print(ans)

Submission status: Accepted

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

num_min = 1000
for bit in range(1 << d):
    sum = 0
    num = 0
    for i in range(d):
        if bit & (1 << i):
            sum += 100 * (i + 1) * problem[i][0] + problem[i][1]
            num += problem[i][0]
    if sum >= g:
        num_min = min(num_min, num)
    else:
        for j in range(d - 1, -1, -1):
            if bit & (1 << j):
                continue
            for k in range(problem[j][0]):
                if sum >= g:
                    break
                sum += 100 * (j + 1)
                num += 1
        if sum >= g:
            num_min = min(num_min, num)

print(num_min)

Submission status: Accepted

Solution code:
N = input().split()
N = [int(i) for i in N]
pi = [0 for i in range(N[0])]
ci = [0 for i in range(N[0])]
for i in range(N[0]):
    buf = input().split()
    pi[i] = int(buf[0])
    ci[i] = int(buf[1])

num_min = 10*100
G_new = N[1]

flag= [0 for i in range(N[0])]
for i in range(0, pow(2, N[0])):
    G_new = N[1]
    count = 0
    #print(bin(i))
    for j in range(N[0]):
        flag[j] = (i>>j & 1)
        if(flag[j]==1):
            G_new -= ci[j]
            G_new -= 100*(j+1)*pi[j]
            count += pi[j]
    #print(flag)

    if(G_new<=0):
        #print(i, flag)
        if(count < num_min):
            #print(count)
            num_min = count
            #print(count)
    else:
        for j in range(N[0]):
            if((flag[N[0]-1-j])==0):
                #print(i, flag, N[0]-1-j, G_new, pi[N[0]-1-j], count, -(-G_new//(100*(N[0]-j)))   )
                if(G_new - 100*(N[0]-j)*pi[N[0]-1-j] < 0):
                    count += -(-G_new//(100*(N[0]-j)))
                    if(count < num_min):
                       # print(count)
                        num_min = count
                        break

    
print(num_min)

Submission status: Accepted

Solution code:
N = input().split()
N = [int(i) for i in N]
pi = [0 for i in range(N[0])]
ci = [0 for i in range(N[0])]
for i in range(N[0]):
    buf = input().split()
    pi[i] = int(buf[0])
    ci[i] = int(buf[1])

num_min = 10*100
G_new = N[1]

flag= [0 for i in range(N[0])]
for i in range(0, pow(2, N[0])):
    G_new = N[1]
    count = 0
    #print(bin(i))
    for j in range(N[0]):
        flag[j] = (i>>j & 1)
        if(flag[j]==1):
            G_new -= ci[j]
            G_new -= 100*(j+1)*pi[j]
            count += pi[j]
    #print(flag)

    if(G_new<=0):
        if(count < num_min):
            num_min = count
            #print(count)

    else:
        for j in range(N[0]):
            if((flag[N[0]-1-j])==0):
                if(G_new - 100*(N[0]-j)*pi[N[0]-1-j] <= 0):
                    count += -(-G_new//(100*(N[0]-j)))
                    if(count < num_min):
                        num_min = count
                break

    
print(num_min)

Submission status: Accepted

Solution code:
N = input().split()
N = [int(i) for i in N]
pi = [0 for i in range(N[0])]
ci = [0 for i in range(N[0])]
for i in range(N[0]):
    buf = input().split()
    pi[i] = int(buf[0])
    ci[i] = int(buf[1])

num_min = 10*100
G_new = N[1]

flag= [0 for i in range(N[0])]
for i in range(0, pow(2, N[0])):
    G_new = N[1]
    count = 0
    #print(bin(i))
    for j in range(N[0]):
        flag[j] = (i>>j & 1)
        if(flag[j]==1):
            G_new -= ci[j]
            G_new -= 100*(j+1)*pi[j]
            count += pi[j]
    #print(flag)

    if(G_new<=0):
        #print(i, flag)
        if(count < num_min):
            #print(count)
            num_min = count
            #print(count)
    else:
        for j in range(N[0]):
            if((flag[N[0]-1-j])==0):
                #print(i, flag, N[0]-1-j, G_new, pi[N[0]-1-j], count, -(-G_new//(100*(N[0]-j)))   )
                if(G_new - 100*(N[0]-j)*pi[N[0]-1-j] < 0):
                    count += -(-G_new//(100*(N[0]-j)))
                    if(count < num_min):
                       # print(count)
                        num_min = count
                break

    
print(num_min)

Submission status: Accepted

Solution code:
from itertools import combinations
D, G = map(int, input().split())
G = G // 100
ns = [0] * (D + 1)
cs = [0] * (D + 1)
for i in range(1, D + 1):
    n, c = map(int, input().split())
    ns[i] = n
    cs[i] = c // 100

ans = sum(ns)
for partialsn in range(1, D + 1):
    for partials in combinations(range(1, D + 1), partialsn):
        sumn = 0
        rp = G
        for i in range(1, D + 1):
            if not i in partials:
                sumn += ns[i]
                rp -= i * ns[i] + cs[i]
        if rp > 0:
            for i in sorted(partials, reverse=True):
                n = ns[i] - 1
                if rp <= i * n:
                    n = rp // i
                    if rp % i != 0:
                        n += 1
                sumn += n
                rp -= i * n
                if rp <= 0:
                    break
        if rp <= 0:
            if sumn < ans:
                ans = sumn
print(ans)

Submission status: Accepted

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

ans = float("inf")
# 各難易度ごとに、全部解くor解かないで場合わけ
for bit in range(1 << D):
    score = 0
    count = 0
    rest = set(pc.keys())
    for i in range(D):
        if (bit >> i) & 1:
            n_problem, complete_score = pc[i]
            score += n_problem * (i + 1) * 100 + complete_score
            count += n_problem
            rest.discard(i)
    lack = G - score
    if lack <= 0:
        ans = min(ans, count)
        continue
    use = max(rest)
    n_problem = pc[use][0]
    extra_count = -(-lack // ((use+1) * 100))
    if extra_count >= n_problem:
        continue
    else:
        count += extra_count
    ans = min(ans, count)
print(ans)

Submission status: Accepted

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

for i in range(1 << D):
	point = 0
	count = 0
	for j in range(D):
		if (i>>j)&1:
			point += 100*(j+1)*X[j][0]+X[j][1]
			count += X[j][0]
	if 	G > point:
		for k in range(D)[::-1]:
			if (i>>k)&1==0:
				if (G-point) <= 100*(k+1)*(X[k][0]-1):
					count += -((-(G-point)) // (100*(k+1)))
					break
				else:
					count = 10**5
					break
	if ans == 0 or count < ans:
		ans = count

print(ans)

Submission status: Accepted

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

for i in range(D):
    L[i][0],L[i][1]=map(int, input().split())
MAP=[0]*(D+1)
C=[[0,0] for i in range(D)]
for i in range(D):
    C[i][1]=(i+1)
    C[i][0]=L[i][0]*(i+1)*100
C=sorted(C,reverse=True)

a=10**10
while(MAP[-1]==0):
    for j in range(D):
        if MAP[j] > 1:
            MAP[j] -= 2
            MAP[j+1]+=1 
    s=0
    c=0
    for j in range(D):   
        if(MAP[j]!=0):
            s+=L[j][0]*(j+1)*100
            s+=L[j][1]
            c+=L[j][0]
    if(c<a):
        if(s<G):
            for i in range(D):
                if(MAP[C[i][1]-1]==0):
                    t=G-s
                    if(C[i][0]>t):
                        c+=math.ceil(t/(C[i][1]*100))
                        s+=C[i][1]*100*math.ceil(t/(C[i][1]*100))
                    break
        if(s>=G):
            a=min(a,c)
            #print(a,MAP)
    MAP[0]+=1
print(a)

Submission status: Accepted

Solution code:
import functools
D, G = map(int, input().split())
G = G // 100
sumn = 0
ns = [0] * (D + 1)
cs = [0] * (D + 1)
for i in range(1, D + 1):
    n, c = map(int, input().split())
    ns[i] = n
    cs[i] = c // 100
    sumn += n

minn = [0] * (D + 1)
for i in range(1, D + 1):
    minn[i] = min(ns[1:i+1])

@functools.lru_cache(maxsize=None)
def f(i, rn):
    if i == 1:
        if ns[1] < rn:
            return -1
        p = rn
        if ns[1] == rn:
            p += cs[1]
        return p
    if rn < minn[i]:
        p = 0
        for j in range(i, 0, -1):
            n = min((ns[j], rn))
            p += j * n
            if n == rn:
                break
            rn -= n
        return p
    maxp = 0
    for n in range(min((ns[i], rn)) + 1):
        p = i * n
        if n == ns[i]:
            p += cs[i]
        np = f(i - 1, rn - n)
        if np >= 0:
            p += np
            if maxp < p:
                maxp = p
    return maxp

mn = 1
mx = sumn
while mn < mx:
    x = mn + ((mx - mn) // 2)
    if G <= f(D, x):
        mx = x
    else:
        mn = x + 1
print(mn)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
l=[list(map(int,input().split())) for i in range(d)]
ans=float('inf')
for i in range(2**d):
  a=[]
  b=[]
  s=0
  sg=g
  for j in range(d):
    if (i>>j)&1:
      a.append(j)
    else:
      b.append(j)
  if a:
    for k in a:
      sg-=100*(k+1)*l[k][0]+l[k][1]
      s+=l[k][0]
  if sg>0:
    if b:
      for m in range(1,l[b[-1]][0]):
        sg-=100*(b[-1]+1)
        s+=1
        if sg<=0:
          ans=min(ans,s)
          break
  else:
    ans=min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
import math
length, goal = map(int, input().split(" "))
nums = []
sumall = []
for i in range(length):
    a, b = map(int, input().split(" "))
    nums.append(a)
    sumall.append(a * (i + 1) * 100 + b)
answer = float("inf")
for bit in range(2 ** length):
    temp = []
    for i in range(length - 1, -1, -1):
        if bit & (1 << i):
            temp.append(i)
    temp_length = len(temp)
    for tempbit in range(2 ** temp_length):
        temp_sum = 0
        choosed = 0
        for i in range(temp_length):
            if tempbit & (1 << i):
                temp_sum += sumall[temp[i]]
                choosed += nums[temp[i]]
                if temp_sum >= goal:
                    answer = min(answer, choosed)
                    break
            else:
                if temp_sum + (nums[temp[i]] - 1) * (temp[i] + 1) * 100 >= goal:
                    answer = min(answer, choosed + int(math.ceil((goal - temp_sum) / (100 * (temp[i] + 1)))) )
                    break
                temp_sum += (nums[temp[i]] - 1) * (temp[i] + 1) * 100
                choosed += nums[temp[i]] - 1
        # print(bin(bit), bin(tempbit), temp_sum, choosed, answer)
    # print(answer, bin(bit))
print(answer)

Submission status: Accepted

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

P = []
for i in range(2 ** D):
    b = format(i, 'b').zfill(D)
    P.append(b)

def get_high_score_q(p):
    if p.count('0') == 0:
        return None
    else:
        pos = []
        for i, pi in enumerate(p):
            if pi == '0':
                pos.append(i)
        return pos[-1]

ans = 10 ** 10
# P: ['00', '01', '10', '11']
for pi in P:
    # print('pi', pi)
    scores = 0
    probs = 0
    for i, b in enumerate(pi):
        if b == '0':
            pass
        elif b == '1':
            pc = PC[i]
            scores += pc[0] * pc[2] + pc[1]
            probs += pc[0]
        else:
            raise Exception()

    # print(scores, probs)
    if scores < G:
        q = get_high_score_q(pi)
        pc = PC[q]
        for i in range(pc[0]):
            scores += pc[2]
            probs += 1
            if scores >= G:
                break
    # print(scores, probs)
    if scores >= G:
        ans = min(ans, probs)

print(ans)

Submission status: Accepted

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

ans = g // 100

for i in range(2 ** d):
    total = 0
    correct = 0
    for j in range(d):
        if (i >> j) & 1:
            correct += S[j][0] 
            total += S[j][0] * (j+1) * 100 + S[j][1]
        else:
            biggest = j

    if total >= g:
        ans = min(correct,ans)
    elif total + (S[biggest][0] - 1) * (biggest+1) * 100 < g:
        continue
    else:
        while total < g:
            total += (biggest+1) * 100
            correct += 1
        ans = min(correct,ans)

print(ans)

Submission status: Accepted

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))





D,G=acinput()


s=[]
for i in range(D):
    s.append(acinput())

#s=s.reverse()

res=10**9
for i in range(2**D):
    d = list(map(int,list(bin(i)[2:].zfill(D))))
    #print(d)
    resid=False
    nquestions=0
    sm=0
    for k in range(D):                
        if d[k]==1:
            sm+=s[k][0]*(100*(k+1))+s[k][1]
            nquestions+=s[k][0]
        else:
            resid=k+1

    needs=0
    if G>sm:
        needs=np.ceil((G-sm)/(100*resid))
        if needs>=s[resid-1][0]:
            continue

    res=min(res,nquestions+needs)
    #print(res)



print(int(res))

Submission status: Accepted

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

ans = sum(p)
for bit in range(1<<d):
  t = -1
  cur = 0
  ret = 0
  for i in range(d):
    if bit & (1<<i):
      cur += p[i]*(i+1) + c[i]
      ret += p[i]
    else:
      t = i
  if cur >= g:
    if ans > ret:
      ans = ret
  else:
    h = (g-cur-1)//(t+1) + 1
    if h <= p[t]:
      ret += h
      if ret < ans:
        ans = ret
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]

class Util():
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Util.round_up(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x

D,G = cin.mapInt()
P = cin.intListList(D)

ans = int(1e09)
for i in range(1 << D):
    point = 0
    cnt = 0
    for j in range(D):
        if i >> j & 1:
            cnt += P[j][0]
            point += P[j][0] * (j + 1) * 100 + P[j][1]
    if point >= G:
        ans = min(ans,cnt)
        continue
    for j in reversed(range(D)):
        if not i >> j & 1:
            p = (j + 1) * 100
            c = min(P[j][0],Util.roundUp(G - point,p))
            cnt += c
            point += c * p
            if point >= G:
               break
    ans = min(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

d,g = inm()
p = []
c = []
for i in range(d):
    pp,cc = inm()
    c.append(cc)
    p.append(pp)

mn = BIG
for i in range(2**d):
    s = [0]*d
    for j in range(d):
        s[j] = (i>>j)%2  ## set bit info
    ddprint("i {} s {}".format(i,s))
    np = 0
    sc = 0
    for j in range(d):
        if s[j]==1:
            sc += 100*(j+1)*p[j] + c[j]
            np += p[j]
    ddprint("full sc {} np {}".format(sc,np))
    if sc<g:
      for j in range(d-1,-1,-1): # only 1st non-full j enuf
        if s[j]==1:
            continue
        for k in range(p[j]-1):
            np += 1
            sc += 100*(j+1)
            if sc >= g:
                break
        break
    ddprint("all sc {} np {}".format(sc,np))
    if sc>=g and np<mn:
        mn = np
print(mn)

Submission status: Accepted

Solution code:


D, G = map(int, input().split())
from itertools import chain

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

L = []
for i in range(2**D):
  T = []
  for j in range(D):
    if (i>>j) & 1:
      T.append(j)
  L.append(T)

X = []
for l in L:
  score, count = 0, 0
  for m in l:
    p, c = S[m]
    score += c + (m+1) * 100 * p
    count += p
  else:
    X.append((score,count,l))

ans = float("inf")
for l in X:
  score, count, indexes = l

  if score >= G:
    ans = min(ans, count)
    continue
  
  end = False
  for i in list(range(D))[::-1]:
    if i in indexes:
      continue

    if end:
      break
    
    p, c = S[i]
    for _ in range(p):
      count += 1
      score += (i+1) * 100
      if score >= G:
        ans = min(ans, count)
        end = True
        break

print(ans)

Submission status: Accepted

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

p = [0]
c = [0]

for i in range(D):
    pi, ci = [int(x) for x in input().split(" ")]
    p.append(pi)
    c.append(ci)

a = list()
for i in range(2**D):
    m = 0
    s = 0
    solves = 0
    for j in range(D):
        if i & (1<<j):
            s += 100 * (j+1) * p[j+1] + c[j+1]
            solves += p[j+1]
        else:
            if m < j+1:
                m = j+1

    if s < G:
        for j in range(1, p[m]):
            s += 100 * m
            solves += 1
            if s >= G:
                break

    if s >= G:
        a.append(solves)

print(min(a))

Submission status: Accepted

Solution code:
dp = [[0 for n in range(1001)] for m in range(11)]
length, goal = map(int, input().split(" "))
problems = []
for l in range(length):
    a, b = map(int, input().split(" "))
    problems.append([a, b])

for i in range(length):
    max_problems = problems[i][0]
            
    for k in range(1000):
        if dp[i][k]:
            for l in range(max_problems):
                dp[i + 1][k + 1 + l] = max(dp[i + 1][k + 1 + l], dp[i][k] + (i + 1) * 100 * (l + 1) + (problems[i][1] * int(l + 1 == max_problems)) )
                dp[i + 1][k] = max(dp[i + 1][k], dp[i][k])
    for l in range(max_problems):
        dp[i + 1][1 + l] = max(dp[i + 1][1 + l], (i + 1) * 100 * (l + 1) + (problems[i][1] * int(l + 1 == max_problems)) )
        # print(dp[i + 1][1])
answer = float("inf")
for i in range(11):
    for j in range(1001):
        if dp[i][j] >= goal:
            answer = min(answer, j)
print(answer)

Submission status: Accepted

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

def dfs(i, sum, count, nokori):
   global ans
   if (i == d):
      if (sum < g):
         use = max(nokori)
         n = min(pc[use-1][0], -(-(g-sum) // (use*100)))
         count += n
         sum += n * use * 100

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

   else:
      dfs(i+1, sum, count, nokori)
      dfs(i+1, sum+pc[i][0]*(i+1)*100+pc[i][1], count+pc[i][0], nokori-{i+1})


ans = float('inf')
dfs(0, 0, 0, set(range(1, d+1)))
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

P_list = list(range(D))
cnt = float('inf')

for i in range(D):
	for bonus in itertools.combinations(P_list, i):

		tmp_cnt = 0
		score = 0

		for j in bonus:
			score += PC[j][0] * 100 * (j+1) + PC[j][1]
			tmp_cnt += PC[j][0]

		res_max_p = max([k for k in range(D) if k not in bonus])
		res_score = G - score
		if res_score > 0:
			t = (-res_score//((res_max_p+1)*100)) * (-1) 
			if t < PC[res_max_p][0]:
				tmp_cnt += t
			else:
				continue

		cnt = min(cnt, tmp_cnt)

if cnt == float('inf'):
	cnt = sum([PC[j][0] for j in range(D)])

print(cnt)

Submission status: Accepted

Solution code:
D, G = [int(i) for i in input().split()]
G //= 100
p = []
c = []
ans = float("inf")
for _ in range(D):
    a, b = [int(i) for i in input().split()]
    p.append(a)
    c.append(b//100)
for i in range(2**D):
    g = G
    count = 0
    B = bin(i)[2:].zfill(D)
    for j, b in enumerate(B):
        if b == "1":
            g -= c[j]+p[j]*(j+1)
            count += p[j]
    i0 = B.rfind("0")
    if i0 >= 0:
        for _ in range(p[i0]):
            if g <= 0:
                break
            g -= i0+1
            count += 1
    if g <= 0:
        ans = min(count, ans)
print(ans)

Submission status: Accepted

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

N = 1<<D
cnts = []
for one in range(N):
    s = 0
    flag=False
    cnt = 0
    for i in range(D):
        if (one>>i &1)==1:
            s+=p_c[i][0]*(i+1)*100+p_c[i][1]
            cnt+=p_c[i][0]
    if G<=s:
        flag=True
    else:
        for i in range(D-1, -1, -1):
            if (one>>i&1)==0:
                if G-s<=p_c[i][0]*100*(i+1):
                    cnt+=(G-s)//(100*(i+1))
                    if (G-s)%(100*(i+1))!=0:
                        cnt+=1
                    flag=True
                    break
    if flag:
        cnts.append(cnt)
print(min(cnts))

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
P=[]
C=[]
for i in range(d):
    x,y=map(int,input().split())
    P.append(x)
    C.append(y)
v=sum(P)
for i in range(1<<d):
	t=0
	c=0
	L=[i for i in range(d)]
	for j in range(d):
		if i&(2**j):
			L.remove(j)
			t+=(j+1)*100*P[j]+C[j]
			c+=P[j]
	if t>=g:
		v=min(v,c)
	else:
		if L:
			s=max(L)
			for k in range(P[s]-1):
				t+=100*(s+1)
				c+=1
				if g<=t:
					v=min(v,c)
					break
print(v)

Submission status: Accepted

Solution code:
import math
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())

min_cost = 10**9
for i in range(2**d):
    count = 0
    score = 0
    use_list = []
    for bit in range(d):
        if i & 2 ** bit > 0:
            use_list.append(bit + 1)
            count += p[bit]
            score += (bit + 1) * 100 * p[bit] + c[bit]
    if score < g:
        p_i = max(set(range(1, d+1)) - set(use_list))
        p_count = math.ceil((g - score) / (p_i * 100))
        if p_count <= p[p_i - 1]:
            count += p_count
            score += p_count * (p_i * 100)
    if score >= g:
        min_cost = min(min_cost, count)
print(min_cost)

Submission status: Accepted

Solution code:
import itertools,math

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

ans = 1000  # 制約上の最大値
for t in itertools.product([0, 1], repeat=D):
    score = sum(t[i] * (Q[i][0] * 100 * (i + 1) + Q[i][1]) for i in range(D))
    ans_tmp = sum(t[i] * Q[i][0] for i in range(D))
    if score < G:
        p = D - 1
        while t[p]:
            p -= 1
        addition_q = math.ceil((G - score) / (100 * (p + 1)))
        if addition_q >= Q[p][0]:
            continue
        ans_tmp += addition_q
    ans = min(ans, ans_tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil

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

ans = 10 ** 10
for e in product((0, 1), repeat=d):
    total_cnt = 0
    score = 0
    odd_idx = 0
    for j in range(d):
        if e[j] == 1:
            cnt = pc[j][0]
            bonus = pc[j][1]
            score += cnt * ((j + 1) * 100) + bonus
            total_cnt += cnt
        else:
            odd_idx = j

    if g <= score:
        ans = min(ans, total_cnt)
    else:
        odd_point = (odd_idx + 1) * 100
        odd_cnt = pc[odd_idx][0] - 1
        if g <= score + (odd_cnt * odd_point):
            total_cnt += ceil((g - score) / odd_point)
            ans = min(ans, total_cnt)
print(ans)

Submission status: Accepted

Solution code:
def dfs(problems: "scores", now_depth: int, g: int) -> int:
  if now_depth == 0:
    return 10 ** 9 # 十分に大きい値
  
  # ある得点帯iにおいて,gを達成するのに必要な問題数を考える
  # g // (100 * idx) は, コンプリートボーナスを考えない場合の問題数
  # これを min() でコンプリートボーナス達成に必要な問題数と比べる.
  solve_count = min(g // (100 * now_depth), problems[now_depth][0]) # // は余り切り捨て
  score = 100 * now_depth * solve_count

  # コンプリートボーナス(に必要な問題数)を選んだときは更に加算
  if solve_count == problems[now_depth][0]:
    score += problems[now_depth][1]
  
  if score < g:
    solve_count += dfs(problems, now_depth - 1, g - score)
  
  return min(solve_count, dfs(problems, now_depth - 1, g))

depth, g = [ int(x) for x in input().split() ]
# [0] は問題番号と入力の帳尻を合わせる為につけているもの.使用しない.
problems = [0] + [ [ int (x) for x in input().split() ] for _ in range(depth) ]
print(dfs(problems, depth, g))

Submission status: Accepted

Solution code:
D,G = map(int,input().split()) #Gは達成すべきスコア。Dは100D点問題まであるって事を示す。
L = []
minimum = 0 #解くべき最低問題数
candidate = 0 #あるループで解いた問題数
score = 0
for _ in range(D):
    p,c = map(int,input().split())
    L.append([p,c]) #k個目の問題はpk個あって、全部正解するとc点もらえる。
#2 700
#3 500
#5 800の場合：[[3, 500], [5, 800]]を得る。
#方針：全部ACの線で問題探して行って、それでダメならgreedyに全完してないやつから難易度順にACして行く。
#まず全完難易度帯を2^D通り決め打ちする。
for i in range(2**D):
    for j in range(len(L)): #list L に対応したフラグ立ってるか見る。
        if ((i>>j)& 1): #立っていれば：
            score += L[j][0] * (j+1) * 100 + L[j][1] #全完した
            candidate += L[j][0]
    if score >= G:#目標達成
        if minimum == 0:
            minimum = candidate #minimum初期化
            candidate = 0 #candidateリセット
            score = 0
        elif candidate != 0 and candidate < minimum:
            minimum = candidate #minimum更新
            candidate = 0 #リセット
            score = 0
    else: #失敗
        for j in range(len(L)-1,-1,-1):
            if ((i>>j) & 1):#立っていれば：
                continue #次の処理はしないでください。
            for k in range(L[j][0]):#全完されてない難易度を見つけた。L[j][0] = k問でリサーチ。
                score += 100*(j+1) #j問目正解
                candidate += 1
                if score >= G:
                    if minimum == 0:
                        minimum = candidate #minimum初期化
                        candidate = 0 #candidateリセット
                        score = 0
                    elif candidate != 0 and candidate < minimum:
                        minimum = candidate #minimum更新
                        candidate = 0 #リセット
                        score = 0
    candidate = 0 #リセット
    score = 0
print(minimum)