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:
import sys
sys.setrecursionlimit(10**8)
def dfs(i, sum, count, nokori):
    global ans
    if i == d:
        # G 点に満たなければ nokori のうち一番大きいものを解く
        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})


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

ans = float("inf")

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

Submission status: Accepted

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


import sys


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


def resolve():
    d, target_score = map(int, input().split())
    p_list = []
    c_list = []
    for i in range(d):
        p, c = map(int, input().split())
        p_list.append(p)
        c_list.append(c)

    ans_list = []

    for bit in range(1<<d):
        # bitが1のところはボーナス
        temp_score = 0
        counter = 0
        for i in range(d):
            # print(str(bit) + ":" + str(i))

            if bit & (1<<i):
                p = p_list[i]
                c = c_list[i]

                temp_score += 100 * (i+1) * p
                temp_score += c
                counter += p
                # print(counter, i, p, temp_score, target_score)
                if temp_score >= target_score:
                    ans_list.append(counter)
                    break

        # 残りは配点の高い問題から
        for i in range(len(p_list)-1, -1, -1):
            achieve_flag = False
            # コンプリートボーナスをもらった問題は飛ばす
            if bit & (1<<i):
                continue

            for j in range(p_list[i]-1):
                temp_score += 100 * (i+1)
                counter += 1
                #print(counter, i, temp_score, target_score)
                if temp_score >= target_score:
                    achieve_flag = True
                    break

            if achieve_flag:
                ans_list.append(counter)
                break

    # 結果出力
    print(min(ans_list))


if __name__ == "__main__":
    resolve()

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())
    
cnt_min = sum(p)

for i in range(2**D):
    flg = [False] * D
    cnt = 0
    score = 0
    for j in range(D):
        if i & (1 << D-1-j):
            flg[j] = True
            cnt += p[j]
            score += p[j]*(j+1)*100 + c[j]
    
    if score >= G:
        if cnt < cnt_min:
            cnt_min = cnt
    else:
        for j in reversed(range(D)):
            if flg[j]:
                continue
            for k in range(p[j]-1):
                cnt += 1
                score += (j+1)*100
                if score >= G:
                    if cnt < cnt_min:
                        cnt_min = cnt
                        break                        
            break
print(cnt_min)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# bit全探索
D, G = lr()
PC = [lr() for _ in range(D)]
answer = 10 ** 5
for pattern in range(1<<D):
    # patternが1のところはコンプリートボーナス
    temp = 0
    cnt = 0
    for i in range(D):
        if pattern>>i & 1:
            temp += PC[i][1] + (i+1) * 100 * PC[i][0]
            cnt += PC[i][0]
    j = D-1  # 残りは配点の多い問題から, 0-indexed
    while temp < G:
        if j < 0:
            break
        if pattern>>j & 1:
            j -= 1
            continue
        remain = G - temp
        point = (j + 1) * 100
        problems = (remain + point - 1) // point
        problems = min(problems, PC[j][0])
        cnt += problems
        temp += point * problems
        j -= 1
    else:
        if cnt < answer:
            answer = cnt

print(answer)

Submission status: Accepted

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

def dfs(d,flag,point,count,tmp):
    point += flag * (PC[d-1][1]+PC[d-1][0]*d*100)
    count += flag * (PC[d-1][0])
    if flag == 0:
        tmp = d
    if d == D:
        if point < G:
            r = math.ceil((G-point)/(tmp*100))
            if r < PC[tmp-1][0]:
                res = count + r
            else:
                res = float("INF")
        else:
            res = count
        return res

    else:
        return min(dfs(d+1,1,point,count,tmp),dfs(d+1,0,point,count,tmp))

print(min(dfs(1,0,0,0,0),dfs(1,1,0,0,0)))

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)

m=100000000000000
for i in range(2**d):
    count=0
    count2=0
    for j in range(d):
        if i&(2**j):
            count+=p[j]*(j+1)*100+c[j]
            count2+=p[j]
    if count>=g and count2<m:
        m=count2
    for j in reversed(range(d)):
        if not(i&(2**j)):
            for k in range(p[j]):
                if count>=g and count2<m:
                    m=count2
                    break
                count+=(j+1)*100
                count2+=1
            break

print(m)

Submission status: Accepted

Solution code:
from itertools import product

D, G = map(int, input().split(' '))
questions = [tuple(map(int, input().split(' '))) for _ in range(D)]
questions = [(100 * index, n, bonus) for index, (n, bonus) in enumerate(questions, start=1)]

min_answer = 1000

for bits in product((True, False), repeat=D):
    not_complete = []
    score = G
    answered = 0
    for index, bit in enumerate(bits):
        if not bit:
            not_complete.append(index)
            continue

        point, n, bonus = questions[index]
        score -= point * n + bonus
        answered += n

    if not_complete:
        index = max(not_complete)
        point, n, _ = questions[index]
        while score > 0 and n > 1:
            score -= point
            n -= 1
            answered += 1

    if score <= 0:
        min_answer = min(min_answer, answered)

print(min_answer)

Submission status: Accepted

Solution code:
import math

def f(i, s):
    global ans
    if s.count(1) > 1:
        return
    if i == d:
        score = 0
        cnt = 0
        notcomp = -1
        for k in range(d):
            if s[k] == 1:
                notcomp = k
            if s[k] == 2:
                score += comp[k]
                cnt += x[k][0]
        if g <= score:
            ans = min(ans, cnt)
        elif not notcomp == -1:
            r = g - score
            if r <= comp[notcomp]:
                cnt += min(math.ceil(r / ((notcomp + 1) * 100)), x[notcomp][0])
                ans = min(ans, cnt)
        return
    for j in range(3):
        s[i] = j
        f(i + 1, s)

d, g = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(d)]
comp = [x[i][0] * 100 * (i + 1) + x[i][1] for i in range(d)]
s = [0] * d
ans = pow(10, 3)
f(0, s)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(D)]
G /= 100
C = 2e3
N = len(pc)
for i in range(2 ** N):
    p = 0
    c = 0
    for j in range(N):
        if i >> j & 1:
            p += pc[j][0] * (j + 1) + pc[j][1] / 100
            c += pc[j][0]
    if p >= G:
        C = min(c, C)
        continue
    for j in range(N-1, -1, -1):
        if not i >> j & 1:
            for k in range(pc[j][0] - 1):
                p += j + 1
                c += 1
                if p >= G:
                    break
        if p >= G:
            break
    if p >= G:
        C = min(c, C)
        continue

print(C)

Submission status: Accepted

Solution code:
import math
d,g = map(int,input().split())
p = [0 for i in range(d)]
c = [0 for i in range(d)]
for i in range(d):
    p[i],c[i] = [int(j) for j in input().split()]

mn = 10**18
for i in range(2**d):
    ii = i
    ni = 0
    mh = -1
    pi = 0
    for j in range(d):
        if ii&1 == 1:
            pi += p[j]*(j+1)*100+c[j]
            ni += p[j]
        else:
            mh = j
        ii >>= 1
    res = g-pi
    if res > (p[mh]-1)*(mh+1)*100:
        continue
    elif 0 < res:
        ni += math.ceil(res/((mh+1)*100))
    if mn > ni:
        mn = ni

print(mn)

Submission status: Accepted

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

scores = []
nums = []
for i in range(0, 2**D):
    score = 0
    num = 0
    remain = []
    for j in range(D):
        if (i>>j)&1:
            score += P[j]*(j+1) + C[j]
            num += P[j]
        else:
            remain.append(j)
    if score >= G:
        scores.append(score)
        nums.append(num)
    else:
        remain = sorted(remain, reverse=True)
        nokori = G - score
        for r in remain:
            if P[r] > -(-nokori // (r+1)):
                num += -(-nokori // (r+1))
                nums.append(num)
                break
print(min(nums))

Submission status: Accepted

Solution code:
import math

d, g = map(int, input().split()) 
num = []
comp = []
for i in range(d):
    p, c = map(int, input().split())
    num.append(p)
    comp.append(p * (i + 1) * 100 + c)

ans = 9999999999999
for i in range(1 << d):
    pos = i
    cnt = 0
    total = 0
    last = -1
    for j in range(d):
        if pos % 2 == 1:
            total += comp[j]
            cnt += num[j]
        else:
            last = j
        pos //= 2
    if total >= g:
        ans = min(ans, cnt)
    elif last == -1:
        continue
    else:
        rem = g - total
        if rem <= num[last] * (last + 1) * 100:
            cnt += math.ceil(rem / ((last + 1) * 100))
            ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

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

for i in range(d+1):
  for j in itertools.combinations(range(d),i):
    score,pro1=0,0
    for k in j:
      score += (PC[k][1] + (k+1) * 100 * PC[k][0])
      pro1 += PC[k][0]
    for k in range(d):
      pro2 = pro1
      if score >= g:
        ans.append(pro2)
      elif k in j:
        continue
      p=math.ceil((g-score) / ((k+1) * 100))
      if 0 < p < PC[k][0]:
        pro2 += p
        ans.append(pro2)
        
print(min(ans))

Submission status: Accepted

Solution code:
inf = 10 ** 15
mod = 10 ** 9 + 7

d,g = map(int, input().split())
p = [list(map(int, input().split())) for i in range(d)]
p.reverse()
ans = inf
for i in range(2**d):
    count = 0
    total = 0
    for j in range(d):  # このループが一番のポイント
        if ((i >> j) & 1):  # 1だったら(オンだったら)
            count += p[j][0]
            total += p[j][0] * 100*(d-j) + p[j][1]
    if total >= g:
        ans = min(ans, count)
    else:
        for j in range(d):
            if not ((i >> j) & 1):
                num = p[j][0]
                score = 100*(d-j)
                if score*num >= g-total:
                    must = (g-total+score-1)//score
                    total+=score*must
                    count+=must
                    break
                else:
                    total+=score*num
                    count+=num
        ans = min(ans, count)
print(ans)

Submission status: Accepted

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

#print(pc)
minn=10000
flug=[]
def func(D,G,pc,flug,i=0,summ=0,num=0):
    global minn
    if i==D:
        #print(flug,summ,num)
        if summ>=G:
            minn=min(minn,num)
            return 0
        else:
            for j,bit in enumerate(reversed(flug)):
                if bit==0:
                    for k in range(pc[D-1-j][0]):
                        summ+=(D-j)*100
                        num+=1
                        if summ>=G:
                            minn=min(minn,num)
        return 0

    return func(D,G,pc,flug+[1],i+1,summ+pc[i][0]*100*(i+1)+pc[i][1],num+pc[i][0]) + func(D,G,pc,flug+[0],i+1,summ,num)


func(D,G,pc,flug)
print(minn)

Submission status: Accepted

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

ans = 1 << 29
t = []
for bit in range(1<<D):
    score = 0
    f = 0
    # フラグが立ってる問題を全完
    for i in range(D):
        if bit & (1<<i):
            score += pc[i][0]*100*(i+1) + pc[i][1]
            f += pc[i][0]
            if score >= G: break
    # 全完した問題以外の中から点数の高い順に解いていく
    nokori = []
    for j in range(D):
        if not (bit & (1<<j)):
            nokori.append(pc[j] + [j+1])
    nokori = list(reversed(nokori))
    for d in nokori:
        for x in range(d[0]):
            if score >= G: break
            score += 100*(d[2])
            f += 1
        if score >= G: break
    ans = min(ans,f)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
p_input = [0]*d
c_input = [0]*d

for i in range(d):
    p_input[i],c_input[i] = map(int,input().split())

ans=float('inf')
for i in range(2**d):
    problem=0
    point=0
    for j in range(d):
        if ((i>>j)&1):
            problem+=p_input[j]
            point+=(1+j)*100*p_input[j]+c_input[j]
    if point>=g:
        ans=min(ans,problem)
    else:
        for j in range(d-1,-1,-1):
            if ((i>>j)&1):
                continue
            for k in range(p_input[j]):
                if point>=g:
                    break
                problem+=1
                point+=100*(j+1)
        ans = min(ans,problem)
            
print(ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc104/tasks/abc104_c

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

set_all=set()
for i in range(d):
    set_all.add(i)


count=1001
for i in range(2**d):
    score=0
    count_buf=0
    set1=set()
    for j in range(d):
        if (i>>j)&1:
            score+=100*(j+1)*l[j][0]+l[j][1]
            count_buf+=l[j][0]
            set1.add(j)
    if score>=g:
        count=min(count,count_buf)
    else:
        set2=set_all-set1
        list_set2=list(set2)
        if len(list_set2)>0:
            list_set2.sort(reverse=True)
            for k in range(l[list_set2[0]][0]):
                score+=100*(list_set2[0]+1)
                count_buf+=1
                if score>=g:
                    count=min(count,count_buf)
                    break
    #print(score)
print(count)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    D,G = LI()
    pc = [LI() for _ in range(D)]
    m = [i for i in range(D)]
    ans = INF
    for p in itertools.permutations(m):
        g = G
        cnt = 0
        for i in p:
            if g < pc[i][0] * (i+1) * 100:
                cnt += math.ceil(g/((i+1)*100))
                break
            else:
                cnt += pc[i][0]
                g -= pc[i][0] * (i+1) * 100 + pc[i][1]
            if g <= 0: break
        ans = min(ans,cnt)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

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

    ans = INF
    for p in itertools.permutations(range(D)):
        g = G
        cnt = 0
        for i in p:
            if g < pc[i][0] * (i+1) * 100:
                cnt += math.ceil(g/((i+1)*100))
                break
            else:
                cnt += pc[i][0]
                g -= pc[i][0] * (i+1) * 100 + pc[i][1]
            if g <= 0: break
        ans = min(ans,cnt)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
D, G = list(map(int,input().split()))
p = []
c = []

for i in range(D):
    in1, in2 = list(map(int,input().split()))
    p.append(in1)
    c.append(in2)
    
ans = 10 ** 9 + 7
for x in range(2 ** D):
    b = str(format(x, '010b'))
    score = 0
    res = 0
    not_perfect = 0
    for i in range(D):
        if b[-(i + 1)] == "1": 
            score += (p[i] * 100 * (i + 1) + c[i])
            res += p[i]
        else:
            not_perfect = i
    rest = G - score
    if rest > 0:
        s = 100 * (not_perfect + 1)
        for i in range(p[not_perfect]):
            res += 1
            rest -= s
            if rest <= 0:
                break
        if rest > 0:
            res = 10 ** 9 + 7
    ans = min(ans, res)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

def judge(li):
    score = 0
    cnt = 0
    for i in range(len(li)):
        if li[i] == False:
            continue
        score += pc[i][1]
        score += pc[i][0]*(i+1)*(100)
        cnt += pc[i][0]
    return [cnt,score]
    
        
D,G = map(int,input().split())
pc = []
for i in range(D):
    p,c = map(int,input().split())
    pc.append([p,c])
ans = 100000000000000
for i in range(2**D):
    li = [False]*(D)
    for j in range(D):
        if (i>>j)&1:
            li[D-j-1] = True
    a = judge(li)
    j = D-1
    if a[1]<G:
        need = G-a[1]
        while True:
            if a[1]>=G:
                break
            if j == -1:
                break
            if li[j] == True:
                j-=1
                continue
            for k in range(pc[j][0]-1):
                a[1] += (j+1)*(100)
                a[0] += 1
                if a[1]>=G:
                    break
            j-=1
    if a[1]>=G:
        ans = min(ans,a[0])
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")


def main():
    d, g = MI()
    pc = [LI() for _ in range(d)]

    ans = inf
    for bit in range(1 << d):
        c = 0
        score = 0
        for i in range(d):
            if bit & (1 << i):
                c += pc[i][0]
                score += pc[i][0] * 100 * (i + 1) + pc[i][1]

        if score >= g:
            ans = min(ans, c)
        else:
            for i in reversed(range(d)):
                if bit & (1 << i):
                    continue
                res = math.ceil((g - score) / (100 * (i + 1)))
                if res < pc[i][0]:
                    ans = min(ans, c + res)
                break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")


def main():
    d, g = MI()
    pc = [LI() for _ in range(d)]

    ans = inf
    for bit in range(2 << d):
        c = 0
        score = 0
        for i in range(d):
            if bit & (1 << i):
                c += pc[i][0]
                score += pc[i][0] * 100 * (i + 1) + pc[i][1]

        if score >= g:
            ans = min(ans, c)
        else:
            for i in reversed(range(d)):
                if bit & (1 << i):
                    continue
                res = math.ceil((g - score) / (100 * (i + 1)))
                if res < pc[i][0]:
                    ans = min(ans, c + res)
                break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import math


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


"""
Dがちいさいのでビット全探索させたそう
中途半端に色んな得点の問題を解くより、全部解く問題と部分的に解く問題に分かれるはず。
で、部分的に解く問題は、残りの中で一番得点が高い物を選ぶのがよい。
で、それを必要な分（あるいは全部-1）解いて得られる点がGを超えていれば、答えの候補になる
候補の中から最小のを選んで終わり
"""

ans = []
for bit in range(1 << D):
    point = 0
    cnt = 0
    for i in range(D):
        if bit & (1 << i):
            point += 100*(1+i)*PC[i][0] + PC[i][1]
            cnt += PC[i][0] 

    idx = -1
    for i in range(D):
        if not bit & (1 << i):
            idx = i

    if idx == -1:
        ans.append(cnt)
    else:
        rem = max(0, G - point)
        if rem == 0:
            ans.append(cnt)
        else:
            extr_cnt = math.ceil(rem / (100*(idx+1)))
            if extr_cnt <= PC[idx][0]-1:
                ans.append(cnt+extr_cnt)


print(min(ans))

Submission status: Accepted

Solution code:
from math import ceil
d,g = map(int,input().split())
point = [list(map(int,input().split())) for _ in range(d)]
ans = 10**18
for i in range(2**d):
  l = []
  cnt = 0
  s = 0
  for j in range(d):
    if i >> j & 1:
      cnt += point[j][0]
      s += point[j][0]*100*(j+1) + point[j][1]
    else:
      l.append(j)
  if s >= g:
    ans = min(ans,cnt)
    continue
  for j in l:
    if g-s > 100*(j+1)*(point[j][0]-1):
      continue
    else:
      ans = min(ans,cnt+ceil((g-s)/(100*(j+1))))
print(ans)

Submission status: Accepted

Solution code:
def rec(i, g, count, rem):
    global ans
    if i == 0:
        # 総得点がGを超えていなければ、remの中の最高配点の問題を解く
        if g < G:
            # 解く問題
            use = max(rem)
            c = min(pc[use-1][0], -(-(G-g) // (use*100)))
            count += c
            g += use*100 * c
            
            
        if g >= G:
            ans = min(ans, count)
            
    else:
        # 全部解かない
        rec(i-1, g, count, rem)
        # 全部解く
        rem[i] = 0
        rec(i-1, g+i*100*pc[i-1][0]+pc[i-1][1], count+pc[i-1][0], rem)
        rem[i] = i

# 入力
D, G = map(int, input().split())
pc = [[int(i) for i in input().split()] for j in range(D)]
# 解いてない問題リスト
rem = [i for i in range(D+1)]
ans = float("inf")

rec(D, 0, 0, rem)

print(ans)

Submission status: Accepted

Solution code:
def rec(i, g, count, rem):
    global ans
    if i == D:
        # 総得点がGを超えていなければ、remの中の最高配点の問題を解く
        if g < G:
            # 解く問題
            use = max(rem)
            c = min(pc[use-1][0], -(-(G-g) // (use*100)))
            count += c
            g += use*100 * c
            
        if g >= G:
            ans = min(ans, count)
    else:
        # 全部解かない
        rec(i+1, g, count, rem)
        # 全部解く
        rec(i+1, g+(i+1)*100*pc[i][0]+pc[i][1], count+pc[i][0], rem-{i+1})

# 入力
D, G = map(int, input().split())
pc = [[int(i) for i in input().split()] for j in range(D)]
# 解いてない問題リスト
rem = set(range(1, D+1))
ans = float("inf")

rec(0, 0, 0, rem)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math


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


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    D, G = map(int, input().split())
    problems = [list(map(int, input().split())) for _ in range(D)]
    answer = INF
    for i in range(2 ** D):
        ans = 0
        point = 0
        for j in range(D):
            if (i >> j) & 1:
                point += problems[j][0] * 100 * (j + 1) + problems[j][1]
                ans += problems[j][0]
        j = D - 1

        while point < G and j >= 0:
            if not (i >> j) & 1:
                p = math.ceil((G - point) / (100 * (j + 1)))
                if problems[j][0] >= p:
                    point += p * 100 * (j + 1)
                    ans += p
                    j = 0
                else:
                    j = 0
            j -= 1
        if answer > ans and point >= G:
            answer = ans
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    D, G = map(int, input().split())
    PC = [(0, 0, 0)]
    for i in range(1, D + 1):
        p, c = map(int, input().split())
        PC.append((i, p, c))
    perms = permutations(range(1, D + 1))

    ans = INF
    for p in perms:
        tmp = 0
        cnt = 0
        for idx in p:
            i, p, c = PC[idx]
            if tmp + 100 * i * p >= G:
                cnt += (G - tmp + 100 * i - 1) // (100 * i)
                break
            elif tmp + 100 * i * p + c >= G:
                cnt += p
                break
            else:
                tmp += 100 * i * p + c
                cnt += p

        if cnt < ans:
            ans = cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math

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

ans = float("inf")

for i in range(2 ** D):
    total = 0
    num = 0
    idx = []
    for k in range(D):
        if i >> k & 1 == 1:
            idx.append(k)
    
    for j in idx:
        d = data[j]
        total += d[0] * d[1] + d[2]
        num += d[1]
    
    if total >= G:
        ans = min(ans, num)
    else:
        for j in set(range(D)) - set(idx):
            d = data[j]
            if total + d[0] * (d[1] - 1) >= G:
                num += math.ceil((G - total) / d[0])
                ans = min(ans, num)
                continue
            else:
                total += + d[0] * (d[1] - 1)
                num += d[1] - 1
print(ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc104/tasks/abc104_c
 
d, g = map(int, input().split())
pc = []
 
for i in range(d):
  pc.append(list(map(int,input().split())))
 
ans = float("inf")
 
#各配点について解くか解かないかを決め、その上で G 点に満たなければ、まだ解いてない配点のうち一番高い配点のものを足りない分解く
 
for i in range(2**d):
    count = 0 #解く問題数
    sum = 0
    nokori = set(range(1, d + 1)) #点数の列
 
    for j in range(d):
        if (i>>j)&1:
            sum += pc[j][0] * (j + 1) * 100 + pc[j][1] #(j+1)*100点+bounus
            count += pc[j][0]
            nokori.discard(j + 1) #(j+1)*100点を処理したので削除
 
    # G 点に満たなければ nokori のうち一番大きいものを解く
    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)
 
print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().strip().split())
pc=[]
for _ in range(D):
    pc.append(list(map(int,input().strip().split())))
    
min_num=0
for i in range(D):
    min_num+=pc[i][0]

def dfs(l,D,G):
    global min_num
    score=0
    num=0
    if len(l)==D:
        for n in range(len(l)):
            if l[n]==1:
                score+=pc[n][0]*100*(n+1)+pc[n][1]
                num+=pc[n][0]
        if score>=G:
            min_num=min(min_num,num)
        else:
            for n in reversed(range(len(l))):
                if l[n]==0:
                    i=0
                    while i<=pc[n][0]-1 and score<G:
                        score+=100*(n+1)
                        num+=1
                        i+=1
                    if score>=G:
                        break
            min_num=min(min_num,num)
        return
    else:
        for n in range(2):
            l.append(n)
            dfs(l,D,G)
            l.pop()
dfs([],D,G)
print(min_num)