Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

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

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

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

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

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

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

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

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

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

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

Sample Input 4

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

Sample Output 4

66

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



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
pc = [0]*d
for i in range(d):
    pc[i] = list(map(int,input().split()))
ans_new = float("inf")
for i in range(1<<d):
    num = 0
    ans = 0
    for j in range(d):
        if (i >> j)%2 == 1:
           num += pc[j][0]*(j+1)*100 + pc[j][1]
           ans += pc[j][0]
    if num < g:
        dum = 0
        for k in range(d):
            if (i >> k)%2 == 0:
               dum = k
        for l in range(pc[dum][0]):
            num += (dum+1)*100
            ans += 1
            if num >= g:
                break
        else:
            continue
    ans_new = min(ans,ans_new)
print(ans_new)

Submission status: Accepted

Solution code:
def solve():
    D, G = map(int, input().split())
    p = [0 for _ in range(D)]
    c = [0 for _ in range(D)]

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

    ans = 1000
    for i in range(2 ** D):
        comp = [0 for _ in range(D)]
        num = 0
        score = 0
        for j in range(D):
            if i >> j & 1:
                comp[j] = 1
                # print('j',j)
                score += 100 * (j + 1) * p[j] + c[j]

        for j in range(D):
            if comp[j] == 1:
                num += p[j]
        if score < G:
            index = 0
            for j in range(D - 1, 0, -1):
                if comp[j] == 0:
                    index = j
                    break
            for _ in range(p[index]):
                score += 100 * (index + 1)
                num += 1
                if score >= G:
                    break
            if score < G:
                continue
        # print('i', i)
        # print('num',num)
        # print('score',score)
        ans = min(ans, num)
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

for bit in range(2 ** D):
    score, solution_count, rest_max = 0, 0, 0
    for i in range(D):
        if bit & (1 << i):
            score += 100 * (i + 1) * p[i] + c[i]
            solution_count += p[i]
        else:
            rest_max = i + 1

    if score < G and rest_max:
        if (G - score) % (100 * rest_max) == 0:
            need_count = (G - score) // (100 * rest_max)
        else:
            need_count = (G - score) // (100 * rest_max) + 1
        if need_count > p[rest_max - 1]:
            continue
        else:
            score += 100 * rest_max * need_count
            solution_count += need_count

    if score >= G:
        answer = min(answer, solution_count)
print(answer)

Submission status: Accepted

Solution code:
from copy import deepcopy
from math import ceil
d,g=map(int,input().split())
lst=[]
for i in range(1,d+1):
    p,c=map(int,input().split())
    lst.append([i*100,p,c])
ans=1145141919
for p in range(d):
    tmp=deepcopy(lst)
    tmp=tmp[:p]+tmp[p+1:]
    for i in range(2**(d-1)):
        point=0
        problem=0
        for j in range(d-1):
            if (i>>j)&1:
                point+=tmp[j][0]*tmp[j][1]+tmp[j][2]
                problem+=tmp[j][1]
        if point<g:
            extra=g-point
            if extra>lst[p][0]*lst[p][1]+lst[p][2]:
                continue
            if extra>lst[p][0]*lst[p][1]:
                ans=min(ans,problem+lst[p][1])
                continue
            problem+=ceil(extra/lst[p][0])
        ans=min(ans,problem)

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
probs = [tuple(map(int, input().split())) for _ in range(D)]
res = 10 ** 4
for i in range(1 << D):
    comps = []
    idx = -1
    for j in range(D):
        if (i >> j) & 1:
            comps.append(j)
        else:
            idx = j
    g = G
    tmp = 0
    for c in comps:
        g -= 100 * (c + 1) * probs[c][0] + probs[c][1]
        tmp += probs[c][0]
    if g <= 0:
        res = min(res, tmp)
        continue
    else:
        t = (g + 100 * (idx + 1) - 1) // (100 * (idx + 1))
        if t <= probs[idx][0]:
            tmp += t
            res = min(res, tmp)
print(res)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

d,g=MI()
lis=[LI() for i in range(d)]
pr=[]
for x in product([0,1],repeat=d):
    #print(x)
    score=0
    pro=0
    for i in range(d):
        if x[i]==1:
            score+=100*(i+1)*lis[i][0]+lis[i][1]
            pro+=lis[i][0]
    if score>=g:
        pr.append(pro)
    else:
        rest=g-score
        #print(rest)
        for i in range(d):
            j=d-i-1
            if x[j]==0:
                pro+=min(ceil(rest/(100*(j+1))),lis[j][0]-1)
                rest-=100*(j+1)*min(ceil(rest/(100*(j+1))),lis[j][0]-1)
            if rest<=0:
                pr.append(pro)
                break
        else:
            continue
        
print(min(pr))
#print(pr)

Submission status: Accepted

Solution code:
# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import math
import sys
input = sys.stdin.readline

D, G = map(int, input().split())
# print(D, G)
P = []
C = []
for i in range(D):
    p,  c = map(int, input().split())
    P.append(p)
    C.append(c)

INF = 10**15


def F(i, n, GetPoint):
    if i == D:
        if GetPoint >= G:
            return n, GetPoint
        else:
            return INF, INF

    PerPoint = (i+1)*100

    if GetPoint < G:
        ANS = INF, INF
        # ALL
        N, GP = F(i+1, n+P[i], GetPoint+PerPoint*P[i] + C[i])
        if N < ANS[0]:
            ANS = N, GP
        # through
        N, GP = F(i+1, n, GetPoint)
        if N < ANS[0]:
            ANS = N, GP

        # part
        # 上位合計
        PupperAll = sum([(j+1)*100*P[j] + C[j] for j in range(i+1, D)])
        rN = math.ceil((G - GetPoint - PupperAll)/PerPoint)
        if 0 < rN < P[i]:
            GP = GetPoint + PerPoint*rN + PupperAll
            N = n + rN + sum(P[i+1:])
            if N < ANS[0]:
                ANS = N, GP

        return ANS
    else:
        return n, GetPoint


print(F(0, 0, 0)[0])

Submission status: Accepted

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

pc = pc[::-1]
#print(pc)
ans = float('inf')
for i in range(2**d):
  total = 0
  cnt = 0
  for j in range(d):
    if (i>>j) & 1:
      total += 100*(d-j)*pc[j][0] + pc[j][1]
      cnt += pc[j][0]
    if total >= g:
      ans = min(ans, cnt)
      continue
  for j in range(d):
    if (i>>j) & 1 == False:
      for k in range(pc[j][0]):
        total += 100*(d-j)
        cnt += 1
        if total >= g:
          ans = min(ans, cnt)
          break
      break
      
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math
 
# import copy
from bisect import bisect_left, bisect_right
# import heapq
 
# sys.setrecursionlimit(1000000)
 
# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
 
def search(pros,tgt,g,d):
    tmp = 0
    cnt = 0
    rest = []
    for i in range(d):
        if tgt % 2 == 1:
            tmp += 100 * (i+1) * pros[i][0] + pros[i][1]
            cnt += pros[i][0]
        else:
            rest.append((i+1,pros[i][0]-1))
        tgt //= 2
    # print(tmp)
    if tmp >= g:
        return cnt
    for ap, ac in rest[::-1]:
        if tmp + 100 * ap * ac >= g:
            cnt += math.ceil((g - tmp)/(100 * ap))
            return cnt
        else:
            cnt += ac
            tmp += 100 * ac * ap

    return INF

def main():
    d,g = getList()
    pros = []
    for i in range(d):
        pros.append(getList())
    ans = INF
    tgt = 2 ** d
    for i in range(tgt):
        tmp = search(pros, i,g, d)
        # print(i, tmp)
        if tmp < ans:
            ans = tmp

    print(ans)
    return


 
if __name__ == "__main__":
    main()

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())
ans_num = float('inf')
for i in range(2 ** d):
    score_li = list(range(1,d+1))
    ans_li = []
    ans_n = 0
    for j in range(d):
        if i >> j & 1:
            ans_li.append(p[j]*score_li[j]*100+c[j])
            score_li[j] = -1
            ans_n += p[j]
    if sum(ans_li) < g:
        s = sum(ans_li)
        score_li.sort(reverse=True)
        for k in score_li:
            for l in range(p[k-1]):
                s += k*100
                ans_n += 1
                if s >= g:
                    ans_num = min(ans_n, ans_num)
    else:
        ans_num = min(ans_n, ans_num)
print(ans_num)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
D, G = map(int, input().split())
solved = [0]*1001
for score in range(100, D*100+1, 100):
    p, c = map(int, input().split())
    q = deque()

    bkp = solved.copy()
    for j, s in enumerate(solved):
        val = s - j*score
        while q and q[-1][1] < val:
            q.pop()
        q.append((j, val))

        k, vmax = q[0]
        solved[j] = max(solved[j], vmax+j*score)
        if k == j-p:
            q.popleft()
        if j-p >= 0:
            solved[j] = max(solved[j], bkp[j-p]+p*score+c)

for i, s in enumerate(solved):
    if s >= G:
        print(i)
        exit()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
d,g = readInts()
P = []
C = []
res = float('inf')
for i in range(d):
    p,c = readInts()
    P.append(p)
    C.append(c)
for bit in range(1 << d):
    SUM = 0
    NUM = 0
    for i in range(d):
        if bit & (1 << i):
            SUM += 100 * (i + 1) * P[i] + C[i]
            NUM += P[i]
    if SUM >= g:
        res = min(res,NUM)
    else:
        for i in range(d-1,-1,-1):
            if bit & (1 << i):
                continue
            else:
                for j in range(P[i]):
                    if SUM >= g:
                        break
                    SUM += 100 * (i+1)
                    NUM += 1
        res = min(res,NUM)
print(res)

Submission status: Accepted

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

PC.reverse()

ans = 10**18
for i in range(2**d):
    temp = 0
    cnt = 0
    flag = True
    for j in range(d):
        if (i >> j) & 1:
            temp += 100*(d-j)*PC[j][0]+PC[j][1]
            cnt += PC[j][0]
    for j in range(d):
        if not ((i >> j) & 1):
            t = 100*(d-j)
            r = g-temp
            if r > 0:
                q = (r+t-1)//t
                if q < PC[j][0]:
                    temp += 100*(d-j)*q
                    cnt += q
                else:
                    flag = False
    if flag and temp >= g:
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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

ans = 9999
for b in range(1<<D):
    sc = pr = 0
    for i,(p,c) in enumerate(PC):
        if b&(1<<i):
            sc += c + (i+1)*100*p
            pr += p
    if sc >= G:
        ans = min(ans, pr)
        continue
    remsc = G - sc
    for i,(p,_) in reversed(list(enumerate(PC))):
        if b&(1<<i): continue
        for j in range(p):
            remsc -= (i+1)*100
            pr += 1
            if remsc <= 0:
                ans = min(ans, pr)
                break
        else:
            continue
        break
    if remsc <= 0:
        ans = min(ans, pr)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = []
for _ in range(d):
    p, c = map(int, input().split())
    pc.append((p, c))
ans = 1000
for i in range(2**d):
    score = 0
    k = 0
    for j in range(d):
        if i>>j&1:
            score += pc[j][0]*100*(j+1) + pc[j][1]
            k += pc[j][0]
    if score>=g:
        ans = min(ans, k)
        continue
    for j in range(d-1, -1, -1):
        if i>>j&1:
            continue
        if score+(pc[j][0]-1)*100*(j+1)<g:
            score += (pc[j][0]-1)*100*(j+1)
            k += pc[j][0]-1
            continue
        k += (g-score+100*(j+1)-1)//(100*(j+1))
        ans = min(ans, k)
        break
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p = []
c = []
for _ in range(D):
    p_i, c_i = map(int, input().split())
    p.append(p_i)
    c.append(c_i)
answer = 10000000

for bit in range(2 ** D):
    s, num, rest_max = 0, 0, 0
    for i in range(D):
        if bit & (1 << i):
            s += 100 * (i + 1) * p[i] + c[i]
            num += p[i]
        else:
            rest_max = i
    if s < G:
        s1 = 100 * (rest_max + 1)
        if (G - s) % s1 == 0:
            need = (G - s) // s1
        else:
            need = (G - s) // s1 + 1
        if need >= p[rest_max]:
            continue
        num += need
    answer = min(answer, num)
print(answer)

Submission status: Accepted

Solution code:
import itertools

D,G = map(int,input().split())
ab = []
for _ in range(D):
    p, c = (int(x) for x in input().split())
    ab.append([p,c])

ans = 10000000

pick_num = []

for i in range(D):
    pick_num.append(i)

for i in range(0,D+1):
    for v in itertools.combinations(pick_num, i):      
        tmp_point = 0
        tmp_count = 0
        for j in v:
            tmp_point += ab[j][0]*(j+1)*100+ab[j][1]
            tmp_count += ab[j][0]
        if tmp_point < G:
            nokori = G-tmp_point
            for k in range(D-1, -1,-1):
                if k not in v:
                    if nokori%(100*(k+1)) == 0:
                        if nokori//(100*(k+1)) < ab[k][0]:
                            tmp_count += nokori//(100*(k+1))
                            tmp_point += nokori
                    else:
                        if nokori//(100*(k+1))+1 < ab[k][0]:
                            tmp_count += nokori//(100*(k+1))+1
                            tmp_point += nokori
                    break
        if G <= tmp_point:
            ans = min(ans, tmp_count)
print(ans)

Submission status: Accepted

Solution code:
#abc104c all green 
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
all_sum = []
for bit in range(1<<d):
    s = 0
    a = 0
    rest = []
    for i in range(d):
        if bit & (1<<i):
            s += pc[i][0]*100*(i+1) + pc[i][1]
            a += pc[i][0]
        else :
            rest.append(i)
    
    if s >= g :
        all_sum.append(a)
    else :
        k = max(rest)
        diff = g - s
        for j in range(pc[k][0]):
            if j*(k+1)*100 >= diff:
                all_sum.append(a+j)
print(min(all_sum))

Submission status: Accepted

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

sum=[]
for i in range(2**(d)):
  s=0
  a=0
  z=[]
  for j in range(d):
    if i >> j & 1:
      s += li[j][0]*100*(j+1) + li[j][1]
      a += li[j][0]
    else:
      z.append(j)

  if s >= g:
    sum.append(a)
  else:
    k = max(z)
    h = g-s
    for l in range(li[k][0]):
      if l*(k+1)*100 >= h:
        sum.append(a+l)
        
print(min(sum))

Submission status: Accepted

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

n = 2 ** d
result = 100 * 10

for i in range(n):
  bin_n = bin(i)[2:]
  bin_n = '0' * (d - len(bin_n)) + bin_n
  max_address = -1
  total = 0
  num_of_question = 0

  for j in range(d):
    if bin_n[j] == '1':
      total += (j+1) * 100 * pc[j][0] + pc[j][1]
      num_of_question += pc[j][0]
    
    else:
      max_address = j
  
  if total >= g:
    result = min(result, num_of_question)
  
  else:
    for _ in range(pc[max_address][0]):
      num_of_question += 1
      total += (max_address+1) * 100
      if total >= g:
        result = min(result, num_of_question)
        break

print(result)

Submission status: Accepted

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

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

min_count = sum([l[1] for l in score_table])
#print(min_count)

for bit in range(1<<D):
    score = 0
    count = 0

    for i in range(D):
        if bit & (1<<i):
            score += score_table[i][0] * score_table[i][1] + score_table[i][2]
            count += score_table[i][1]
    
    if score >= G:
        min_count = min(min_count, count)
    else:
        additional = []
        for j in range(D):
            if not bit & (1<<j):
                additional.append(score_table[j])
        
        additional_ = sorted(additional, key=lambda x:x[0], reverse=True)
        #print(additional_)
        
        # for i in additional_:
        #     if i[1] > 1:
        #         add_score = i
        #         break

        #add_score = additional_[0]

        for k in range(additional_[0][1]-1):
            score += additional_[0][0]
            count += 1
            if score >= G:
                min_count = min(min_count, count)

print(min_count)

Submission status: Accepted

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

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

min_count = sum([l[1] for l in score_table])
#print(min_count)

for bit in range(1<<D):
    score = 0
    count = 0

    for i in range(D):
        if bit & (1<<i):
            score += score_table[i][0] * score_table[i][1] + score_table[i][2]
            count += score_table[i][1]
    
    if score >= G:
        min_count = min(min_count, count)
    else:
        additional = []
        for j in range(D):
            if not bit & (1<<j):
                additional.append(score_table[j])
        
        additional_ = sorted(additional, key=lambda x:x[0], reverse=True)
        #print(additional_)
        
        # for i in additional_:
        #     if i[1] > 1:
        #         add_score = i
        #         break

        add_score = additional_[0]

        for k in range(add_score[1]-1):
            score += add_score[0]
            count += 1
            if score >= G:
                min_count = min(min_count, count)

print(min_count)

Submission status: Accepted

Solution code:
P=[]
C=[]
point=1001    #全問題数
 
D,G=map(int,input().split())
for i in range(D):
    p,c= map(int,input().split())
    P.append(p)
    C.append(c)
 
#とりあえず全部解くor解かないで目標スコアを超えるか超えないかを考える
 
 
for i in range(2**D) :
    score=0
    solve=0
    needproblem=0
    for j in range(D) :                  #全正解した大問をスコアに変換
        if (i>>j) & 1 :
            score+=P[j]*100*(j+1)+C[j]
            solve+=P[j]
        if (~i>>j) & 1 :                  #1問も解かなかった問題の中で最も一題あたりの点が高い問題
            needproblem=j+1
    if score>=G :
        point=min(point,solve)
 
#ぎりぎりスコアが届いていない場合、1問も解かなかった問題の中で最も一題あたりの点が高い問題だけ解いてみる
#中途半端に大問を解ききるのが１種類以下でも目標に届く場合もあるという予想
 
    elif score<G :                
        rest=G-score
        sum=(P[needproblem-1]-1)*needproblem*100
        if rest>sum :            #1問も解かなかった問題の中で最も一題あたりの点が高い問題を解いても届かないのでやり直し
            continue
        elif rest<=sum :
            resolve=solve+(rest//(needproblem*100)+(rest%(needproblem*100)>0))
            point=min(point,resolve)
 
print(point)

Submission status: Accepted

Solution code:
P=[]
C=[]
point=1001    #全問題数
 
D,G=map(int,input().split())
for i in range(D):
    p,c= map(int,input().split())
    P.append(p)
    C.append(c)
 
#とりあえず全部解くor解かないで目標スコアを超えるか超えないかを考える
 
 
for i in range(2**D) :
    score=0
    solve=0
    needproblem=0
    for j in range(D) :                  #全正解した大問をスコアに変換
        if (i>>j) & 1 :
            score+=P[j]*100*(j+1)+C[j]
            solve+=P[j]
    if score>=G :
        point=min(point,solve)
 
#ぎりぎりスコアが届いていない場合、1問も解かなかった問題の中で最も一題あたりの点が高い問題だけ解いてみる
#中途半端に大問を解ききるのが１種類以下でも目標に届く場合もあるという予想
    elif score<G :
        rest=G-score
        for j in range(D) :
            if (~i>>D-j-1) & 1 :
                needproblem=D-j
                sum=needproblem*100*(P[needproblem-1]-1)
                if rest>sum :            #1問も解かなかった問題の中で最も一題あたりの点が高い問題を解いても届かないのでやり直し
                    rest-=sum
                    solve+=P[needproblem-1]-1
                elif rest<=sum :
                    solve+=(rest//(needproblem*100)+(rest%(needproblem*100)>0))
                    rest=0
            if rest<=0 and D*100>solve :
                point=min(point,solve)               
 
print(point)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
# bit全探索で、全問解く問題の組み合わせをすべて試す
 
scores=[None]*D
for i in range(D):
  p,c=map(int,input().split())
  # 一問の得点、問題数、ボーナス、全てといたときの得点
  scores[i]=[(i+1)*100,p,c,((i+1)*100)*p+c]
 
# あとあとのために点数高い順に並べる
scores=sorted(scores,key=lambda x:x[0])[::-1]
 
# 全問とく組み合わせに対して、最小の問題数
ans=D*100
for i in range(2**D):
  total=0
  solve=0
  for j in range(D):
    if (i>>j)&1:
      # 全問とく問題のボーナスを足していく
      total+=scores[j][3]
      solve+=scores[j][1]
  if total>=G:
    if ans>solve:
      ans=solve
    continue
  rest=G-total
  for j in range(D):
    if (i>>j)&1==0:
      point=scores[j][0]
      num=scores[j][1]-1 # 全問とかないので1減らす
      if point*num<rest:
        rest-=point*num
        solve+=num
      else:
        solve+=(rest//point+(rest%point>0))
        rest=0
    if rest<=0 and ans>solve:
      ans=solve
  
print(ans)

Submission status: Accepted

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

res = 1000
for i in range(1 << D):
    b = format(i, '01000b')[::-1]
    s = 0
    cnt = 0
    k = 0
    for j in range(D):
        if b[j] == '1':
            s += 100 * (j + 1) * P[j] + C[j]
            cnt += P[j]
        else:
            k = j
    if s >= G:
        res = min(res, cnt)
    else:
        for l in range(P[k] - 1):
            s += 100 * (k + 1)
            cnt += 1
            if s >= G:
                res = min(res, cnt)
                break
print(res)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(D)]
min_solve_num = 1000
for i in range(1, 2 ** D):
    score = 0
    tmp_solve_num = 0
    for j in range(D):
        if (i >> j) & 1:
            score += pc[j][0] * (j + 1) * 100 + pc[j][1]
            tmp_solve_num += pc[j][0]
    if score >= G and tmp_solve_num < min_solve_num:
        min_solve_num = tmp_solve_num
score = 0
tmp_solve_num = 0
for i in range(D - 1, -1, -1):
    num = pc[i][0]
    for j in range(num):
        score += (i + 1) * 100
        tmp_solve_num += 1
        if j == num - 1:
            score += pc[i][1]
        if score >= G:
            break
    else:
        continue
    break
if tmp_solve_num < min_solve_num:
    min_solve_num = tmp_solve_num
print(min_solve_num)

Submission status: Accepted

Solution code:
import math

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

ans = float('inf')
for i in range(2 ** d):
    sum = 0
    count = 0
    s = set(k for k in range(1, d + 1))
    for j in range(d):
        if (i >> j) & 1 == 1:
            sum += l[j][0] * (j + 1) * 100 + l[j][1]
            count += l[j][0]
            s.discard(j + 1)
    if sum < g:
        t = max(s)
        n = min(l[t - 1][0] - 1, math.ceil((g - sum) / (t * 100)))
        count += n
        sum += n * t * 100
    if sum >= g:
        ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:

def solve():
    d = 0
    c = 0
    for i in range(D):
        d += p[i][0]
    dp = [[0]*(d+1) for i in range(D)]
    for i in range(D):
        for j in range(p[i][0]+1):
            if i == 0:
                if j == p[i][0]:
                    dp[i][j] += p[i][1]
                dp[i][j] += 100*j
            else:
                for k in range(c+1):
                    if j == p[i][0]:
                        dp[i][k+j]=max(dp[i][k+j],dp[i-1][k]+100*j*(i+1)+p[i][1])
                    else:
                        dp[i][k+j]=max(dp[i][k+j],dp[i-1][k]+100*j*(i+1))
        c += p[i][0]
    for i in range(d+1):
        if dp[D-1][i]>=G:
            print(i)
            break    
    
if __name__=="__main__":
    D,G = list(map(int, input().split()))
    p = [list(map(int, input().split())) for _ in range(D)]
    solve()

Submission status: Accepted

Solution code:
import sys
import itertools
from math import ceil

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    D, G = in_nn()
    p = [0] * D
    c = [0] * D
    for i in range(D):
        a, b = in_nn()
        p[i] = a
        c[i] = b

    comb = itertools.product([0, 1], repeat=D)
    ans = 10**9 + 7

    for com in comb:
        score = 0
        prob = 0
        for i, x in enumerate(com):
            if x == 1:
                prob += p[i]
                score += c[i] + p[i] * 100 * (i + 1)

        for i in range(D - 1, -1, -1):
            if score >= G:
                break
            if com[i] == 0:
                pt = ceil((G - score) / (100 * (i + 1)))
                pt = min(pt, p[i] - 1)
                score += pt * 100 * (i + 1)
                prob += pt

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    D, G = in_nn()
    p = [0] * D
    c = [0] * D
    for i in range(D):
        a, b = in_nn()
        p[i] = a
        c[i] = b

    comb = itertools.product([0, 1], repeat=D)
    ans = 10**9 + 7

    for com in comb:
        score = 0
        prob = 0
        for i, x in enumerate(com):
            if x == 1:
                prob += p[i]
                score += c[i] + p[i] * 100 * (i + 1)

        for i in range(D - 1, -1, -1):
            if score >= G:
                break
            if com[i] == 0:
                pt = int((G - score) / (100 * (i + 1)) + 0.9999)
                pt = min(pt, p[i] - 1)
                score += pt * 100 * (i + 1)
                prob += pt

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

    print(ans)


if __name__ == '__main__':
    main()