Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

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

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

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

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

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

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

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

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

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

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

Sample Input 4

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

Sample Output 4

66

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



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Accepted

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

for i in range(2**D):
  point = 0
  count = 0
  bin_i = bin(i)[2:].zfill(D)
  for j in range(D):
    if bin_i[j] == '1':
      point += 100 * (j+1) * pc[j][0] + pc[j][1]
      count += pc[j][0]
  if point >= G:
    count_list.append(count)
  else:
    index = bin_i.rindex('0')
    for j in range(pc[index][0]-1):
        point += 100 * (index+1)
        count += 1
        if point >= G:
          count_list.append(count)
          break
          
print(min(count_list))

Submission status: Accepted

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

ans=10000000000
slis=[]
def dfs(i,point,pr):
    global ans
    global slis
    if i==D:
#        print(point)
#        print(slis)
        if G<=point:
            ans=min(ans,pr)
        else:
            for j in range(D-1,-1,-1):
                if slis[j]==0:
                    k=j
                    break
            
#            print('G-point:',G-point)
#            print('(100*(k+1)*(p[k]-1)):',(100*(k+1)*(p[k]-1)))
            if (G-point)<=(100*(k+1)*(p[k]-1)):
                pr+=-(-(G-point)//(100*(k+1)))
                ans=min(ans,pr)
#                print('ans:',ans)


#            if umax!=-1 and (G-point)<(100*(umax+1)*(p[umax]-1)):
        
        return
    #全て解かない
    slis.append(0)
    dfs(i+1,point,pr)
    slis.pop(-1)
    #全て解く
    slis.append(1)
    dfs(i+1,point+(100*(i+1)*p[i]+c[i]),pr+p[i])
    slis.pop(-1)
dfs(0,0,0)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

def all_comb(iterable):
    for i in range(0, len(iterable) + 1):
        comb = itertools.combinations(iterable, i)
        for pair in comb:
            yield(pair)

def min_solve(goal_point, solve, pc_list):
    solve_point = sum([pc[0] * pc[2] + pc[1] for pc in solve])
    solve_num = sum([pc[0] for pc in solve])
    nc_solve = set(pc_list) - set(solve)
    if solve_point >= goal_point:
        return solve_num
    nc_solve_max = max(nc_solve, key=lambda pc:pc[2])
    if solve_point + (nc_solve_max[0] - 1) * nc_solve_max[2]  >= goal_point:
        min_solve = int(math.ceil((goal_point - solve_point) / nc_solve_max[2] + solve_num))
        return min_solve
    else:
        return float('Inf')

if __name__=='__main__':
    D, G = map(int, input().split())
    pc_list = []
    for i in range(D):
        (p, c) = map(int, input().split())
        pc_list.append((p, c, (i + 1) * 100))
    min_num = min([min_solve(G, solve, pc_list) for solve in all_comb(pc_list)])
    print(min_num)

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())

min_count = 0 #最小問題数
for i in range(2 ** d):
    point = 0 #現在の得点
    count = 0 #現在の問題数
    s = bin(i)[2:].zfill(d)
    for j in range(d):
        # p_kについて2進数のk文字目が1のとき全問、0のとき0問解く
        if s[j] == "1":
            point += 100 * (j+1) * p[j] + c[j]
            count += p[j]
    #目標点を超えた場合
    if point >= g:
        #最小問題数を更新
        if min_count > count or min_count == 0:
            min_count = count
    #目標点を超えなかった場合
    else:
        #未解答中で配点が最大の問題を1問ずつ加算
        index = s.rindex("0")
        for j in range(p[index]-1):
            count += 1
            point += 100 * (index + 1)
            # 目標点を超えた場合
            if point >= g:
                # 最小問題数を更新しbreak
                if min_count > count or min_count == 0:
                    min_count = count
                break

#出力
print(min_count)

Submission status: Accepted

Solution code:
from math import ceil
D,G=map(int,input().split())
p=[0]*D
c=[0]*D

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

flag=0
while(flag < 2**D):
    
    _G=G
    tmp=0
    max_ind=0
    for i in range(D):
        if(flag & 1<<i):
            _G-=p[i]*(i+1)*100 + c[i]
            tmp+=p[i]
        else:
            max_ind=i
    k=ceil( max([(_G),0]) / (100*(max_ind+1)) )  
    if(k < p[max_ind] or k==0):
        tmp+=k
        _min=min([tmp,_min])
    flag+=1
print(_min)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    D, G = map(int, input().split())
    G //= 100

    P, C = [], []
    for _ in range(D):
        p, c = map(int, input().split())
        c //= 100
        P.append(p)
        C.append(c)

    dp = [[INF] * (2 * 10 ** 5 + 10) for _ in range(11)]
    dp[0][0] = 0
    for i in range(D):
        for j in range(len(dp[0])):
            if dp[i][j] == INF:
                continue

            for k in range(P[i] + 1):
                score = (i + 1) * k
                if k == P[i]:
                    score += C[i]
                dp[i + 1][j + score] = min(dp[i + 1][j + score], dp[i][j] + k)

    ans = INF
    for i in range(len(dp)):
        for j in range(len(dp[0])):
            if j >= G:
                ans = min(ans, dp[i][j])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil
D,G=map(int,input().split())
p,c=[0]*D,[0]*D
for i in range(D):
    p[i],c[i]=map(int,input().split())

m=0
mondai=[]
for i in range(2**D,2**(D+1)):
    s=(bin(i))[3:]
    a,b=0,0
    for j in range(D):
        if s[j]=='1':
            a,b=a+p[j],b+100*(j+1)*p[j]+c[j]
        else:
            m=j
    if G<=b:
        mondai.append(a)
    if G-p[m]*100*(m+1)<b<G:
        ad=ceil((G-b)/(100*(m+1)))
        mondai.append((a+ad))
print(min(mondai))

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
PC = [0] + [tuple(map(int, input().split())) for _ in range(D)]
def f(G, i):
    if i == 0:
        return 1e9
    n = min(G // (i * 100), PC[i][0])
    s = n * i * 100
    if n == PC[i][0]:
        s += PC[i][1]
    if s < G:
        n += f(G - s, i - 1)
    return min(n, f(G, i - 1))
print(f(G, D))

Submission status: Accepted

Solution code:
import itertools

def combination(d):
    dd = [i for i in range(d)]
    return [itertools.combinations(dd, i) for i in range(d + 1)]

def all_green(d, g, ps, cs):
    # tood use int max value or other constant value
    min_count = 1000000
    for cc in combination(d):
        for c in cc:
            v = 0
            count = 0
            for ccc in c:
                v += cs[ccc]
                v += (ccc + 1) * 100 * ps[ccc]
                count += ps[ccc]
            if v >= g:
                if count < min_count:
                    min_count = count
                continue
            if count >= min_count:
                continue

            dd = [i if i not in c else None for i in range(d)]
            dd = list(filter(lambda x: x is not None, dd))
            for vvv in reversed(dd):
                for _ in range(ps[vvv]):
                    v += 100 * (vvv + 1)
                    count += 1
                    if v >= g:
                        if count < min_count:
                            min_count = count
                        break
                if count >= min_count:
                    break
    return min_count

d, g = map(int, input().split())
ps = []
cs = []
for _ in range(d):
    p, c = map(int, input().split())
    ps += [p]
    cs += [c]
print(all_green(d, g, ps, cs))

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)
iters = 2 ** D
ans = 1<<30
for i in range(iters):
    score = 0
    nums = 0
    for b in range(D):
        if ((1 << b) & i) != 0:
            score += c[b] + p[b] * 100 * (b+1)
            nums += p[b]
    need = G - score
    if need <= 0:
        ans = min(ans, nums)
        continue
    for b in range(D):
        if (1 << b) & i == 0:
            kai = (need+(100*(b+1)-1)) // (100*(b+1))
            if kai <= p[b]:
                ans = min(ans, kai+nums)
print(ans)

Submission status: Accepted

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

#各得点帯の問題を完答したときの点数をcscoreに入れる
for i in range(D):
    pi, ci = map(int, input().split())
    p.append(pi)
    c.append(ci)
    score = pi * (i+1) * 100 + ci
    cscore.append(score)

#各得点帯を完答する組み合わせ全パターン試してその総得点をtotscoreに入れる
totscore = []
for i in range(1 << len(cscore)):
    output = []
    for j in range(len(cscore)):
        if ((i >> j) & 1) == 1:
            output.append(cscore[j])
    tot = 0
    for i in range(len(output)):
        tot += output[i]
    totscore.append(tot)
#totscoreの各場合においてそれぞれ解くべき問題数を計算
for i in range(len(totscore)):
    problems = 0
    b = format(i, "b").zfill(D)

    #完答のみで目標得点を超えている場合はその問題数を計算
    if totscore[i] >= G:
        for k in range(D):
            problems += p[k] * int(b[D-1-k])
        ans.append(problems)

    #完答のみで目標得点を超えていない場合は得点の高い方から問題を1問ずつ解いていく
    else:
        remainscore = G - totscore[i]
        for k in range(D):
            problems += p[k] * int(b[D-1-k])
        for l in range(D, 0, -1):
            if int(b[D-l]) == 0:
                for m in range(p[l-1]):
                    if remainscore > 0:
                        remainscore -= l * 100
                        problems += 1
        #点数がGに届いてない場合はカット
        if remainscore <= 0:
            ans.append(problems)

#条件を満たしたもののうち最小値を出力
print(min(ans))

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
p = [0]*(d+1)
c = [0]*(d+1)
for i in range(1,d+1):
  p[i],c[i] = map(int,input().split())
m = sum(p)
for x in range(2**d-1):
  b = str(format(x, '010b'))
  s = 0
  y = 0
  for i in range(1,d+1):
    if b[-i] == "1":
      s += 100*i*p[i]+c[i]
      y += p[i]
    else:
      a = i
  if g <= s:
    m = min(m,y)
  elif g <= s+100*a*p[a]:
    m = min(m,y+(g-s+100*(a-1))//(100*a))
print(m)

Submission status: Accepted

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

minProblems = 10000000

for i in range(2 ** D):
    tempScore = 0
    bit = 1
    solveSet = [False] * D
    solveCount = 0
    for j in range(D):
        if i & bit:
            solveSet[j] = True
            solveCount += p[j]
            tempScore += p[j] * 100 * (j + 1)
            tempScore += c[j]

        bit = bit << 1
    
    if tempScore >= G:
        minProblems = min(minProblems, solveCount)
        continue

    minNeedProblems = 10000000
    for j in range(D):
        if not solveSet[j]:
            needPoint = G - tempScore
            needProblems = (needPoint - 1) // (100 * (j + 1)) + 1
            if needProblems < p[j]:
                minNeedProblems = min(minNeedProblems, needProblems)

    if minNeedProblems <= 100:
        minProblems = min(minProblems, solveCount + minNeedProblems)

print(minProblems)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter
D, G = map(int, input().split())
P = [list(map(int, input().split())) for i in range(D)]
min_num = 10**8

judge_list = list(itertools.product([0, 1, 2], repeat=D)) #0:中途半端に解く 1:一問も解かない 2: 全部解く


for judge in judge_list:
    score = 0
    num = 0
    d = Counter() #インスタンスを生成
    d.update(judge)
    if (d[0] <= 1):
        for i in range(1, len(judge) + 1):
            if score >= G:
                break

            if judge[-i] == 1:
                pass

            if judge[-i] == 2:
                score += P[-i][0] * (D - i + 1) * 100 + P[-i][1]
                num += P[-i][0]

            if (judge[-i] == 0):
                for j in range(P[-i][0]):
                    if score >= G:
                        break
                    score += 100 * (D - i + 1)
                    num += 1

        if score >= G:
            min_num = min(num, min_num)

print(min_num)

Submission status: Accepted

Solution code:
D,G = [int(i) for i in input().split()]
pc = [[int(i) for i in input().split()]for j in range(D)]
Ans = sum(list(map(list, zip(*pc)))[0])
G1 = G 
for i in range(2**D-1):
    ans = 0
    G1 = G
    i2 = '0'*(D-len(str(bin(i)[2:100])))+str(bin(i)[2:100])
    i_2 = i2.rfind('0')
    for j in range(D):
        if i2[j] == '1':
            G1 -= pc[j][0]*(j+1)*100 + pc[j][1]
            ans += pc[j][0]
    if G1 <= 0:
        Ans = min(Ans,ans)
    elif G1 <= pc[i_2][0]*(i_2+1)*100:
        Ans = min(Ans,ans-(-G1//((i_2+1)*100)))
print(Ans)

Submission status: Accepted

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

ans = 10 ** 9
for msk in range(1 << D):
    tmp = 0
    cnt = 0
    for i in range(D):
        if msk >> i & 1:
            p, c = pc[i]
            tmp += p * (i + 1) * 100 + c
            cnt += p

    for i in range(D - 1, -1, -1):
        if tmp >= G:
            break
        if (msk >> i & 1) ^ 1:
            p, c = pc[i]
            k = min(p, -(-(G - tmp) // ((i + 1) * 100)))
            cnt += k
            tmp += (i + 1) * 100 * k

    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
# ABC 104 C
# bit
import math
D, G = map(int, input().split())
S = [list(map(int, input().split())) for k in range(D)]

ans = float("inf")
for k in range(2**D):
    temp_score = 0
    temp_ans = 0
    r = -1
    for l in range(D):
        if int(bin(k>>l)[-1]):
            temp_score += (l+1)*100*S[l][0] + S[l][1]
            temp_ans += S[l][0]
        else:
            r = l
    if temp_score < G:
        if G-temp_score <= (r+1)*(S[r][0]-1)*100:
            temp_ans += math.ceil((G-temp_score)/((r+1)*100))
        else:
            temp_ans = float("inf")
    ans = min(ans,temp_ans)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import math

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

D, G = ds_in()

Score = []
for i in range(D):
    p, c = ds_in()
    Score.append([(i+1)*100, p, c])

INF = 10**10

search = []
def SearchMin(search, idx):
    if idx == D:
        score = 0
        num = 0
        res = []
        maxprob = [0, 0, 0]
        for s, i in zip(Score, search):
            num += s[1] * i
            score += (s[0] * s[1] + s[2]) * i
            if i == 0 and s[0] > maxprob[0]:
                maxprob = s.copy()
        if (G > score) and (math.ceil((G - score) / maxprob[0]) <= maxprob[1]):
            return num + max(0, math.ceil((G - score) / maxprob[0]))
        elif G <= score:
            return num
        else:
            return INF

    else:
        s0 = search.copy()
        s0.append(0)
        s1 = search.copy()
        s1.append(1)
        idx += 1
        ans0 = SearchMin(s0, idx)
        ans1 = SearchMin(s1, idx)
        return min(ans0, ans1)

print(SearchMin(search, 0))

Submission status: Accepted

Solution code:
# coding:utf-8

INF = float('inf')


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


D, G = inpl()
P, C = [], []
for i in range(D):
    p, c = inpl()
    P.append(p)
    C.append(c + 100 * (i + 1) * p)

ans = INF
for i in range(2 ** D):
    point = 0
    cnt = 0
    rest_max = 0
    for shift in range(D):
        if i >> shift & 1:
            cnt += P[shift]
            point += C[shift]
        else:
            rest_max = shift

    if point < G:
        for j in range(P[rest_max]):
            if point >= G:
                break
            cnt += 1
            point += (rest_max + 1) * 100
        else:
            continue

    ans = min(ans, cnt)

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_cnt = 10 ** 20
for i in range(2 ** (D)):
    def make_p(i):
        p = bin(i)[2::]
        while len(p) != D:
            p = "0" + p
        key = D
        for j in range(D - 1, -1, -1):
            if int(p[j]) == 0:
                key = j
                break
        return p, key
    
    p_and_key = make_p(i)
    p = p_and_key[0]
    key = p_and_key[1]
    cnt = 0
    ansP = 0
    for j in range(len(p)):
        if p[j] == "1":
            ansP += pc[j][0] * 100 * (j + 1) + pc[j][1]
            cnt += pc[j][0]
    j = 0
    if int(key) != int(D):
        key = int(key)
        while ansP < G:
            j = int(j)
            if pc[key][0] <= j:
                break
            ansP += 100 * (key + 1)
            cnt += 1
            j += 1
    if ansP >= G:
        ans_cnt = min(ans_cnt, cnt)

print(ans_cnt)

Submission status: Accepted

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

a=[]
for j in range(d):
  a.append([(j+1)*100*l[j][0]+l[j][1],l[j][0]])

b=[]
for k in range(2**d):
  b.append(format(k,'0'+str(d)+'b'))

c=[]
for m in range(len(b)):
  e=0;f=0;z=-1
  for n in range(d):
    if b[m][n]=='1':
      e+=a[n][0];f+=a[n][1]
    else:
      z=n+1
  c.append([e,f,z])

p=[]
for x in range(len(c)):
  q=c[x][0];r=c[x][1];s=c[x][2]
  if q>=g:
    p.append(r)
  else:
    for y in range(a[s-1][1]+1):
      q+=s*100;r+=1
      if q>=g:
        p.append(r)
        break

print(min(p))

Submission status: Accepted

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

a=[]
for j in range(d):
  a.append([(j+1)*100*l[j][0]+l[j][1],l[j][0]])

b=[]
for k in range(2**d):
  b.append(format(k,'0'+str(d)+'b'))

c=[]
for m in range(len(b)):
  e=0;f=0;z=-1
  for n in range(d):
    if b[m][n]=='1':
      e+=a[n][0]
      f+=a[n][1]
    else:
      z=n+1
  c.append([e,f,z])

p=[]
for x in range(len(c)):
  if c[x][0]>=g:
    p.append(c[x][1])
  else:
    r=c[x][0];s=c[x][1]
    for y in range(a[c[x][2]-1][1]+1):
      r+=c[x][2]*100
      s+=1
      if r>=g:
        p.append(s)
        break

print(min(p))

Submission status: Accepted

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

a=[]
for j in range(d):
  b=[]
  b.append((j+1)*100*l[j][0]+l[j][1])
  b.append(l[j][0])
  a.append(b)

c=[]
for k in range(2**d):
  c.append(format(k,'0'+str(d)+'b'))

e=[]
for m in range(len(c)):
  f=0;h=0;z=-1
  for n in range(d):
    if c[m][n]=='1':
      f+=a[n][0]
      h+=a[n][1]
    else:
      z=n+1
  e.append([f,h,z])

p=[]
for x in range(len(e)):
  if e[x][0]>=g:
    p.append(e[x][1])
  else:
    r=e[x][0];s=e[x][1]
    for y in range(a[e[x][2]-1][1]+1):
      r+=e[x][2]*100
      s+=1
      if r>=g:
        p.append(s)
        break

print(min(p))

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-

def main():
    d, g = map(int, input().split())
    prob_list = [tuple(map(int, input().split())) for _ in range(d)]
    ans = float('inf')

    for x in range(2 ** d):
        score = 0
        tmp_ans = 0
        bonus_list = []
        for i in range(d):
            if (x >> i) % 2 == 1:
                score += prob_list[i][0] * (i + 1) * 100 + prob_list[i][1]
                tmp_ans += prob_list[i][0]
                bonus_list.append(i)
        if score < g:
            for j in range(d-1, -1, -1):
                if j not in bonus_list:
                    if score + (prob_list[j][0] - 1) * (j + 1) * 100 >= g:
                        tmp_ans += -(-(g - score) // ((j + 1) * 100)) 
                        break
                    else:
                        tmp_ans = float('inf')
        ans = min(ans, tmp_ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n,g = map(int,input().split())
lis = []
sum = []
for i in range(n):
  a,b = map(int,input().split())
  lis.append([a,b])
  sum.append((i+1)*100*a+b)
def ans(x,y):
  if y <= 0:return 10 ** 12
  nu = min(math.ceil(x/(100 * y)),lis[y-1][0])
  num = 100 * y * nu
  if nu == lis[y-1][0]:num += lis[y-1][1]
  if num >= x:cou = nu
  else:cou = nu +ans(x-num,y-1)
  return min(cou,ans(x,y-1))

print(ans(g,n))

Submission status: Accepted

Solution code:
import math

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

ans = sum(P)
for i in range(2**D - 1):
    inSolve = -1
    score_tmp = 0
    solved = 0
    for j in range(D):
        if (i>>j)%2 == 1:
            score_tmp += (j+1)*100*P[j]+C[j]
            solved += P[j]
        else:
            inSolve = max(j,inSolve)
    if score_tmp < G and inSolve != -1:
        if math.ceil((G-score_tmp)/((inSolve+1)*100)) <= P[inSolve]:
            ans = min(ans,solved + math.ceil((G-score_tmp)/((inSolve+1)*100)))
    elif score_tmp >= G:
        ans = min(ans,solved)
print(ans)

Submission status: Accepted

Solution code:
def max_zero(t, n):
    if n % 2 == 1:
        n = (n-1) / 2
        t += 1
        return(max_zero(t, n))
    else:
        return t


d, g = [int(_) for _ in input().split()]
l = [0] * d
for i in range(d):
    p, c = [int(_) for _ in input().split()]
    all_score = (i+1)*100*p + c
    l[i] = [p, all_score]

n = 2**d
ans = float('inf')
for i in range(n):
    total = 0
    p_total = 0
    st = '0' + str(d) + 'b'
    n_bin = format(i, st)
    for j in range(d):
        if n_bin[j] == '1':
            total += l[j][1]
            p_total += l[j][0]
    if total >= g:
        ans = min(ans, p_total)
    else:
        b = g - total
        y = max_zero(0, i)
        a = d * 100 - 100 * y
        if b % a == 0:
            u = b // a
        else:
            u = (b // a) + 1
        if u <= l[d-1-y][0]-1:
            ans = min(ans, p_total + u)
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import itertools
import numpy as np
# d, g = 2, 700
# ls_p = [3, 5]
# ls_c = [500, 800]
d, g = map(int,input().split())
ls_p = []
ls_c = []
for i in range(d):
    p, c = map(int,input().split())
    ls_p.append(p)
    ls_c.append(c)
ls_p = np.array(ls_p)
min = ls_p.sum()
ls_c = np.array(ls_c)
nums = [0, 1]
ls_isFull = np.array([list(i) for i in itertools.product(nums, repeat=d)])[:-1]
ls_count = ls_isFull * ls_p

w = np.arange(1,d+1) * 100
#print (ls_count.dot(w) + ls_isFull.dot(ls_c))

def get_idx(ls):
    return max(np.where(ls==0)[0])


for i in range(len(ls_count)):
    
    if ls_count[i].sum() >=  min:
        continue
    idx = get_idx(ls_isFull[i])
    for j in range(ls_p[idx]):

        score = ls_count[i].dot(w) + ls_isFull[i].dot(ls_c)
        #print ( ls_count[i], score)

        if (score >= g) &  (ls_count[i].sum() < min):
            min = ls_count[i].sum()
            #print (min)
            continue
        ls_count[i][idx]+=1
print (min)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - All Green
https://beta.atcoder.jp/contests/abc104/tasks/abc104_c

"""
import sys
from sys import stdin
input = stdin.readline


from itertools import combinations
from math import ceil

def solve(D, G, scores):
    def pick_max(comb):
        a = [i*100 for i in range(D, 0, -1)]
        for c in comb:
            a.remove(c)
        return a[0] if a else None


    ans = float('inf')
    points = [100 * p for p in range(1, D+1)]

    for d in range(D+1):
        for comb in combinations(points, d):
            score = 0
            pick = 0
            for p in comb:
                score += (p * scores[p][0]) + scores[p][1]
                pick += scores[p][0]
            if score < G:
                ad = pick_max(comb)
                if ad:
                    n = ceil((G - score) / ad)
                    if n >= scores[ad][0]:
                        pick = float('inf')
                    else:
                        pick += n
                else:
                    pick = float('inf')
            ans = min(ans, pick)
    return ans


def main(args):
    D, G = map(int, input().split())

    scores = {}
    for i in range(1, D+1):
        p, c = map(int, input().split())
        scores[i*100] = [p, c]
    ans = solve(D, G, scores)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
li = lambda: list(map(int,input().split()))

d,g = li()
g //= 100
num,comp = [], []
for _ in range(d):
    a,b = li()
    num.append(a)
    comp.append(b//100)

from itertools import product
mul = product((0, 1), repeat=d)

ans = float('inf')
for m in mul:
    pt = sum(m[i]*comp[i] for i in range(d)) + sum(m[i]*(i+1)*num[i] for i in range(d))
    n = sum(m[i]*num[i] for i in range(d))
    if pt < g:
        if not all(m):
            i = [i for i,j in enumerate(m) if j==0][-1]
        else:
            continue
        if pt + (i+1)*(num[i]-1) < g:
            continue
        n += -((pt-g)//(i+1))
    ans = min(ans,n)
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
	d, g = list(map(int, input().split()))
	problems = [list(map(int, input().split())) for _ in range(d)]

	ptns = list(itertools.product([0, 1], repeat = d))

	ans = 10 ** 10

	for pt in ptns:
		rest = g - sum([((i + 1) * 100 * problems[i][0] + problems[i][1]) * pt[i] for i in range(d)])
		tmp = sum([problems[i][0] * pt[i] for i in range(d)])
		
		if rest > 0:
			if 0 in pt:
				rest_max_idx = d - pt[::-1].index(0) - 1
				#print(pt, tmp, rest_max_idx, rest)
				for i in range(problems[rest_max_idx][0]):
					rest -= (rest_max_idx + 1) * 100
					tmp += 1
					if rest <= 0:
						break

		if rest <= 0:
			ans = min(ans, tmp)

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
plist=[]
clist=[]
for i in range(d):
    p,c=map(int,input().split())
    plist.append(p-1)
    clist.append(c)
def f(pl,goal):
    result=0
    if goal<0:
        return 0
    for i in range(d,0,-1):
        if goal>=pl[i-1]*(i)*100:
            result+=pl[i-1]
            goal-=pl[i-1]*(i)*100
        else:
            if goal%((i)*100)==0:
                result+=goal//((i)*100)
                goal=0
                break
            
                
            result+=goal//((i)*100)+1
            goal=0
            break
    if goal>0:
        return 1000
    return result
blist=[list(str(bin(i)))[2:][-1::-1]for i in range(2**d)]
result=1000
    
for c in blist:
    qlist=plist[:]
    h=g
    ires=0
    for i in range(len(c)):
        if c[i]=='1':
            qlist[i]=0
            h-=clist[i]+(plist[i]+1)*(i+1)*100
            ires+=plist[i]+1
    result=min([result,f(qlist,h)+ires])
print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
D,G = map(int,input().split())

G1 = int(G)
G2 = int(G)
taples = []
count = 1e9

for i in range(D):
	p,c = map(int,input().split())
	taples.append((p,c,100*(i+1)))

for bit in range(1 << D):
	# bit = [0 ~ 1<<D)
	sumpoint = 0
	solved = 0
	remprob = []
	for i in range(D):
		# i bit目が立っているか
		if (bit >> i) & 1:
			# 100i点の問題を全問解く
			sumpoint += 100*(i+1)*taples[i][0]+taples[i][1]
			solved += taples[i][0]
		else:
			# 解かない
			remprob.append(i)
	
	if sumpoint < G:
		maxi = max(remprob)
		for num in range(1, taples[maxi][0]):
			if sumpoint + 100*(maxi+1)*num >= G:
				count = min(count, solved + num)
				break
	else:
		count = min(count, solved)

print(count)

Submission status: Accepted

Solution code:
from itertools import product


def f(comb, ans, scores):
    score = 0
    problems = 0
    for i, bi in enumerate(comb):
        if bi == 1:
            score += scores[i][1] + scores[i][0] * 100 * (i + 1)
            problems += scores[i][0]

    if score >= g:
        return min(ans, problems)

    else:
        for j in reversed(range(d)):
            if comb[j] == 0:
                for _ in range(1, scores[j][0]):
                    problems += 1
                    score += (j + 1) * 100
                    if score >= g:
                        ans = min(ans, problems)
                        return ans

        return ans


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

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

ans = float("inf")
for comb in product((0, 1), repeat=d):
    ans = f(comb, ans, scores)

print(ans)