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

ret = 1000
for i in range(2 ** D):
  s=S[:]
  tot=0
  top=0
  m=0
  am=0
  for j in range(D):
    if (i >> j) & 1:
      s.remove(j)
      tot += iPC[j][0]
      top += iPC[j][1]
  if top<G and len(s)>0:
    m=max(s)
    am=(G-top+((m+1)*100-1))//((m+1)*100)
    if am<iPC[m][0]:
      tot+=am
    else:
      tot=1000
#  print(i,m,am,top,tot)
  ret=min(ret,tot)
print(ret)

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)
ans = 10000
for i in range(1<<d):
    s = cnt = 0
    rest_max = -1
    for j in range(d):
        if (i>>j)&1:
            s += c[j] + 100*(j+1)*p[j]
            cnt += p[j]
        else:
            rest_max = j
    if s < g:
        if g-s > (p[rest_max]-1)*(rest_max+1)*100:
            continue
        else:
            cnt += (g-s-1)//((rest_max+1)*100)+1
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    d,g = map(int,input().split())
    pc = [list(map(int,input().split())) for i in range(d)]
    p = [pc[i][0] for i in range(d)]
    c = [pc[i][1] for i in range(d)]
    ans = 10 ** 9
    def dfs(i,pro):
        if i == 0:
            return 10**9
        cnt = min(pro//(i*100),p[i-1])
        tmp = 100*i*cnt
        if cnt == p[i-1]:
            tmp += c[i-1]
        if tmp < pro:
            cnt += dfs(i-1,pro-tmp)
        return min(cnt,dfs(i-1,pro))
    print(dfs(d,g))
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

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

#得点の大きい順に並び替えておく
l = l[::-1]

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)*l[j][0] + l[j][1]
            cnt += l[j][0]
    if total >= G:
        ans = min(ans,cnt)
        continue
    for j in range(D):
        if (i>>j)&1 == False:
            for k in range(l[j][0]):
                total += 100*(D-j)
                cnt+=1
                if total >= G:
                    ans = min(ans,cnt)
                    break
            else:
                continue
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
D,G=map(int, input().split())
G//=100
p=[list(map(int, input().split())) for i in range(D)]
m=[None]*D
for i in range(D):
    m[i]=p[i][0]*(i+1)+p[i][1]//100
l=[None]*2**D
for i in range(2**D):
    l[i]="{:0>{}b}".format(i,D)
a=1000
for i in l:
    c=0
    t=0
    for j in range(D):
        if i[j]=="1":
            t+=m[j]
            c+=p[j][0]
    if t>G:
        if a>c:
            a=c
        continue
    s=i.rfind("0")
    if t+(s+1)*p[s][0]>G:
        c+=(G-t-1)//(s+1)+1
        if a>c:
            a=c
print(a)

Submission status: Accepted

Solution code:
from math import ceil

D, G = map(int, input().split())
Pd, Cd = [0] * D, [0] * D

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


ans = float("inf")
for i in range(1 << D):
    score, solved, unsolved = 0, 0, 0
    for j in range(D):
        if i & (1 << j):
            score += 100 * (j+1) * Pd[j] + Cd[j]
            solved += Pd[j]
        else:
            unsolved = j

    rest = G - score
    if rest > 0:
        k = 100 * (unsolved+1)
        if k * Pd[unsolved] < rest:
            continue
        solved += ceil(rest/k)

    ans = min(ans, solved)

print(ans)

Submission status: Accepted

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

ans=1000

for b in range(1<<d):
  s=0
  cnt=0
  for i in range(d):
    if b&(1<<i):
      s+=l[i][0]*(i+1)*100+l[i][1]
      cnt+=l[i][0]
  for i in range(d-1,-1,-1):
    if not b&(1<<i):
      for j in range(1,l[i][0]):
        if s<g:
          s+=(i+1)*100
          cnt+=1
  if s>=g:
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

D,G=map(int,input().split())
p,c=[],[]

for _ in range(D):
  pi,ci=map(int,input().split())
  p.append(pi)
  c.append(ci)
  
ans=10**4
  
for cpls in product(range(2),repeat=D):
  num=0#回答数
  tensu=0#各cplsの得点
  for i,v in enumerate(cpls,start=1):
    if v==1:
      tensu+=i*100*p[i-1]+c[i-1]
      num+=p[i-1]
  if tensu>=G:
    ans=min(ans,num)
    continue
  for i,v in reversed(list(enumerate(cpls,start=1))):
    if v==0:
      for _ in range(p[i-1]-1):
        tensu+=100*i
        num+=1
        if tensu>=G:
          ans=min(ans,num)
          break
print(ans)

Submission status: Accepted

Solution code:
import math

D,G = list(map(int,input().split()))
lst = [list(map(int,input().split())) for i in range(D)]
for i in range(10-D):
    lst.append([0,0]) 
lst.insert(0,[])

ans = 1000
for i in range(1024):
    bin_i = format(i,'b').zfill(11)
    tmp = G
    solved = 0
    for j in range(1,11):
        if bin_i[j] == "1":
            tmp -= lst[j][0]*j*100 + lst[j][1]
            solved += lst[j][0]
    if 0 < tmp:
        for j in range(10,0,-1):
            if bin_i[j] == "0" and lst[j][0] != 0:
                if tmp <= (lst[j][0]-1)*j*100:
                    solved += math.ceil(tmp/(j*100))
                    break
        else:
            #この条件ではGを超えない
            continue
        ans = min(ans,solved)
    else:
        ans = min(ans,solved)
print(ans)

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=10e+9

for i in range(2**D):
    sum=0
    q=0
    for j in range(D):
        if(i>>j & 1):
            sum+=(j+1)*100*p[j]+c[j]
            q+=p[j]
        else:
            rest_max=j
    if(sum<G):
        r1=100*(rest_max+1)
        need=-(-(G-sum)//r1)
        if(need>p[rest_max]-1):
            continue
        q+=need
        sum+=need*r1
    
    if(sum>=G):
        ans=min(ans,q)

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

input = sys.stdin.readline


def main():
    D, G = [int(x) for x in input().split()]
    pc = []
    for _ in range(D):
        pc.append([int(x) for x in input().split()])

    ruiseki = []
    for i, v in enumerate(pc):
        ruiseki.append((i + 1) * v[0] * 100 + v[1])

    ans = float("inf")
    for i in itertools.product(range(3), repeat=D):
        tmp = 0
        c = 0
        x = []
        for j, v in enumerate(i):
            if v == 0:
                continue
            elif v == 2:
                tmp += ruiseki[j]
                c += pc[j][0]
            else:
                if pc[j][0] == 1:
                    continue
                x.append(j)

        while tmp < G and x:
            y = x.pop()
            if G - tmp > (pc[y][0] - 1) * (y + 1) * 100:
                tmp += (pc[y][0] - 1) * (y + 1) * 100
                c += pc[y][0] - 1
            else:
                z = -(-(G - tmp) // ((y + 1) * 100))
                c += z
                tmp += z * (y + 1) * 100

        if tmp >= G:
            ans = min(ans, c)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
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())
    
ans=10**7

for ite in itertools.product([0,1], repeat=D):
    temp=0
    tn=0
    for i in range(len(ite)):
        temp+=ite[i]*(c[i]+100*(i+1)*p[i])
        tn+=p[i]*ite[i]
    if temp>=G:
        ans=min(ans,tn)
    else:
        for i in range(len(ite)-1,-1,-1):
            if ite[i]==0:
                if math.ceil((G-temp)/((i+1)*100)) <=p[i]-1 :#その難易度の問題を1問残しで埋めて目標に届くなら:
                    ans=min(ans,tn+math.ceil( (G-temp)/((i+1)*100) ) )
                else:
                    temp+=(i+1)*100*(p[i]-1)
                    tn+=p[i]-1
                    
print(int(ans))

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

D,G = imn()
pc = [iln() for _ in range(D)]

ans = 10**10

for i in range(2**D):
    tmp = i
    point = 0
    count = 0
    complete_set = set()
    for j in range(D):
        if tmp & 1 == 1:
            complete_set.add(j)
            point += pc[j][0] * (100*(j+1)) + pc[j][1]
            count += pc[j][0]
        tmp = tmp >> 1
    for j in range(D-1, -1, -1):
        if j not in complete_set:
            for k in range(pc[j][0]-1):
                if point >= G: break
                point += 100*(j+1)
                count += 1
    if point >= G:
        ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
d,g = map(int,input().split())
lis = [list(map(int,input().split())) for _ in range(d)]
# print(list(itertools.product([0,1], repeat=d))) [(0, 0), (0, 1), (1, 0), (1, 1)]
count_list = []
for flag in itertools.product([0,1], repeat=d):
    tmp = g
    count = 0
    score_list = []
    kosuu_list = []
    for i,f in enumerate(flag):
        if f==1:
            count += lis[i][0]
            #print(lis[i][1],100*(i+1),lis[i][0],tmp)
            tmp -= (lis[i][1]+100*(i+1)*lis[i][0])
        else:
            score_list.insert(0,100*(i+1))
            kosuu_list.insert(0,lis[i][0]-1)
    #print(score_list)
    #print(kosuu_list)
    #print(lis[i][1],100*(i+1),lis[i][0],tmp)
    if tmp <= 0:
        count_list.append(count)
    else:
        for sss,kkk in zip(score_list,kosuu_list):
            if tmp <= 0:
                break
            elif sss*kkk >= tmp:
                count += math.ceil(tmp/sss)
                tmp -= sss*math.ceil(tmp/sss)
                break
            elif sss*kkk < tmp:
                count += kkk
                tmp -= sss*kkk
        if tmp <= 0:
            count_list.append(count)
    #print(flag)
#print(count_list)
print(min(count_list))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
from operator import itemgetter
from math import ceil
def main():
    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):
        done = [False]*D
        tmp = 0
        q = 0
        cnt = i
        point = 0
        while cnt > 0:
            if cnt%2 == 1:
                done[point] = True
                tmp += PC[point][0]*(100*(point + 1)) + PC[point][1]
                q += PC[point][0]
            point += 1
            cnt //= 2
        if tmp < G:
            for j in range(D):
                if not(done[D - j - 1]):
                    score = 100*(D - j)
                    num = min(ceil((G - tmp) / score),PC[D - j - 1][0])
                    tmp += num*score
                    q += num
                    if tmp < G:
                        q = float("inf")
                    break
                
        ans = min(q,ans)
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = []

max_score = [(i+1)*100*List[i][0]+List[i][1] for i in range(n-1, -1, -1)] #全て答えたときのスコアを算出(逆順)
score = [(i+1)*100 for i in range(n-1, -1, -1)] #各レベルの点数を算出しておく(逆順)
howmany = [List[i][0] for i in range(n-1, -1, -1)] #回数も逆順に出しておく

for i in range(2**n):
    s = 0
    m = 0
    max = 0 #残りの中で最も得点の単位が大きいもの
    for j in range(n):
        if((i >> j) & 1):
            max += 1
            s += max_score[j]
            m += howmany[j]
    if(s >= g):
        ans.append(m)
    else:
        if(max < n):
            rest = g - s
            k = -(-rest // score[max]) #最も得点の単位の高い問題を何問解くか
            if(k < howmany[max]):
                m += k
                ans.append(m)

print(min(ans))

Submission status: Accepted

Solution code:
import math

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

P = list()
C = list()

for _ in range(d):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)

check = float('inf')
for i in range(2 ** d):
    ans = 0
    cnt = 0
    for j in range(d):
        # flagがたっていたら
        if (i >> j) & 1:
            ans += P[j] * (j + 1) * 100 + C[j]
            cnt += P[j]
            if ans >= g:
                check = min(check, cnt)
                break
        else:
            rest = j
    extra = P[rest] * (rest + 1) * 100
    if ans < g < (ans + extra):
        cnt += math.ceil(((g - ans) / ((rest + 1) * 100)))
        check = min(check, cnt)

print(check)

Submission status: Accepted

Solution code:
import math
d,g=map(int,input().split())
l=[list(map(int,input().split())) for i in range(d)]
#p,c
cnt=float('inf')
score=0
for i in range(2**d):
    temp_cnt=0
    temp_score=0
    max_point = d - 1
    for j in range(d):
        if (i>>j)&1:
            temp_score+=100*l[d-1-j][0]*(d-j)+l[d-1-j][1]
            temp_cnt+=l[d-1-j][0]
            if d-j-1==max_point:
                #解いてない問題の中で最も配点の高い問題
                max_point+=-1

    left=g-temp_score

    if left>0 and left<l[max_point][0]*100*(max_point+1):
        temp_cnt+=math.ceil(left/(100*(max_point+1)))
        temp_score+=math.ceil(left/(100*(max_point+1)))*100*(max_point+1)
    if temp_cnt<cnt and temp_score>=g:
        cnt=temp_cnt


print(cnt)

Submission status: Accepted

Solution code:
def main():
    D, G = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(D)]
    ans = 10**6
    for bit in range(1 << D):  # bitが立っている問題のコンプリートボーナスを得る
        cur = 0
        cur_sum = 0
        cur_set = set()
        for j in range(D):
            if (bit & (1 << j)):
                cur += A[j][0]
                cur_sum += A[j][1] + A[j][0] * (100*(j+1))
                cur_set.add(j)
        if cur_sum >= G:
            ans = min(ans, cur)
        else:
            less = G - cur_sum
            for j in range(D)[::-1]:
                if j in cur_set:
                    continue
                solve = (less+(100*(j+1))-1)//(100*(j+1))
                less -= min(solve, A[j][0] - 1) * (100*(j+1))
                cur += min(solve, A[j][0] - 1)
                if less <= 0:
                    ans = min(ans, cur)
                    break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
p = [0]*int(D)
c = [0]*int(D)
for i in range(D):
  p[i],c[i] = map(int,input().split())
ans = 1e9
for i in range(2**D):
  s = 0
  num = 0
  rest_max = -1
  for j in range(D):
    if (i>>j)&1:
      s += 100 * (j+1) * p[j] + c[j]
      num += p[j]
    else:
      rest_max = j
  if s<G:
    s1 = 100 * (rest_max + 1)
    need = int((G - s + s1 - 1) / s1)
    if need >= p[rest_max]:
      continue
    num += need
  ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

ans = 1000
for i in range(1<<D):
    point = 0
    comp = 0
    l_index = -1
    for j in range(D):
        if (i>>j)&1:
            comp += Q[j][0]
            point += Q[j][2]
        else:
            l_index = j
    
    if point >= G:
        ans = min(ans,comp)
    else:
        if l_index >= 0:
            for i in range(Q[l_index][0]):
                if point+(l_index+1)*100*i >= G:
                    ans = min(ans,comp+i)
                    break

print(ans)

Submission status: Accepted

Solution code:
import itertools as iter

def main(D,G,lst):
    res = 2**31 -1
    #全問解答するかしないかをBit全探索
    for i in range(2 ** D):
        count = 0
        s, count = calcBounus(D, lst, i)
        #Gに達している場合はresをセット
        if G <= s:
            res = min(res, count)
        #達していない場合、配点の大きい問題を解いていく
        else:
            for j in range(len(lst)):
                #ボーナスのために解答済みならスキップ
                if (i >> (D-j-1)) & 1:
                    continue
                else:
                    tar = lst[-1*(j+1)]
                    if tar[0] == 1:
                        continue
                    for k in range(tar[0]-1):
                        s += 100*(D-j)
                        count += 1
                        if G <= s:
                            res = min(res, count)
    return res

def calcBounus(D, lst, b):
    s = 0
    count = 0
    for i in range(D):
        if (b >> i) & 1:
            count += lst[i][0]
            s += lst[i][1]
            s += 100*(i+1)*lst[i][0]
    return [s,count]
    
D,G = map(int, input().split())
lst = list(list(map(int, input().split())) for _ in range(D))
print(main(D,G,lst))

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
import copy
from heapq import *

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

mincount=10000000
for i in range(2**D):
    b=(D-len(bin(i)[2:]))*"0"+bin(i)[2:]
    value=0
    count=0
    for s in range(D):
        if b[s]=="0":
            pass
        if b[s]=="1":
            p,c=PC[s]
            value+=p*(s+1)*100+c
            count+=p
    for s in range(D-1,-1,-1):
        if value<G:
            if b[s]=="0":
                p,c=PC[s]
                a=min(p-1,(G-value)//((s+1)*100)+((G-value)%((s+1)*100)>=1) * 1)
                count+=a
                value+=a*(s+1)*100
    #print(count,value,"2")
    if value>=G:
        mincount=min(mincount,count)
print(mincount)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
p,c=[],[]
for _ in range(d):
    pi,ci=map(int,input().split())
    p.append(pi)
    c.append(ci)
ans=float("inf")
for i in range(1<<d):
    tmp=0
    solvedproblemNum=0
    problemlist=[]
    for j in range(d):
        if (i>>j) & 1 :
            tmp+=p[j]*100*(j+1)+c[j]
            solvedproblemNum+=p[j]
        else:
            problemlist+=[100*(j+1)]*(p[j]-1)
    problemlist=sorted(problemlist,reverse=True)
    for item in problemlist:
        if tmp>=g:
            ans=min(ans,solvedproblemNum)
            break
        solvedproblemNum+=1
        tmp+=item
    if tmp>=g:
        ans=min(ans,solvedproblemNum)
    # print(problemlist,i,tmp)
print(ans)

Submission status: Accepted

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

#print(plist)

bit = [0,1]
'''
(0, 0, 0, 0, 0)
(0, 0, 0, 0, 1)
(0, 0, 0, 1, 0)
(0, 0, 0, 1, 1)
(0, 0, 1, 0, 0)
(0, 0, 1, 0, 1)
(0, 0, 1, 1, 0)
(0, 0, 1, 1, 1)
(0, 1, 0, 0, 0)
(0, 1, 0, 0, 1)
(0, 1, 0, 1, 0)
(0, 1, 0, 1, 1)
(0, 1, 1, 0, 0)
(0, 1, 1, 0, 1)
(0, 1, 1, 1, 0)
(0, 1, 1, 1, 1)
(1, 0, 0, 0, 0)
(1, 0, 0, 0, 1)
(1, 0, 0, 1, 0)
(1, 0, 0, 1, 1)
(1, 0, 1, 0, 0)
(1, 0, 1, 0, 1)
(1, 0, 1, 1, 0)
(1, 0, 1, 1, 1)
(1, 1, 0, 0, 0)
(1, 1, 0, 0, 1)
(1, 1, 0, 1, 0)
(1, 1, 0, 1, 1)
(1, 1, 1, 0, 0)
(1, 1, 1, 0, 1)
(1, 1, 1, 1, 0)
(1, 1, 1, 1, 1)

'''
answerList = []
for i in range(D):
    answerList.append([plist[i][0], 100 * (i+1) * plist[i][0] + plist[i][1]])


solutionList = itertools.product(bit, repeat=D)
result = []

for i,solutionTupple in enumerate(itertools.product(bit, repeat=D)):
    if i == 0:
        for j in range(answerList[D-1][0]-1):
            a = j + 1
            result.append([j+1, D * 100 * (j + 1)])
        continue

    tmp = [0,0]
    maxIndex = -1
    for i in range(D):
        if solutionTupple[i] == 1:
            tmp[0] += answerList[i][0]
            tmp[1] += answerList[i][1]
        if solutionTupple[i] == 0:
            maxIndex = max(maxIndex, i)

    result.append(tmp)
    #print(solutionTupple)

    if maxIndex == -1:
        break
    for i in range(answerList[maxIndex][0]-1):
        a = tmp[0] + i + 1
        b = tmp[1] + (i + 1) * (maxIndex+1) * 100
        result.append([a,b])
#print(answerList)
#print(result)
answer = float('inf')
for r in result:
    if r[1] >= G:
        answer = min(answer,r[0])

print(answer)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
plist, clist = [], []

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

def dfs(i, s, not_used):
    if i==D:
        if len(not_used)==0:
            return True, 0
        u = max(not_used)
        for p in range(plist[u-1]):
            if s + p * (u*100) >= G:
                return True, p
        return False, 0
    
    check1, num1 = dfs(i+1, s+plist[i]*(i+1)*100+clist[i], not_used)
    check2, num2 = dfs(i+1, s, not_used+[i+1])

    if check1 and check2:
        if num1 + plist[i] <= num2:
            return True, num1 + plist[i]
        else:
            return True, num2
    
    if check1:
        return True, num1 + plist[i]
    
    if check2:
        return True, num2
    
    else:
        return False, 0
    

_, ans = dfs(0, 0, [])

print(ans)

Submission status: Accepted

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

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

#中途半端に解く配点は一種類以下であり、それ以外の配点は冠山に解くか全く解かない
#中途半端に解く配点があるなら、それは完全に解く配点以外の配点の中で最も高い配点である
ans = 10000
#完全に解く配点がある場合
for i in range(2**D+1):
    ok = []
    s = 0
    solve = 0
    for j in range(D):
        a = (i >> j) & 1
        ok.append(a)
    for j in range(D):
        s += ok[j]*pc[j][0]*100*(j+1)
        solve += ok[j]*pc[j][0]
        s += ok[j]*pc[j][1]
    if G<=s:
        #完全に解く配点のみ
        ans = min(ans,solve)
    else:
        #完全に解く配点＋中途半端に解く配点
        for j in range(D):
            sum1 = s
            solve1 = solve
            for k in range(pc[j][0]):
                sum1 += 100*(j+1)*(1-ok[j])
                solve1 += 1*(1-ok[j])
                if G<= sum1:
                    ans = min(ans,solve1)
#完全に解く配点がない場合
for i in range(D):
    s = 0
    solve = 0
    for j in range(pc[i][0]):
        s += 100*(i+1)
        solve += 1
        if G<=s:
            ans = min(ans,solve)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
d,g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float('INF')
inf = float('INF')
for i in range(2**d):
    tmp = 0
    cnt = 0
    for j in range(d):
        p,c = pc[j]
        if i & (1 << j):
            tmp += p * (j+1) * 100 + c
            cnt += p
    if g <= tmp and cnt < ans:
        ans = cnt
    if g > tmp:
        tmp_cnt = inf 
        tmp_ = 0
        gg = (g - tmp) / 100
        for j in range(d):
            p,c = pc[j]
            if i & (1 << j):
                continue
            if ceil(gg / (j+1)) < min(p,tmp_cnt):
                cc = ceil(gg / (j+1))
                tmp_ = cc * (j+1) * 100
                tmp_cnt = cc
            elif gg - c / 100 <= p * (j+1) and p < tmp_cnt:
                tmp_ = p * (j+1) * 100 + c
                tmp_cnt = p
        if g <= tmp + tmp_ and cnt + tmp_cnt < ans:
            ans = cnt + tmp_cnt

print(ans)

Submission status: Accepted

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

# map of {number of problems to achieve ps : ps}
basiclist = []

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)

# combination of perfect score cases: ps0, ps1, ps2, ps0 + ps1, ...
import itertools

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

combs = []

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


mincount = 2**10+1

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

# case of with perfect score
for comb in combs:
    # find the best-valued question that is not in the combination
    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

    # total perfect score of the combination and attempts required to achieve the score
    total_ps = 0
    total_ps_count = 0
    for com in comb:
        total_ps += basiclist[com][1]
        total_ps_count += basiclist[com][0]

    if best_remaining_num == -1:
        mincount = min(mincount, total_ps_count)
        continue

# case ps comb + remaining best-valued question*0, ..., ps comb + remaining best-valued question*(max possible -1)
    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)