Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

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

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

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

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

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

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

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

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

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

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

Sample Input 4

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

Sample Output 4

66

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



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Accepted

Solution code:
from math import ceil

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

answer = float("inf")
for combination in range(2 ** d):
    score = 0
    solved = 0
    for difficuty in range(d):
        if (combination >> difficuty) & 1:
            score += points[difficuty][0] * 100 * (difficuty + 1) + points[difficuty][1]
            solved += points[difficuty][0]
    if score < g:
        for difficuty in range(d)[::-1]:
            if not (combination >> difficuty) & 1 and g - score < points[difficuty][0] * 100 * (difficuty + 1):
                solved += ceil((g - score) / (100 * (difficuty + 1)))
                break
        else:
            continue
    if answer > solved:
        answer = solved
print(answer)

Submission status: Accepted

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

import pdb
import sys
import math
F = sys.stdin

D, G = map(int,F.readline().split())
p = []
c = []
all_score = []
maisu = 0
ans = 0
sum = 0
all_selected = [0]*D
for k in range(D):
    p1, c1 = map(int,F.readline().split())
    p.append(p1)
    c.append(c1)
    all_score.append(100 * (k+1) * p1 + c1)

for bit in range(1<<D):
    for i in range(D):
        if bit & (1<<i):
            all_selected[i] = 1
            sum += all_score[i]
            maisu += p[i]

    nokori = G - sum
    if nokori <= 0:
        if ans == 0:
            ans = maisu
        else:
            ans = min(ans, maisu)
        all_selected = [0]*D
        maisu = 0
        sum = 0
        continue

    for j in range(D)[::-1]:
        if all_selected[j] == 0:
            nokorimaisu = math.ceil(nokori / (100 * (j+1)))
            if nokorimaisu <= p[j]:
                maisu += nokorimaisu
                if ans == 0:
                    ans = maisu
                else:
                    ans = min(ans, maisu)
            break

    all_selected = [0]*D
    maisu = 0
    sum = 0

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
f_i = stdin

D, G = map(int, f_i.readline().split())

score_data = []
for i in range(1, D + 1):
    p, c = map(int, f_i.readline().split())
    score = i * 100
    score_data.append((score, p, c))
score_data.sort(reverse=True)

count_rec = []
def dfs(i, score, count, unsolved):
    if score >= G:
        count_rec.append(count)
    elif i == D:
        if unsolved:
            s, p, c = score_data[unsolved[0]]
            remain = G - score
            if s * p >= remain:
                if remain % s == 0:
                    count_rec.append(count + remain // s)
                else:
                    count_rec.append(count + remain // s + 1)
    else:
        s, p, c = score_data[i]
        dfs(i + 1, score + s * p + c, count + p, unsolved)
        dfs(i + 1, score, count, unsolved + [i])

dfs(0, 0, 0, [])
print(min(count_rec))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7
ans = inf
count = 0; pro = 1

d, g = map(int, input().split())
g //= 100
dp=[[inf]*(10**5+10000) for i in range(11)]
dp[0][0]=0
for i in range(d):
    p,c=map(int,input().split());c//=100
    for j in range(10**5+10000):
        if dp[i][j]!=inf:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
            for k in range(1,p):
                dp[i+1][j+(i+1)*k]=min(dp[i+1][j+(i+1)*k],dp[i][j]+k)
            dp[i+1][j+(i+1)*p+c] = min(dp[i+1][j+(i+1)*p+c],dp[i][j]+p)
for i in range(g,10**5+10000):
    ans=min(ans,dp[d][i])
print(ans)




# for i in range(1, d+1):
#     p, c = map(int, input().split())
#     c //= 100
#     # for key, value in tuple(D.items()):
#     #     print(D[key],p)
#     #     D[key+i*p+c//100] = min(D[key+i*p+c//100], D[key]+p)
#     S = D.copy()
#     for key, value in S.items():
#         for k in range(1, p):
#             # print(D[key+i])
#             D[key+i*k] = min(D[key+i*k], S[key]+k)
#         D[key+i*p+c] = min(D[key+i*p+c], S[key]+p)
# ans = inf
# for key, value in D.items():
#     # print(key,value)
#     if key >= g:
#         ans = min(ans, value)
# print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7
ans = inf
count = 0; pro = 1

d, g = map(int, input().split())
g //= 100
dp=[[inf]*(10**5*2) for i in range(11)]
dp[0][0]=0
for i in range(d):
    p,c=map(int,input().split());c//=100
    for j in range(10**5*2):
        if dp[i][j]!=inf:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
            for k in range(1,p):
                dp[i+1][j+(i+1)*k]=min(dp[i+1][j+(i+1)*k],dp[i][j]+k)
            dp[i+1][j+(i+1)*p+c] = min(dp[i+1][j+(i+1)*p+c],dp[i][j]+p)
for i in range(g,10**5*2):
    ans=min(ans,dp[d][i])
print(ans)




# for i in range(1, d+1):
#     p, c = map(int, input().split())
#     c //= 100
#     # for key, value in tuple(D.items()):
#     #     print(D[key],p)
#     #     D[key+i*p+c//100] = min(D[key+i*p+c//100], D[key]+p)
#     S = D.copy()
#     for key, value in S.items():
#         for k in range(1, p):
#             # print(D[key+i])
#             D[key+i*k] = min(D[key+i*k], S[key]+k)
#         D[key+i*p+c] = min(D[key+i*p+c], S[key]+p)
# ans = inf
# for key, value in D.items():
#     # print(key,value)
#     if key >= g:
#         ans = min(ans, value)
# print(ans)

Submission status: Accepted

Solution code:

import math
D,G = map(int, input().split())

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

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


ans = 10000
for n in range(2**D):
    bnum = (bin(n)[2:]).zfill(D)
    score = 0
    cnt = 0
    for i,s in enumerate(bnum):
        if s == "1":
            #print(i, p[i], s[i])
            score += (i+1)*100*p[i] + c[i]
            cnt += p[i]
    
    #print(score, bnum)
    if score >= G:
        ans = min(ans, cnt)
    else:
        for i,s in enumerate(reversed(bnum)):
            if s == "0":
                rest = G - score
                if rest / ((D-i)*100) <= p[i]:
                    #print(bnum, i, rest, cnt , math.ceil(rest / ((D-i)*100)))
                    cnt += math.ceil(rest / ((D-i)*100))
                    ans = min(ans, cnt)


print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = float('inf')
for ptn in product([0, 1], repeat=D):
    total = 0
    cnt = 0
    for i in range(D):
        total += score[i][3] * ptn[i]
        cnt += score[i][1] * ptn[i]

    if 0 in ptn[::-1]:
        i = D - 1 - ptn[::-1].index(0)
        x = score[i]
    else:
        x = score[-1]

    for i in range(x[1]):
        if total >= G:
            break
        total += x[0]
        cnt += 1

    if total < G:
        cnt = float('inf')
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
D,G = map(int, input().split(' '))
prb = []
for i in range(D):
    prb.append(list(map(int, input().split(' '))))
p_cmp = []
for i in range(D):
    p_cmp.append((i+1)*100*prb[i][0]+prb[i][1])
ans = 10**18

for b in range(2**D):
    Gtmp = G
    pslv = 0
    binstr = format(b,'b')
    binstr = binstr.zfill(D)
    for i, x in enumerate(binstr):
        if x == "1":
            Gtmp -= p_cmp[i]
            pslv += prb[i][0]
        if x == '0':
            continue
    if Gtmp > 0:
        for i, x in enumerate(binstr[::-1]):
            if x == "1":
                continue
            if x == '0':
                j = D-i-1
                if Gtmp < prb[j][0] * (j+1) * 100:
                    pslv += (Gtmp + (j+1)*100-1)//((j+1)*100)
                    Gtmp = 0
                    ans = min(ans, pslv)
                    break
                else:
                    break
                break
    if Gtmp <= 0:
        ans = min(ans, pslv)

print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
pc={_:(list(map(int,input().split()))) for _ in range(d)}
bin_lst=[]
d2=2**d
for x in range(d2):
    buf=bin(x)[2:]
    len_buf=len(buf)
    if len_buf<d:
        buf='0'*(d-len_buf)+buf
    bin_lst.append(buf)
lst_cnt=[]
buf_lst=[]
for x in bin_lst:
    cnt=0
    buf_int=0
    len_x=len(x)
    for y in range(d):
        if x[y]=="1":
            buf_lst=pc[y]
            buf_int+=(y+1)*100*buf_lst[0]+buf_lst[1]
            cnt+=buf_lst[0]
    if buf_int<g:
        buf_index=x.rfind("0")
        buf_lst=pc[buf_index]
        i=buf_lst[0]
        for z in range(1,i):
            if buf_int+(buf_index+1)*100*z>=g:
                buf_int+=(buf_index+1)*100*z
                cnt+=z
                break
    if buf_int>=g:
        lst_cnt.append(cnt)
print(min(lst_cnt))

Submission status: Accepted

Solution code:
D , G = map(int,input().split())
bonus = []
question_cnt = []
for i in range(D):
    p , c = map(int,input().split())
    question_cnt.append(p)
    bonus.append(c)
ans = float('inf')
for bit in range(2 ** D):
    sum_val = 0
    tmp_ans = 0
    Flag = False
    for j in range(D):
        if bit >> j & 1:
            sum_val += question_cnt[j] * (j + 1) * 100 + bonus[j]
            tmp_ans += question_cnt[j]
    if sum_val < G:
        for j in range(D-1 , - 1 , -1):
            if Flag:
                break
            if not bit >> j & 1:
                Flag = True
                for k in range(question_cnt[j]):
                    sum_val += (j + 1) * 100
                    tmp_ans += 1
                    if sum_val >= G:
                        break
    if tmp_ans < ans and sum_val >= G:
        ans = tmp_ans
print(ans)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
pc = [list(map(int,input().split())) for i in range(D)]
ans = 10**9
for i in range(2**D):
  score=0
  n=0
  done=""
  for j in range(D):
    if (i>>j)&1:
      score += 100*(j+1)*pc[j][0]+pc[j][1]
      n += pc[j][0]
      done+=str(j)
  if score < G:
    for k in range(D):
      if str(D-k-1) in done:
        continue
      for l in range(pc[D-k-1][0]):
        score += 100*(D-k)
        n += 1
        if score >= G:
          break
      if score >= G:
        break
  ans = min(ans,n)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])


def main():
    d,g=inpm()
    p,c,t=[],[],[]
    ans=10**5
    for i in range(d):
        x,y=inpm()
        p.append(x)
        c.append(y)
        t.append(x*(i+1)*100+y)
    for num in range(1,d+1):
        for groop in combinations(range(d),num):
            total = 0
            member = 0
            for e in groop:
                total += t[e]
                member += p[e]
            if total < g:
                continue
            notgroup = []
            for i in range(d):
                if i not in groop:
                    notgroup.append(i)
            max_e=-1
            if len(notgroup)>0:
                max_e = max(notgroup)
            if max_e == d-1 or max_e==-1:
                pre_ans = 0
                for i in groop:
                    pre_ans += p[i]
                ans = min(ans,pre_ans)
            if max_e!=d-1:
                for way in range(max_e+1,d):
                    if total - c[way] - (way+1)*100 <g:
                        continue
                    diff = total - g - c[way] - (way+1)*100
                    pre_ans = member - 1 - min(p[way]-1,diff//((way+1)*100))
                    ans = min(ans,pre_ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
PC = [list(map(int,input().split())) for _ in range(D)]
comp = [PC[i][0]*(i+1)*100+PC[i][1] for i in range(D)]
ans = float("inf")
for i in range(2**D):
    Gt = 0
    cnt = 0
    lis = [0]*D
    tmp = str(bin(i))[2:]
    for j in range(len(tmp)):
        lis[-j-1] = int(tmp[-j-1])
    for k in range(D):
        if lis[k]:
            Gt += comp[k]
            cnt += PC[k][0]
        else:
            hanpa = k
    if Gt>=G:
        ans = min(ans,cnt)
        continue
    if G-Gt > (PC[hanpa][0]-1)*(hanpa+1)*100:
        continue
    cnt += -(-(G-Gt)//((hanpa+1)*100))
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

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

for i in range(2 ** D):
    a = 0
    b = 0
    for j in range(D):
        if (i >> j) & 1 :
            a += 100 * P[j] * (j + 1) + C[j]
            b += P[j]
    for k in range(D - 1, -1, -1):
        if (i >> k) & 1:
            continue
        if a >= G:
            break
        for l in range(P[k]):
            a += 100 * (k + 1)
            b += 1
            if a >= G:
                break
    ans = min(ans, b)
print(ans)

Submission status: Accepted

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

for i in range(2 ** D):
    a = 0
    b = 0
    for j in range(D):
        if (i >> j) & 1 :
            a += 100 * P[j] * (j + 1) + C[j]
            b += P[j]
    for k in range(D - 1, -1, -1):
        if (i >> k) & 1:
            continue
        if a >= G:
            break
        for l in range(P[k] + 1):
            a += 100 * (k + 1)
            b += 1
            if a >= G:
                break
    ans = min(ans, b)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
D, G = map(int, input().split())
pc = []
for i in range(D):
    p, c = map(int, input().split())
    pc.append([p, c])
ans = 10**7
for i in range(2**D):
    tmp = 0
    cnt = 0
    rest = list(range(1, D+1))
    for j in range(D):
        if (i >> j) & 1 == 1:
            tmp += pc[j][0] * 100 * (j+1) + pc[j][1]
            cnt += pc[j][0]
            rest.remove(j+1)
    # print(rest)
    if tmp < G:
        plus = max(rest)
        n = min(pc[plus-1][0], -(-(G-tmp) // (plus * 100)))
        cnt += n
        tmp += n * plus * 100
    if tmp >= G:
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
D, G = map(int, input().split())
pc = []
for i in range(D):
    p, c = map(int, input().split())
    pc.append([p, c])

ans = []
for i in range(2**D):
    cnt = 0
    tmp = 0
    nokori = set(range(1, D+1))
    for j in range(D):
        if (i >> j) & 1 == 1:
            tmp += pc[j][0] * (100 * (j+1)) + pc[j][1]
            cnt += pc[j][0]
            nokori.discard(j+1)
    if tmp < G:
        use = max(nokori)
        n = min(pc[use-1][0], -(-(G-tmp) // (use * 100)))
        cnt += n
        tmp += n * use * 100
    
    if tmp >= G:
        ans.append(cnt)

print(min(ans))

Submission status: Accepted

Solution code:
def main():

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

    hs = [[0, 0, 0]]
    for i, p, c in A:
        temp = []
        for h, v, q in hs: temp.append([h|(1 << i), v+100*(i+1)*p+c, q+p])
        hs += temp

    # print(hs)

    ans = float('inf')
    for h, v, q in hs:
        if v >= G:
            ans = min(ans, q)
        else:
            for i, p, c in A:
                if (h >> i) % 2 == 0:
                    if v + 100*(i+1)*(p-1) < G:
                        v += 100*(i+1)*(p-1)
                        q += p-1
                    else:
                        if (G-v) % (100*(i+1)) == 0:
                            ans = min(ans, q + (G-v) // (100*(i+1)))
                        else:
                            ans = min(ans, q + 1 + (G-v) // (100*(i+1)))
                        break
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def main():

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

    cur = [[0, 0]]
    used = [set()]

    for i, p, c in A:
        temp = []
        temp_used = []
        for j in range(len(cur)):
            temp.append(cur[j])
            temp_used.append(used[j])
            temp.append([cur[j][0]+ 100*(i+1)*p+c, cur[j][1] + p])
            temp_used.append(used[j] | {i})
        cur = temp
        used = temp_used
    # 
    # print(cur)
    # print(used)

    ans = float('inf')
    for j in range(len(cur)):
        if cur[j][0] >= G:
            ans = min(ans, cur[j][1])
        else:
            for i, p, c in A:
                if i not in used[j]:
                    if cur[j][0] + 100 * (i+1) * (p-1) < G:
                        cur[j][0] += 100 * (i+1) * (p-1)
                        cur[j][1] += p-1
                    else:
                        if (G - cur[j][0]) % (100*(i+1)) == 0:
                            ans = min(ans, cur[j][1] + (G - cur[j][0]) // (100*(i+1)))
                        else:
                            ans = min(ans, cur[j][1] + (G - cur[j][0]) // (100*(i+1)) + 1)
                        break
    return ans



if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys
if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

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

#print(pd)
N = len(pd)

p_effort = []
for i in range(len(pd)):
	p_effort.append([pd[i][0], pd[i][0]*(i+1)*100+pd[i][1]])
#print(p_effort)

bonus_pattern = []
for i in range(2**N):
	bonus = [0] * N
	for j in range(N):
		if (i>>j & 1):
			bonus[N-j-1] = 1
	bonus_pattern.append(bonus)
#print(bonus_pattern)

ans = []
for bp in bonus_pattern:
	total,effort = 0,0
	for i in range(len(bp)):
		if bp[i] == 1:
			total += p_effort[i][1]
			effort += p_effort[i][0]
	#print(bp, total, effort)
	if total < G:
		for j in range(len(bp)-1,-1,-1):
			if bp[j] == 0:
				for _ in range(pd[j][0]):
					#print('here', j)
					total += (j+1)*100
					effort += 1
					if total >= G:
						break
				break
	ans.append([bp,total,effort])
#print(ans)

min_effort = float('INF')
for answer in ans:
	if answer[1]>=G:
		min_effort=min(min_effort, answer[2])

print(min_effort)

Submission status: Accepted

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

ans=100000

for i in range(2**D):
    ten=0
    mondaisu=0
    for j in range(D):
        if ((i>>j)&1):
            ten+=(j+1)*100*p[j]+c[j]
            mondaisu+=p[j]
        else:
            k=j
    if ten>=G:
        if ans>mondaisu:
            ans=mondaisu
    else:
        if G-ten<=(k+1)*100*p[k]:
            mondaisu+=(G-ten-1)//((k+1)*100)+1
            if ans>mondaisu:
                ans=mondaisu
print(ans)

Submission status: Accepted

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

ans=100000

for i in range(2**D):
    ten=0
    mondaisu=0
    for j in range(D):
        if ((i>>j)&1):
            ten+=(j+1)*100*p[j]+c[j]
            mondaisu+=p[j]
        else:
            k=j
    if ten>G:
        if ans>mondaisu:
            ans=mondaisu
    else:
        if G-ten<=(k+1)*100*p[k]:
            mondaisu+=(G-ten-1)//((k+1)*100)+1
            if ans>mondaisu:
                ans=mondaisu
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
P = []
C = []
All = []
for i in range(d):
  p, c = map(int, input().split())
  P.append(p)
  C.append(c)
  All.append((i+1) * p * 100 + c)
#print(All)

import itertools
import math
cand = 100000000000000
for pat in itertools.product([0, 1], repeat=d):
  bonus_point = sum([a * p for a, p in zip(All, pat)])
  bonus_n = sum([num * p for num, p in zip(P, pat)])
  total_n = 0
#  print(bonus_point, bonus_n)
  if bonus_point >= g:
    total_n = bonus_n
  else:
    total_n = bonus_n
    rest = g - bonus_point
    for i in range(d, 0, -1):
      if pat[i-1] == 0:
        if (P[i-1] - 1) * i * 100 >= rest:
          total_n += math.ceil(rest / (i * 100))
          break
        else:
          rest -= (P[i-1] - 1) * i * 100
          total_n += P[i-1]
#  print(bonus_n, total_n)
  cand = min(cand, total_n)
print(cand)

Submission status: Accepted

Solution code:
import math
d, g = map(int, input().split())
p = []
c = []
su = []
ans = 1000
for i in range(d):
  a,b = map(int, input().split())
  p.append(a)
  c.append(b)
  su.append(a*100*(i+1)+b)
bit = [1,2,4,8,16,32,64,128,256,512]
for i in range(int(math.pow(2,d))):
  count = 0
  score = 0
  for j in range(d):
    if i & bit[j] == 0:
      continue
    score += su[j]
    count += p[j]
  if score < g:
    continue
  for j in range(d):
    if i & bit[j] == 0 or score - su[j] >= g:
      continue
    rest = g - (score - su[j])
    count_tmp = min(count , count - p[j] + math.ceil(rest / ((j+1)*100)))
    ans = min(ans, count_tmp)
print(ans)

Submission status: Accepted

Solution code:
# ABC104C
# 解説をみた．
# 一部をとる場合は，まだ残っていてかつ最大の点数のもので良い
import math
inf = 10000000000000000
D, G = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(D)]
ans_cnt = inf
# bit全探索
# ex)i = 0b0000011111 -> 1 ~ 5問目まで全て解く
for i in range(2 ** D):
    flag = True
    tmp_score = 0           # iにおけるscore
    tmp_cnt = 0             # iにおけるcount
    for j in range(D):      # iの各桁が1かどうかを調べる
        if (i >> j) & 1:    # 1の時は足していく
            tmp_score += pc[j][0] * (100 * (j+1)) + pc[j][1]    # p[j]とボーナスを全部足す
            tmp_cnt += pc[j][0]                                 # p[j]:をcountに足す
    if tmp_score < G:       # 足りない時
        for j in range(D-1, -1, -1):    # 使っていなくてかつ最も大きいところからとってくる
            if not (i >> j) & 1:
                tmp_tmp_cnt = math.ceil((G - tmp_score) / ((j+1) * 100))        # Gを超えるのに必要な点数
                if tmp_tmp_cnt > pc[j][0]:          # もってる枚数より多い場合はダメ
                    flag = False
                    break
                else:                               # 足りるならcntに加える
                    tmp_cnt += tmp_tmp_cnt
                    break
    if flag:
        ans_cnt = min(tmp_cnt, ans_cnt)
print(ans_cnt)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
l=[]
for i in range(d):
    l.append(list(map(int,input().split())))
op=[[0],[1]]
for i in range(d-1):
    tmp=[]
    for j in op:
        tmp.append(j+[0])
        tmp.append(j+[1])
    op=tmp
ans=10**10
for i in op:
    z=0
    k=[]
    c=0
    for j in range(d):
        if i[j]==1:
            z+=l[j][0]*100*(j+1)+l[j][1]
            c+=l[j][0]
        else:
            k.append(j)
    if z>=g:
        ans=min(ans,c)
    else:
        if len(k)>0:
            m=max(k)
            p=g-z
            cn=-(-p//((m+1)*100))
            if cn<l[m][0]:
                ans=min(ans,c+cn)
print(ans)

Submission status: Accepted

Solution code:
#各配点の問題について、全て解くor全く解かないを決める
#点数に満たない場合は、配点のうち最も高いものを足りない分解く

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

#まずはbitの列挙、一つずつ探索する
for bit in range(1<<d):
    count = 0
    sum = 0
    #残った配点を列挙するためにsetを用意しておく
    nokori = set(range(1,d+1))

    for i in range(d):
        #各bitが1の場合は解く, i=0は一桁目=1問目を見ている
        if (bit>>i)&1 == 1 :
            sum += pc[i][0] * (100*(i+1)) + pc[i][1]
            count += pc[i][0]
            #set.discard('x')で集合から'x'を削除する
            #i=0 -> 1桁目 -> discard(i+1), set(1, ..., d)
            nokori.discard(i+1)

    #合計sumが求めるgに達していない場合の処理をする
    #足すのは最大のものだけ、それ以外の場合は他のbitで処理
    #sumがgに足りないときはansに入れない
    if sum < g:
        #用いるのは、nokori集合の配点が最大のもの
        use = max(nokori)
        #解く問題数nを設定する
        #(g-sum): 必要な点数、use*100: 1問あたりの点数、切り上げて求める。最大はpi
        n = min(pc[use-1][0], -(-(g-sum)//(use*100)))
        count += n
        sum += n * use * 100
    #sumがgを超えた場合だけ、ansと比較する
    if sum >= g:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
#各配点の問題について、全て解くor全く解かないを決める
#点数に満たない場合は、配点のうち最も高いものを足りない分解く

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

#まずはbitの列挙、一つずつ探索する
for bit in range(1<<d):
    count = 0
    sum = 0
    #残った配点を列挙するためにsetを用意しておく
    nokori = set(range(1,d+1))

    for i in range(d):
        #各bitが1の場合は解く, i=0は一桁目=1問目を見ている
        if bit & (1<<i):
            sum += pc[i][0] * (100*(i+1)) + pc[i][1]
            count += pc[i][0]
            #set.discard('x')で集合から'x'を削除する
            #i=0 -> 1桁目 -> discard(i+1), set(1, ..., d)
            nokori.discard(i+1)

    #合計sumが求めるgに達していない場合の処理をする
    #足すのは最大のものだけ、それ以外の場合は他のbitで処理
    #sumがgに足りないときはansに入れない
    if sum < g:
        #用いるのは、nokori集合の配点が最大のもの
        use = max(nokori)
        #解く問題数nを設定する
        #(g-sum): 必要な点数、use*100: 1問あたりの点数、切り上げて求める。最大はpi
        n = min(pc[use-1][0], -(-(g-sum)//(use*100)))
        count += n
        sum += n * use * 100
    #sumがgを超えた場合だけ、ansと比較する
    if sum >= g:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

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

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def calc(d, mask, probs, g):
    score = 0
    ret = 0
    flags = [mask & (1<<i) for i in range(d)]
    for i in range(d):
        val = (i+1)*100
        p = probs[i][0]
        c = probs[i][1]
        if flags[i]:
            ret += p
            score += c+p*val
    if g <= score:
        return ret
    for i in range(d, -1, -1):
        val = i*100
        p = probs[i-1][0]
        c = probs[i-1][1]
        if flags[i-1]:
            continue
        else:
            if (g - score) > val*(p-1):
                score += val*(p-1)
                ret += p-1
            else:
                np = (g-score+val-1)//val
                score += val*np
                ret += np
                break
    if score < g:
        return 100000
    return ret

def main():
    d, g = rli()
    probs = []
    for i in range(d):
        p, c = rli()
        probs.append([p, c])
    ans = -1
    for i in range(2**d):
        ret = calc(d, i, probs, g)
        # print(bin(i), ret)
        if ans == -1:
            ans = ret
        else:
            ans = min(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
LC=[]
LB=[]
for i in range(d):
	c,b=map(int,input().split())
	LC.append(c)
	LB.append(b)
ans=sum(LC)
for i in range(1<<d):
	P=0
	c=0
	n=-1
	for j in range(d):
		if i&(1<<j):
			P+=(j+1)*100*LC[j]+LB[j]
			c+=LC[j]
		else:
			n=max(n,j)
	if P>=g:
		ans=min(ans,c)
	else:
		if n!=-1:
			for k in range(LC[n]-1):
				P+=(n+1)*100
				c+=1
				if P>=g:
					ans=min(ans,c)
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
pl=[]
cl=[]
for i in range(d):
  p,c=map(int,input().split())
  pl.append(p)
  cl.append(c)
bitlist=[]
for i in range(2**d):
  sub=[]
  num=i
  while num!=0:
    sub.append(num%2)
    num=num//2
  while len(sub)<d:
    sub.append(0)
  bitlist.append(sub)
ans=10000
for i in bitlist:
  l=i
  score=0
  count=0
  for i in range(d):
    if l[i]==1:
      score+=pl[i]*(i+1)*100
      score+=cl[i]
      count+=pl[i]
  if score>g:
    if count<ans:
      ans=count
  else:
    b=False
    for j in range(1,d+1):
      if not b:
        if l[-j]==1:
          pass
        else:
          m=min(pl[-j],(g-score)//((d-j+1)*100))
          score+=m*(d-j+1)*100
          count+=m
          if m==pl[-j]:
            score+=cl[-j]
          if score>g:
            b=True
    if count<ans:
      ans=count    
print(ans)