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 math


max_rank, target_score = map(int, input().split())

problems = []
min_problems_count = 0
for i in range(max_rank):
	problems.append(list(map(int, input().split())))
	min_problems_count += problems[i][0]


def calc_score(answer_status):
	score = 0
	for i in range(max_rank):
		if answer_status[i] == '1':
			score += (problems[i][0] * 100 * (i + 1) + problems[i][1])
	return score


def calc_problems_count(answer_status):
	count = 0
	for i in range(max_rank):
		if answer_status[i] == '1':
			count += problems[i][0]
	return count


if __name__ == '__main__':
	for i in range(2 ** max_rank):
		is_clear = True
		answer_status = str(format(i, 'b')).zfill(max_rank)
		score = calc_score(answer_status)
		count = calc_problems_count(answer_status)
		if score < target_score:
			is_clear = False
			shortage_score = target_score - score
			min_counts = []
			for j in range(max_rank):
				if answer_status[j] == '0':
					needed_count = math.ceil(shortage_score / ((j + 1) * 100))
					if needed_count <= problems[j][0]:
						min_counts.append(needed_count)
						is_clear = True
			if is_clear:
				count += min(min_counts)
		if is_clear and count < min_problems_count:
			min_problems_count = count
	print(min_problems_count)

Submission status: Accepted

Solution code:
import copy

def calc(wk, kouho, G):
    ans = 0
    for i in range(D):
        if kouho[i] == 1:
            G -= wk[i][1] + 100*(i+1)*wk[i][0]
            ans += wk[i][0]
            wk[i][0] = 0
    if G <= 0:
        return ans
    solve = D-1
    while G > 0 and solve >= 0:
        if wk[solve][0] >= 2: #2問以上問題が残っていれば
            wk[solve][0] -= 1 #その問題を1つ解き
            G -= 100*(solve+1) #得点を加算する
            ans += 1
        if wk[solve][0] <= 1: #残りが一問or既に問題をコンプしていたら
            solve -= 1 #解く問題を変える
    return ans if G <= 0 else 10000

D, G = map(int,input().split())
#100-100*Dの問題をコンプリートするかどうか
zenbu = 2**D
prob = []
min = 10000
for i in range(D):
    prob.append(list(map(int,input().split())))
for i in range(zenbu):
    work = copy.deepcopy(prob)
    kouho = []
    key = i
    for j in range(D):
        kouho.append(key % 2)
        key //= 2
    res = calc(work, kouho, G)
    if res < min:
        min = res
print(str(min))

Submission status: Accepted

Solution code:
from collections import namedtuple
from math import ceil

Problem = namedtuple('Problem', ('count', 'bonus'))

def main():
    d, g = map(int, input().split())
    problems = []
    for _ in range(d):
        count, bonus = map(int, input().split())
        problems.append(Problem(count, bonus))
    
    print(solve(d, g, problems))

def solve(d, g, problems):
    r = float('inf')

    for i in range(2 ** d):
        k = -1
        score = 0
        count = 0
        for j in range(d):
            if (i >> j) & 0x01 != 0:
                score += 100 * (j + 1) * problems[j].count + problems[j].bonus
                count += problems[j].count
            else:
                k = j
        
        if score >= g:
            r = min(r, count)
        else:
            c = ceil((g - score) / (100 * (k + 1)))
            if c <= problems[k].count:
                r = min(r, count + c)

    return r

main()

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict, Counter
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

D, G = s_inpl()
p, c = [], []

for i in range(D):
    pi, ci = s_inpl()
    p.append(pi)
    c.append(ci)

ans = INF
for i in range(1<<D):
    ct = 0
    score = 0
    for j in range(D):
        if i>>j&1:
            score += c[j]
            score += p[j] * (j+1) * 100
            ct += p[j]
    for j in range(D-1, -1, -1):
        if i>>j&1: continue
        if score >= G: break
        g = (j+1)*100
        got = (G-score+g-1)//g
        score += min(got, p[j]) * g
        ct += min(got, p[j])
    ans = min(ans, ct)
print(ans)

Submission status: Accepted

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

#G点のために、

answer = 1e10

from itertools import product

for x in product([0,1], repeat=D):
  #print(x)
  
  temp_score = 0 
  temp_q = 0
  rest = None
  
  for i, _x in enumerate(x):
    if _x:
      temp_score += (i+1)*100*PC[i][0] + PC[i][1]
      temp_q += PC[i][0]
    else:
      rest = i
  #print(temp_score, temp_q, rest)
  if temp_score >= G:
    answer = min(answer, temp_q)
  
  if temp_score < G and (G-temp_score) < PC[rest][0] * (100*(rest+1)):
    answer = min(answer, temp_q + (G-temp_score)//(100*(rest+1)) + bool((G-temp_score)%(100*(rest+1))))
    

print(answer)

Submission status: Accepted

Solution code:
D,G = [int(x) for x in input().split()]
pc = [0]*D
for i in range(D):
    pc[i] = [int(x) for x in input().split()]


mincnt = 10**9

for i in range(1 << D):
    score = 0
    cnt = 0
    full = []
    non_full = []

    for j in range(D):
        if((i>>j & 1) == 1):
            full += [[(j+1)*100]+pc[j]]
        else:
            non_full += [[(j+1)*100]+pc[j]]

    non_full.reverse()

    for j in full:
        score += j[0]*j[1]+j[2]
        cnt += j[1]
    if(score < G):
        for j in non_full:
            a = 1
            while(score+j[0]*a < G and a<j[1]):
                a += 1
            score += j[0]*a
            cnt += a
            if(score >= G):
                mincnt=min(cnt,mincnt)
                break
    else:
        mincnt=min(cnt,mincnt)
    
print(mincnt)

Submission status: Accepted

Solution code:
import itertools

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

m = 10**10
for comb in itertools.product(*[[0, 1]]*D):
    score = 0
    solve = 0
    stack = []
    for i in range(D):
        p, c = pc[i]
        if comb[i] == 1:
            solve += p
            score += p*(i + 1)*100 + c
        else:
            for j in range(p - 1):
                stack.append(i + 1)
    while score < G and len(stack) != 0:
        score += stack.pop()*100
        solve += 1
    if score >= G:
        m = min(m, solve)
print(m)

Submission status: Accepted

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

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 = 1000000000
#bit全探索
n = d
arr = [0] * n
for i in range(2 ** n):
    for j in range(n):
        if((1&i>>j) == 1):
            arr[j] = 1
        else:
            arr[j] = 0
    #ここに処理
    score = 0
    question = 0
    for j in range(len(arr)):
        if arr[j] == 1:
            score += (j+1)*100*p[j] + c[j]
            question += p[j]
    if score >= g:
        ans = min(ans,question)
    else:
        for j in range(len(arr)-1,-1,-1):
            if arr[j] == 0:
                if g - score <= (j+1)*100*(p[j]-1):
                    temp = math.ceil((g - score) / ((j+1)*100))
                    question += temp
                    ans = min(ans,question)
                break


print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
p = [0] * d
c = [0] * d
ans = 10000000000000000000000000000
for i in range(d):
    p[i], c[i] = map(int, input().split())

for i in range(2**d):
    sum = 0
    num = 0
    for j in range(d):
        if i & (1 << j):
            sum += c[j]+p[j]*100*(j+1)
            num += p[j]
    if sum >= g:
        ans = min(ans, num)
    else:
        for j in range(d-1, -1, -1):
            if i & (1 << j):
                continue
            for k in range(p[j]):
                if sum >= g:
                    break
                sum += 100*(j+1)
                num += 1
        ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
ans = float('inf')
D, G = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(D)]
for i in range(1 << D):
    point = 0
    count = 0
    tmp = 0
    for j in range(D):
        if ((i >> j) & 1) == 0:
            if (100 * j + 100) * p[j][0] + p[j][1]:
                tmp = j
        else:
            point += (100 * j + 100) * p[j][0] + p[j][1]
            count += p[j][0]
    if G - point > 100 * (tmp + 1) * p[tmp][0]:
        continue
    count += max(0, ceil((G - point) / (100 * (tmp + 1))))
    ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
D,G = list(map(int,input().split()))
PC = [tuple(map(int,input().split())) for i in range(D)]
res = 99999999999
for i in range(1 << D):
  n = 0
  po = 0
  for j in range(D):
    if ((i >> j) & 1)  == 1:
      n = n + PC[j][0]
      po = PC[j][1] + po + (j+1)*100*PC[j][0]
  if po >= G:
    res = min(n,res)
    continue
  for j in reversed(range(D)):
    if ((i >> j) & 1)  == 0:
      if po + (j+1)*100*(PC[j][0] - 1)  >= G:
        n = n + (G-po+100*(j+1)-1)//(100*(j+1))
        po = G+1
        break
      else:
      	n = n + PC[j][0] - 1
      	po = po + (j+1)*100*(PC[j][0] - 1)
  if po >= G:
  	res = min(n,res)

print(res)

Submission status: Accepted

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

INF = 10 ** 9
ans = []
for i in range(2 ** D):
    ii = bin(i)[2:]
    ii = '0' * (D - len(ii)) + ii
    y = 0
    x = 0
    for j in range(D):
        if ii[j] == '1':
            y += s[j]
            x += p[j]
    yy = G - y
    if yy > 0:
        xx = sum(p)
        flag = False
        for j in range(D):
            xt = x
            if ii[j] == '0':
                ss = 100 * (j + 1)
                if (yy + ss - 1) // ss < p[j]:
                    xt += (yy + ss - 1) // ss
                    if xt < xx:
                        xx = xt
                        flag = True
        if flag:
            x = xx
        else:
            x = INF
    ans.append(x)
print(min(ans))

Submission status: Accepted

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

ans = 1e9
for i in range(1 << D):
  point = 0
  cnt = 0
  for j in range(D):
    if (i >> j)& 1:
      point += PC[j][0]*(j+1)*100+PC[j][1]
      cnt += PC[j][0]
    else:
      tmp = j
  if point < G:
    R = G-point
    if (PC[tmp][0]-1)*(tmp+1)*100 < R:
      continue
    cnt += -(-R//(100*(tmp+1)))
  ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
answer = 0
Q = []
for i in range(d):
    p,c=map(int,input().split())
    answer += p
    Q.append((i+1,p,c))

dp = [-10**9]*(answer+1) 
dp[0] = 0
for i,p,c in Q:
    for j in range(answer,-1,-1):
        for k in range(1,p+1):
            cc = i*100*k
            if k == p:
                cc += c
            if j-k >= 0:
                dp[j]=max(dp[j],dp[j-k]+cc)
        
for i in range(answer+1):
    if dp[i] >= g:
        print(i)
        exit()

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)
    
def f(p,c):
    if p==0:
        return 10**9
    m = min(c//(p*100),P[p-1])
    s = 100*p*m
    if m == P[p-1]:
        s += C[p-1]
    if s < c:
        m += f(p-1,c-s)
    return min(m,f(p-1,c))

print(f(d,g))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
D, G = 0, 0
P, C = [], []


def set_inputs():
    global D, G, P, C
    D, G = get_li()
    P, C = get_data(D, [int, int])
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    all_d = set(range(1, D+1))
    ans = inf
    for i in range(2 ** D):
        comp_d = {j + 1 for j in range(D) if ((1 << j) & i) != 0}
        p = sum(100 * d * P[d-1] + C[d-1] for d in comp_d)
        s = sum(P[d-1] for d in comp_d)
        additional_p = 0
        available_p = 0
        if p < G and i != 2 ** D - 1:
            max_other_d = max(all_d - comp_d)
            additional_p = 100 * max_other_d
            available_p = additional_p * (P[max_other_d-1] - 1)
        if p + available_p < G:
            continue
        tmp = s
        if additional_p:
            tmp += (G - p + additional_p - 1) // additional_p
        ans = min(ans, tmp)
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math
import sys

d, g = [int(x) for x in input()[:-2].split()]
pc = [[int(x) for x in input()[:-2].split()] for _ in range(d)]

def search(choice):
    total = sum(((i + 1) * p + c) * chosen for i, ((p, c), chosen) in enumerate(zip(pc, choice)))
    count = sum(p * chosen for (p, _), chosen in zip(pc, choice))

    if total < g:
        partial = d - list(reversed(choice)).index(0)
        partial_count = math.ceil((g - total) / partial)
        if partial_count <= pc[partial - 1][0]:
            count += partial_count
        else:
            count = sys.maxsize

    return count

print(min(search(choice) for choice in itertools.product(*([0, 1] for _ in range(d)))))

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
#d_pc={}
l_p=[0 for i in range(d)]
l_c=[0 for i in range(d)]
for i in range(d):
    p,c=map(int,input().split())
    #d_pc[p]=c
    l_p[i]=p
    l_c[i]=c
#l=[0 for i in range(d)]
#k=0
#for i in range(d):
#    for j in range(2):
#        l[k]=j

#l_min=[0]*d
num_q_min=100*d
for i in range(2**d):
    num_q=0
    poi=0
    l_sol=[0]*d#前から100,200,,
    for j in range(d):
        if i&1:
            num_q+=l_p[j]
            poi+=l_c[j]+100*(j+1)*l_p[j]
            l_sol[j]=1
        i>>=1
    #print(l_sol)
    #while poi<g:
    for j in range(d):
        if poi>=g:#到達したら
            if num_q<num_q_min:
                num_q_min=num_q
                #l_min=l_sol
            break
        if l_sol[d-1-j]==0:
            delta=(g-poi+100*(d-j)-1)//(100*(d-j))
            if delta>l_p[d-1-j]:
                num_q+=l_p[d-1-j]
                poi+=100*(d-j)*l_p[d-1-j]
            else:
                num_q+=delta
                if num_q<num_q_min:
                    num_q_min=num_q
                    #l_min=l_sol
                break

print(num_q_min)
#print(l_min)

Submission status: Accepted

Solution code:
import sys
d,g=map(int,input().split())
l=[[int(i) for i in l.split()] for l in sys.stdin]
def dfs(x,num,cost,flag):
  if x==len(l):
    return 10**18
  num1=num+l[x][0]*100*(x+1)+l[x][1]
  cost1=cost+l[x][0]
  flag1=flag|(2**x)
  cost3=dfs(x+1,num1,cost1,flag1)
  num2=num
  cost2=cost
  flag2=flag
  cost4=dfs(x+1,num2,cost2,flag2)
  for i in range(len(l),0,-1):
    if 2**(i-1)&flag1>0:
      continue
    if num1>=g:
      break
    if (g-num1+i*100-1)//(i*100)<l[i-1][0]:
      cost1+=(g-num1+i*100-1)//(i*100)
      num1+=((g-num1+i*100-1)//(i*100))*100*i
      break
    else:
      num1+=l[i-1][0]*100*i+l[i-1][1]
      cost1+=l[i-1][0]
  for i in range(len(l),0,-1):
    if 2**(i-1)&flag2>0:
      continue
    if num2>=g:
      break
    if (g-num2+(i*100)-1)//(i*100)<l[i-1][0]:
      cost2+=(g-num2+(i*100)-1)//(i*100)
      num2+=((g-num2+(i*100)-1)//(i*100))*100*i
      break
    else:
      num2+=l[i-1][0]*100*i+l[i-1][1]
      cost2+=l[i-1][0]
  if num1<g:
    cost1=10**18
  if num2<g:
    cost2=10**18
  cost=min(cost1,cost2,cost3,cost4)
  return cost
print(dfs(0,0,0,0))

Submission status: Accepted

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

p = [[i*100] + [int(_) for _ in input().split()] for i in range(1, D+1)]
p.sort(reverse=True)

def dfs(pos, total, maxpos, count, ans):
    if total >= G:
        if count < ans:
            return count
    if pos >= D:
        if maxpos < D:
            for i in range(1, p[maxpos][1]+1):
                if total + i * p[maxpos][0] >= G:
                    if count + i < ans:
                        return count + i
        return ans

    ans1 = dfs(pos+1, total, maxpos, count, ans)
    ans2 = dfs(pos+1, total+p[pos][0]*p[pos][1]+p[pos][2],
            maxpos+1 if pos==maxpos else maxpos, count+p[pos][1], ans)

    return min(ans, ans1, ans2)

print(dfs(0,0,0,0,10000))

Submission status: Accepted

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

ans = 10000
# bit探索
for i in range(1 << D):
    bonus_sum = 0
    cnt = 0
    for j in range(D):
        if (i >> j) & 1 == 1:
            bonus_sum += c[j] + (j + 1) * 100 * p[j]
            cnt += p[j]
    # ボーナスでGを超えたら最小問題数を出す
    if bonus_sum >= G:
        ans = min(ans, cnt)
    # 超えなかったら点数の大きいものを使う
    # 一番大きいものを全部使って、その次の問題を数問使うパターンはない->break処理
    # 全部使う時点でボーナスが発生するのでそれはiの探索にまかせる
    else:
        # bitの0を探索する
        for j in range(D)[::-1]:
            if (i >> j) & 1 == 0:
                # 最大のものを何問使うか
                for k in range(p[j]):
                    ten = (j + 1) * 100 * k
                    if ten + bonus_sum < G:
                        continue
                    else:
                        cnt += k
                        ans = min(ans, cnt)
                        break
                # 一回探索したから終わり
                break

print(ans)

Submission status: Accepted

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

def solve(g,i):
    if i<=0:
        return float('inf')
    n = min(int(g/(100*i)),PC[i-1][0])
    score = 100 * i * n
    if n == PC[i-1][0]:
        score += PC[i-1][1]
    if g > score:
        n += solve(g-score,i-1)
    return min(n,solve(g,i-1))

print(solve(g,d))

Submission status: Accepted

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

import itertools
import collections
import bisect
import math

def main():
    D, G = map(int, input().split())
    p = []
    c = []
    for _ in range(D):
        pi, ci  = map(int, input().split())
        p.append(pi)
        c.append(ci)


    # big value
    INF = int(1e15)
    ans = INF
    # Bit 全探索
    pattern = 1 << D  # 1 をリストの長さだけ左にシフトする
    for i in range(pattern):
        scope = []
        for j in range(D):
            if (i >> j) & 1:
                scope.append(j)

        score = 0
        result = 0
        for s in scope:
            score += (s + 1) * p[s] * 100 + c[s]
            result += p[s]

        # print("i = {}, score = {}, result = {}".format(i, score, result))
        if score < G:
            for idx in range(D - 1, -1, -1):
                if idx not in scope:
                    rest = G - score
                    count = min(math.ceil(rest / ((idx + 1) * 100)), p[idx])
                    # print("idx = {}, count = {}".format(idx, count))
                    score += (idx + 1) * count * 100
                    result += count
                    break

        # print("i = {}, score = {}, result = {}".format(i, score, result))
        if score >= G:
            ans = min(ans, result)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve(G, i):
    if i <= 0:
        return float('inf')
    n = min(int(G/(100*i)), PC[i-1][0])
    score = 100 * i * n
    if n == PC[i-1][0]:
        score += PC[i-1][1]
    if G > score:
        n += solve(G-score, i-1)
    return min(n, solve(G, i-1))


print(solve(G, D))

Submission status: Accepted

Solution code:
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 = float('inf')

for bit in range(2**D):
    score, solve_num = 0, 0

    for i in range(D):
        if (bit >> i) & 1:
            score += (100 * (i+1) * P[i] + C[i])
            solve_num += P[i]

    for i in range(D-1, -1, -1):
        if score >= G:
            break

        if (bit >> i) & 1:
            continue

        for j in range(P[i]):
            score += 100*(i+1)
            solve_num += 1

            if score >= G:
                break

    ans = min(ans, solve_num)

print(ans)

Submission status: Accepted

Solution code:
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 = float('inf')

for bit in range(2**D):
    is_solve = [ 0 for _ in range(D) ]
    score, solve_num = 0, 0
    # i 番目の bit が立っている => 100(i+1)点をつけられた p_i 問を全完する
    for i in range(D):
        if (bit >> i) & 1:
            score += (100 * (i+1) * P[i] + C[i])
            solve_num += P[i]
            is_solve[i] += P[i]

    for i in range(D-1, -1, -1):
        if score >= G:
            break

        while is_solve[i] < P[i]:
            score += 100*(i+1)
            solve_num += 1
            is_solve[i] += 1
            if score >= G:
                break

    ans = min(ans, solve_num)

print(ans)

Submission status: Accepted

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

def main():
	D, G = map(int, input().split(" "))
	
	score_board = []
	all_bms = []
	for i in range(D):
		a, b = map(int, input().split(" "))
		score_board.append((a, b))
		all_bms.append(((i+1) * 100 * a) + b)
	
	ans = 1000000000000
	for i in range(2 ** D):
		total = 0
		turn = 0
		p = 0
		for j in range(D):
			if i >> j & 1 == 1:
				total += all_bms[j]
				a, b = score_board[j]
				turn += a
			else:
				p = j
				
		if G <= total and ans > turn:
			ans = turn
			continue
			
		a, b = score_board[p]
		for i in range(a):
			turn += 1
			total = total + (100 * (p+1))
			if G <= total and ans > turn:
				ans = turn
				continue
		total += b
		if G <= total and ans > turn:
			ans = turn
				
			
	print(ans)
		
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import math
d, g = map(int, input().split())
questions = [list(map(int, input().split())) for _ in range(d)]
ans = 10**9

for i in range(2**d):
    score = 0
    problems = 0
    resindex = -1  # 完全に解いた問題以外で最も点数が高い問題
    for j in range(d):
        # print(i, j)
        # print(i >> j & 1)
        if i >> j & 1 == 1:
            # 完全にj+1問目を解いた時の合計点数
            score += (j+1)*100*questions[j][0] + questions[j][1]
            problems += questions[j][0]
        else:
            resindex = j
    # 完全に解いた問題だけで，目標点数を超えた場合
    if g <= score:
        ans = min(ans, problems)
    # 完全に解いた問題以外で最も点数が高い問題を全て解いて
    # 目標点を超える場合（ボーナス点は考慮しない）
    elif 0 <= resindex \
            and g <= score + questions[resindex][0]*(resindex+1)*100:
        problems += -(-(g-score) // ((resindex+1)*100))
        # problems += math.ceil((g-score) // ((resindex+1)*100))
        ans = min(ans, problems)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

D, G = map(int, input().split())
G //= 100
p = [0]
c = [0]
for _ in range(D):
    pi, ci = map(int, input().split())
    p.append(pi)
    c.append(ci // 100)

q = deque()
q.append((0, 0, 0, " "))
ans = float("inf")
while len(q):
    i, m, g, s = q.pop()
    if i != D:
        q.append((i + 1, m, g, s + "0"))
        q.append((i + 1, m + p[i + 1], g + (i + 1)
                  * p[i + 1] + c[i + 1], s + "1"))
        continue

    if g < G:
        j = s.rfind("0")
        if j < 0:
            continue
        if g + j * (p[j] - 1) < G:
            continue
        m += (G - g + j - 1) // j  # ceil

    ans = min(ans, m)

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    d, g = LI()
    pc = LIR(d)
    ans = float("INF")
    tokumono = list(itertools.product((0, 1), repeat=d))
    #print(tokumono)
    for toku in tokumono:
        #print(toku)
        ansa = 0
        ansb = 0
        for i in range(len(toku)):
            if toku[i] == 1:
                ansa += pc[i][0]
                ansb += pc[i][0] * (i + 1) * 100 + pc[i][1]
        for k in range(len(toku) - 1, -1, -1):
            if toku[k] == 0:
                for i in range(pc[k][0] + 1):
                    #print(ans, ansb, ansa)
                    if i == pc[k][0]:
                        ansb += pc[k][1]
                    if ansb >= g:
                        ans = min(ans, ansa)
                        break
                    ansa += 1
                    ansb += (k+1) * 100
                break

        

    print(ans)
            

    return

#D
def D():
    N, X = LI()
    def dfs(n, x):
        #print(n, x)
        if x == 1 and n > 0:
            return 0 
        elif x < 2 ** (n + 1) - 1:
            return dfs(n - 1, x - 1)
        elif x == 2 ** (n + 1) - 1:
            return 2 ** n 
        elif x == 2 ** (n + 2) - 3:
            return 2 ** (n + 1) - 1
        else:
            return dfs(n - 1, x - 2 ** (n + 1) + 1) + 2 ** n 
    a = dfs(N, X)
    print(a)
        
    return


#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
import itertools as it
D, G = map(int, input().split())
P, C = [], []
for _ in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)
A = it.permutations([i for i in range(D)])
ans = 10**9
for a in A:
    S, i, sub_ans = 0, 0, 0
    while 1:
        if S + (a[i] + 1) * 100 * P[a[i]] < G:
            S += (a[i] + 1) * 100 * P[a[i]]
            sub_ans += P[a[i]]
        else:
            x = (G - S) // ((a[i] + 1) * 100)
            if S + (a[i] + 1) * 100 * x < G:
                x += 1
            sub_ans += x
            S += (a[i] + 1) * 100 * x
        S += C[a[i]]
        if S >= G:
            if sub_ans < ans:
                ans = sub_ans
            break
        i += 1
print(ans)