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: Time Limit Exceeded

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

def gen(i, p, c):
  it = [ (0,0) ]
  for _p in range(p):
    if _p == p-1:
      it.append( (c + (i+1)*(_p+1)*100, _p+1) )
    else:
      it.append( ((i+1)*(_p+1)*100, _p+1) )
  return it

its = []
for i in range(D):
  p, c = map(int, input().split())
  it = gen(i, p, c)
  its.append( it )
from functools import reduce
import copy
ps = [ [0, 0] ]
for it in its:
  size = len(it)
  ps_next = []
  for p in ps:
    for cur in range(size): 
      pp    = copy.copy(p)
      pp[0] += it[cur][0]
      pp[1] += it[cur][1]
      ps_next.append( pp )
  ps = ps_next
#sys.exit()
ps = [ p for p in ps if p[0] >= G]
#print(ps)
print( min(ps, key=lambda x:x[1])[1] )

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

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

ans = 114514
for order in itertools.permutations(range(d)):
    point = 0
    cnt = 0
    for i in order:
        if g - point <= 100 * (i + 1) * p[i]:
            cnt += math.ceil((g - point) / (100 * (i + 1)))
            break
        elif g - point <= 100 * (i + 1) * p[i] + c[i]:
            cnt += p[i]
            break
        else:
            point += 100 * (i + 1) * p[i] + c[i]
            cnt += p[i]         

    ans = min([ans, cnt])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
D,G=map(int,raw_input().split())
G=G/100

P=[map(int,raw_input().split()) for i in range(D)]

S=10**5+100
#S=30

dp=[ [ float("inf") for i in range(S)]  for j in range(D) ] 
a=P[0][0]
b=P[0][1]/100

for i in range(a+1):
	if i==a: dp[0][i+b]=i
	else: dp[0][i]=i

for j in range(D): dp[j][0]=0


for i in range(1,D):
	a=P[i][0]
	b=P[i][1]/100


	for s in range(S):
		for k in range(1,a):
			if s-(k*(i+1)) >=0:
				dp[i][s]=min( dp[i-1][s-(k*(i+1))]+k, dp[i-1][s] )
		if s-( a*(i+1)+b )>=0:
			dp[i][s]=min( dp[i-1][s-( a*(i+1)+b ) ]+a, dp[i-1][s] )


ans=float("inf")
for i in range(G,S):
	ans=min(ans,dp[D-1][i] )

print ans

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

ans = float('inf')
caches = []
for perm in permutations(range(d)):
    flag = False
    for cache in caches:
        if perm[:len(cache)] == cache:
            flag = True
    if flag:
        continue
    h = g
    tmp = 0
    cache = []
    for i in perm:
        cache.append(i)
        p, c, a, b = pcs[i]
        if h <= a:
            q = (h - 1) // (i + 1) + 1
            tmp += q
            break
        tmp += p
        h -= b
        if h <= 0:
            break
        if tmp >= ans:
            break
    ans = min(ans, tmp)
    caches.append(cache)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

d, g = map(int, input().split())
dp = defaultdict(lambda: float('inf'))
dp[0] = 0
for i in range(d):
    p, c = map(int, input().split())
    solo_score = (i + 1) * 100
    ndp = dp.copy()
    for s, q in dp.items():
        if s == g:
            continue
        for j in range(1, p):
            k = min(g, s + solo_score * j)
            ndp[k] = min(ndp[k], q + j)
        k = min(g, s + solo_score * p + c)
        ndp[k] = min(ndp[k], q + p)
    dp = ndp
print(dp[g])

Submission status: Time Limit Exceeded

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

import math
m = {}
def f(cur, n, left):
    if left <= 0:
        return n
    def g(cur, n, left):
        if cur in m: return m[cur]
        r = m[cur] = f(cur, n, left)
        return r
    ret = 10**9
    for x in pc:
        i, p, c = x
        if (1 << i) & cur: continue
        ip = i*100*p
        if ip > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            if n + p >= ret: continue
            h = f(cur | (1 << i), n + p, left - ip - c)
            ret = min(ret, h)
    return ret

print(f(0, 0, G))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
D, G = map(int, input().split(" "))
data = np.array([list(map(int, input().split())) for i in range(D)])

calc = np.array([[100*(i+1)*j + data[i, 1] if j == data[i, 0]
                  else 100*(i+1)*j for j in range(data[i, 0]+1)] for i in range(D)])

x = np.array(list(itertools.product(*calc)))

y = np.sum(x, axis=1)
I = np.zeros(y.shape)
os = np.where(y >= G, y, I)

res = [sum(np.asscalar(np.where(calc[j] == x[i][j])[0])
           for j in range(len(calc))) if o != 0 else 10**10 for i, o in enumerate(os)]
print(min(res))

Submission status: Time Limit Exceeded

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

import math
m = {}
def f(cur, n, left):
    if left <= 0:
        return n
    def g(cur, n, left):
        if cur in m: return m[cur]
        r = m[cur] = f(cur, n, left)
        return r
    ret = 10**9
    for x in pc:
        i, p, c = x
        if i in cur: continue
        if i*100*p > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            if n + p >= ret: continue
            cur.add(i)
            h = f(cur, n + p, max(0, left - i*100*p - c))
            cur.remove(i)
            ret = min(ret, h)
    return ret

print(f(set(), 0, G))

Submission status: Time Limit Exceeded

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

import math
m = {}
def f(cur, n, left):
    if left <= 0:
        return n
    def g(cur, n, left):
        if cur in m: return m[cur]
        r = m[cur] = f(cur, n, left)
        return r
    ret = 10**9
    for x in pc:
        i, p, c = x
        if i in cur: continue
        if i*100*p > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            cur.add(i)
            h = f(cur, n + p, max(0, left - i*100*p - c))
            cur.remove(i)
            ret = min(ret, h)
    return ret

print(f(set(), 0, G))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil
d, g = map(int, input().split())
P = {}
C = {}
for i in range(1,d+1):
    p, c = map(int, input().split())
    P[i] = p
    C[i] = c

ans = 100000
# S問題でiから始めてh点取る時の必要問題数
# 例: S = [1, 2, 5]
def solve(h, i, S):
    # コンプせずにいけるとき
    if h <= 100*i*(P[i]-1):
        return ceil(h/(100*i))
    # コンプでいけるとき
    elif h <= 100*i*P[i]+C[i]:
        return P[i]
    # 足りないとき
    else:
        p = P[i]
        if p > ans:
            return p
        h -= (100*i*p+C[i])
        S.remove(i)
        min_p = 100000
        for j in S:
            min_p = min(min_p, solve(h, j, S.copy()))
        p += min_p
        return p

for j in list(range(1,d+1)):
    ans = min(ans, solve(g, j, list(range(1,d+1))))
print(ans)

Submission status: Time Limit Exceeded

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

#残りgと100iの問題に費やした回数を返す
def solve(g, i):
  #全問解いても終わらないケース
  if p[i]*100*i + c[i] < g:
    return g-(p[i]*100*i + c[i]), p[i]
  #ボーナス無しでも終わるケースはgを超えるのに必要な問題数だけ解く
  elif p[i]*100*i > g:
    return 0, math.ceil(g/i/100)
  #ボーナスあれば終わるケースはちょうどp[i]問解く
  else:
    return 0, p[i]

def func(g, remain):
  m = 0
  for j in remain:
    new_remain = copy(remain)
    new_remain.remove(j)
    new_g, n = solve(g, j)
    if (m==0 or n<m) and g>0:
      n += func(new_g, new_remain)
    if m==0:
      m=n
    else:
      m=min(m,n)
  return m

remain=[]
for k in range(1,D+1):
  remain.append(k)
ans = func(G,remain)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

ans = sum(p)
for i in range(D):
        for j in range(p[i]):
                for k in range(2**D-1):
                        score = (i+1)*100*j
                        ans_tmp = j
                        for l in range(D):
                                if l == i:
                                        continue
                                elif (k>>l)%2 == 1:
                                        score += (l+1)*100*p[l]+c[l]
                                        ans_tmp += p[l]
                        if score >= G:
                                ans = min(ans,ans_tmp)

print(ans)

Submission status: Time Limit Exceeded

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

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

def Calc(score, num):
    temp = list(filter(lambda x: x[1] < num+1, score))
    if temp == []:
        return score[-1][0] * num
    else:
        cand = []
        if len(score) == 1:
            cand.append(temp[0][0]*temp[0][1] + temp[0][2])
        else:
            copy_score = score.copy()
            for t in temp:
                temp_score = score.copy()
                del temp_score[temp_score.index(t)]
                del copy_score[copy_score.index(t)]
                cand.append(t[0]*t[1] + t[2] + Calc(temp_score, num - t[1]))
            if len(copy_score) > 0:
                cand.append(copy_score[-1][0] * num)
        return max(cand)

a, b = 1, q_sum+1
while (b-a) > 1:
    if Calc(Score, (b+a) // 2) >= G:
        b = (b+a) // 2
    else:
        a = (b+a) // 2
if Calc(Score, a) >= G:
    print(a)
else:
    print(b)

Submission status: Time Limit Exceeded

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

#残りgと100iの問題に費やした回数を返す
def solve(g, i):
  #全問解いても終わらないケース
  if p[i]*100*i + c[i] < g:
    return g-(p[i]*100*i + c[i]), p[i]
  #ボーナス無しでも終わるケースはgを超えるのに必要な問題数だけ解く
  elif p[i]*100*i > g:
    return 0, math.ceil(g/i/100)
  #ボーナスあれば終わるケースはちょうどp[i]問解く
  else:
    return 0, p[i]

def func(g, remain):
  m = 0
  for j in remain:
    new_remain = copy(remain)
    new_remain.remove(j)
    new_g, n = solve(g, j)
    if g>0:
      n += func(new_g, new_remain)
    if m==0:
      m=n
    else:
      m=min(m,n)
  return m

remain=[]
for k in range(1,D+1):
  remain.append(k)
ans = func(G,remain)
print(ans)

Submission status: Time Limit Exceeded

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

import math, copy
m = {}
def f(cur, n, pc, left):
    if left <= 0:
        return n
    def g(cur, n, pc, left):
        fp = (cur, left)
        if fp in m: return m[fp]
        m[fp] = f(cur, n, pc, left)
        return m[fp]
    ret = 10**9
    for x in pc:
        i, p, c = x
        if i*100*p > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            nc = copy.copy(cur)
            nc.add(i)
            npc = copy.copy(pc)
            npc.remove(x)
            h = f(nc, n + p, npc, max(0, left - i*100*p - c))
            ret = min(ret, h)
    return ret

print(f(set(), 0, pc, G))

Submission status: Time Limit Exceeded

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

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

def Calc(score, num):
    temp = list(filter(lambda x: x[1] < num+1, score))
    if temp == []:
        return score[-1][0] * num
    else:
        cand = []
        if len(score) == 1:
            cand.append(temp[0][0]*temp[0][1] + temp[0][2])
        else:
            copy_score = score.copy()
            for t in temp:
                temp_score = score.copy()
                del temp_score[temp_score.index(t)]
                del copy_score[copy_score.index(t)]
                cand.append(t[0]*t[1] + t[2] + Calc(temp_score, num - t[1]))
            if len(copy_score) > 0:
                cand.append(copy_score[-1][0] * num)
        return max(cand)

    

for i in range(1, q_sum+1):
    res = Calc(Score, i)
    if res >= G:
        print(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil
d, g = map(int, input().split())
P = {}
C = {}
for i in range(1,d+1):
    p, c = map(int, input().split())
    P[i] = p
    C[i] = c

# S問題でiから始めてh点取る時の必要問題数
# 例: S = [1, 2, 5]
def solve(h, i, S):
    # コンプせずにいけるとき
    if h <= 100*i*(P[i]-1):
        return ceil(h/(100*i))
    # コンプでいけるとき
    elif h <= 100*i*P[i]+C[i]:
        return P[i]
    # 足りないとき
    else:
        p = P[i]
        h -= (100*i*p+C[i])
        S.remove(i)
        min_p = 100000
        for j in S:
            min_p = min(min_p, solve(h, j, S.copy()))
        p += min_p
        return p

min_p = 100000
for j in list(range(1,d+1)):
    min_p = min(min_p, solve(g, j, list(range(1,d+1))))
print(min_p)

Submission status: Time Limit Exceeded

Solution code:
import itertools

d, g = [int(i) for i in input().split()]
p_list = []
c_list = []
for i in range(d):
    p, c = [int(j) for j in input().split()]
    p_list.append(p)
    c_list.append(c)

sample = list(itertools.permutations([i for i in range(d)]))
ans_list = []
ans_pattern_dict = {}
for per in sorted(sample, reverse=True):
    idx_list = list(per)
    score = 0
    num = 0
    for k, v in ans_pattern_dict.items():
        if idx_list[:len(k)] == k:
            continue
    for index in range(len(idx_list)):
        i = idx_list[index]
        s = 100 * (i + 1)
        p = p_list[i]
        c = c_list[i]
        if score + s * p + c < g:
            score += s * p + c
            num += p
            if len(ans_list) > 0 and min(ans_list) < num:
                break
            continue
        elif score + s * p + c == g:
            num += p
            ans_list.append(num)
            index = idx_list.index(i)
            ans_pattern_dict[str(idx_list[:index+1])] = True
            break
        elif g - score < s * p:
            if (g - score) % s == 0:
                num += (g - score) // s
            else:
                num += (g - score) // s + 1
            ans_list.append(num)
            index = idx_list.index(i)
            ans_pattern_dict[str(idx_list[:index + 1])] = True
            break
        else:
            num += p
            ans_list.append(num)
            index = idx_list.index(i)
            ans_pattern_dict[str(idx_list[:index + 1])] = True
            break

print(min(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import itertools, operator
def combinations_with_replacement_counts(n, r):
    size = n + r - 1
    for indices in itertools.combinations(range(size), n-1):
        starts = [0] + [index+1 for index in indices]
        stops = indices + (size,)
        yield tuple(map(operator.sub, stops, starts))

a = input().split(' ')
d = int(a[0])
g = int(a[1])
p = []
c = []
for i in range(d):
	a = input().split(' ')
	p.append(int(a[0]))
	c.append(int(a[1]))

end = False

for i in range(1, 1001):
	if (g <= i*d*100 + sum(c)):
		for j in list(combinations_with_replacement_counts(d, i)):			
			score = 0
			go = True
			for l in range(len(j)):
				if j[l] > p[l]:
					go = False
					break
			if go == True:
				for l in range(len(j)):
					score += j[l] * 100 * (l + 1) + j[l]//p[l]*c[l]
				if score >= g:
					print (i)
					exit()

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import permutations
d,g = map(int,input().split())
x = []
for i in range(d):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
zy = [i for i in range(1,d+1)]
zyu = list(permutations(zy, d))
ans2 = 100000000000000000000000
gou = g+0
for i in zyu:
  ans = 0
  g = gou +0
  while g > 0:
    for j in i:
      if g <= 0:
        break
      dai = x[-j][0]
      if g > (d-j+1)*100*dai:
        g-= ((d-j+1)*100*dai +x[-j][1])
        ans += dai
        continue
      else:
        ans += math.ceil(g/((d-j+1)*100))
        g = 0
      g -= x[-j][1]
  ans2 = min(ans,ans2)
print(int(ans2))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def solve(d, g, pcs):
    queue = deque()
    queue.append((0, d, g, pcs, 0))
    while True:
        count, d, g, pcs, n = queue.popleft()
        #print(count, d, g, pcs)
        if g <= 0:
            return count
        if n > 0:
            p, c = pcs[n - 1]
            l = pcs.copy()
            if p == 1:
                l = pcs.copy()
                l[n - 1] = (0, 0)
                queue.append((count + 1, d, g - c - 100 * n, l, 0))
            elif p > 1:
                l = pcs.copy()
                l[n - 1] = (p - 1, c)
                queue.append((count + 1, d, g - 100 * n, l, n))
        else:
            for i in range(1, d + 1):
                p, c = pcs[i - 1]
                if p == 1:
                    l = pcs.copy()
                    l[i - 1] = (0, 0)
                    queue.append((count + 1, d, g - c - 100 * i, l, 0))
                elif p > 1:
                    l = pcs.copy()
                    l[i - 1] = (p - 1, c)
                    queue.append((count + 1, d, g - 100 * i, l, i))


if __name__ == "__main__":
    d, g = map(int, input().split())
    pcs = [tuple(int(s) for s in input().split()) for _ in range(d)]
    print(solve(d, g, pcs))

Submission status: Time Limit Exceeded

Solution code:
import itertools

d, g = [int(i) for i in input().split()]
p_list = []
c_list = []
for i in range(d):
    p, c = [int(j) for j in input().split()]
    p_list.append(p)
    c_list.append(c)

sample = list(itertools.permutations([i for i in range(d)]))
ans_list = []
for per in sorted(sample, reverse=True):
    idx_list = list(per)
    score = 0
    num = 0
    for i in idx_list:
        s = 100 * (i + 1)
        p = p_list[i]
        c = c_list[i]
        if score + s * p + c < g:
            score += s * p + c
            num += p
            if len(ans_list) > 0 and min(ans_list) < num:
                break
            continue
        elif score + s * p + c == g:
            num += p
            ans_list.append(num)
            break
        elif g - score < s * p:
            if (g - score) % s == 0:
                num += (g - score) // s
            else:
                num += (g - score) // s + 1
            ans_list.append(num)
            break
        else:
            num += p
            ans_list.append(num)
            break

print(min(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import itertools, operator
def combinations_with_replacement_counts(n, r):
    size = n + r - 1
    for indices in itertools.combinations(range(size), n-1):
        starts = [0] + [index+1 for index in indices]
        stops = indices + (size,)
        yield tuple(map(operator.sub, stops, starts))

a = input().split(' ')
d = int(a[0])
g = int(a[1])
p = []
c = []
for i in range(d):
	a = input().split(' ')
	p.append(int(a[0]))
	c.append(int(a[1]))

end = False

for i in range(1, 1001):
	for j in list(combinations_with_replacement_counts(d, i)):
		if (g > i*d*100 + sum(c)):
			break
			
		score = 0
		go = True
		for l in range(len(j)):
			if j[l] > p[l]:
				go = False
				break
		if go == True:
			for l in range(len(j)):
				score += j[l] * 100 * (l + 1) + j[l]//p[l]*c[l]
			if score >= g:
				print (i)
				exit()

Submission status: Time Limit Exceeded

Solution code:
import itertools

d, g = [int(i) for i in input().split()]
p_list = []
c_list = []
for i in range(d):
    p, c = [int(j) for j in input().split()]
    p_list.append(p)
    c_list.append(c)

sample = list(itertools.permutations([i for i in range(d)]))
ans_list = []
for per in sample:
    idx_list = list(per)
    score = 0
    num = 0
    for i in idx_list:
        s = 100 * (i + 1)
        p = p_list[i]
        c = c_list[i]
        if score + s * p + c < g:
            score += s * p + c
            num += p
            if len(ans_list) > 0 and min(ans_list) < num:
                break
            continue
        elif score + s * p + c == g:
            num += p
            ans_list.append(num)
            break
        elif g - score < s * p:
            if (g - score) % s == 0:
                num += (g - score) // s
            else:
                num += (g - score) // s + 1
            ans_list.append(num)
            break
        else:
            num += p
            ans_list.append(num)
            break

print(min(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import itertools

d, g = [int(i) for i in input().split()]
p_list = []
c_list = []
for i in range(d):
    p, c = [int(j) for j in input().split()]
    p_list.append(p)
    c_list.append(c)

sample = list(itertools.permutations([i for i in range(d)]))
ans_list = []
for per in sample:
    idx_list = list(per)
    score = 0
    num = 0
    for i in idx_list:
        s = 100 * (i + 1)
        p = p_list[i]
        c = c_list[i]
        if score + s * p + c < g:
            score += s * p + c
            num += p
            continue
        elif score + s * p + c == g:
            num += p
            ans_list.append(num)
            break
        elif g - score < s * p:
            if (g - score) % s == 0:
                num += (g - score) // s
            else:
                num += (g - score) // s + 1
            ans_list.append(num)
            break
        else:
            num += p
            ans_list.append(num)
            break

print(min(ans_list))

Submission status: Time Limit Exceeded

Solution code:
def compute_score(p, c, solved):
    score = 0
    for i, (p_i, c_i, s_i) in enumerate(zip(p, c, solved)):
        score += (i + 1) * 100 * s_i
        if p_i == s_i:
            score += c_i

    return score


if __name__ == '__main__':
    d, g = map(int, input().split())
    p = []
    c = []
    for _ in range(d):
        p_i, c_i = map(int, input().split())
        p.append(p_i)
        c.append(c_i)

    # d = 2
    # g = 700
    # p = [3, 5]
    # c = [500, 800]

    # d = 5
    # g = 25000
    # p = [20, 40, 50, 30, 1]
    # c = [1000, 1000, 1000, 1000, 1000]

    solved = tuple([0 for _ in range(d)])
    scores = dict()
    scores[solved] = 0

    min_n_solved = 10 * 100
    next_solved_set = {solved}
    while True:
        solved = next_solved_set.pop()

        for i in range(d):
            # complete i-th problems
            if solved[i] == p[i]:
                continue

            next_solved = list(solved)
            next_solved[i] += 1
            next_solved = tuple(next_solved)

            if next_solved in scores:
                continue

            next_score = compute_score(p, c, next_solved)
            if g <= next_score:
                min_n_solved = min(min_n_solved, sum(next_solved))
                continue

            scores[next_solved] = next_score
            next_solved_set.add(next_solved)

        if len(next_solved_set) == 0:
            break

    print(min_n_solved)

Submission status: Time Limit Exceeded

Solution code:

import copy
import sys

sys.setrecursionlimit(10000000)
d, g = map(int, input().split())

scores = {}

for i in range(d):
    p, c = map(int, input().split())
    scores[i] = {
        'num' : p,
        'comp': c
    }



ans = 10000
def calc(scoreList, currentScore, ct):
    global ans, g
    # print("currentScore %d , %d " % (currentScore, ct))
    if currentScore >= g:
        if ct < ans:
            ans = ct
            # print("ok")
            # print(ans)
        return

    for i in range(d):
        score = scoreList[i]
        tempScore = currentScore
        if score['num'] == 0: continue

        tempScore += (i+1) * 100
        if score['num'] == 1:
            tempScore += score['comp']
        tempScoreList = copy.deepcopy(scoreList)
        tempScoreList[i]['num'] -= 1
        calc(tempScoreList, tempScore, ct+1)

calc(scores, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

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

import math
m = {}
def f(cur, n, pc, left):
    if left <= 0:
        return n
    def g(cur, n, pc, left):
        fp = (cur, left)
        if fp in m: return m[fp]
        m[fp] = f(cur, n, pc, left)
        return m[fp]
    ret = 10**9
    for x in pc:
        i, p, c = x
        if i*100*p > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            nc = cur.copy()
            nc.add(i)
            npc = pc.copy()
            npc.remove(x)
            h = f(nc, n + p, npc, max(0, left - i*100*p - c))
            ret = min(ret, h)
    return ret

print(f(set(), 0, pc, G))

Submission status: Time Limit Exceeded

Solution code:
import itertools

d, g = [int(i) for i in input().split()]
p_list = []
c_list = []
for i in range(d):
    p, c = [int(j) for j in input().split()]
    p_list.append(p)
    c_list.append(c)

sample = list(itertools.permutations(set([str(i) for i in range(d)])))
ans_list = []
for per in sample:
    idx_list = list(per)
    score = 0
    num = 0
    for idx in idx_list:
        i = int(idx)
        s = 100 * (i + 1)
        p = p_list[i]
        c = c_list[i]
        if score + s * p + c < g:
            score += s * p + c
            num += p
            continue
        elif score + s * p + c == g:
            num += p
            ans_list.append(num)
            break
        elif g - score < s * p:
            if (g - score) % s == 0:
                num += (g - score) // s
            else:
                num += (g - score) // s + 1
            ans_list.append(num)
            break
        else:
            score += s * p + c
            num += p
            ans_list.append(num)
            break

print(min(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import heapq

D,G=map(int,raw_input().split())

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

dat=[]

for p,c in P:
	dat.append( range(p+1) )


L=list(itertools.product(*dat))

S=[]

for u in L:
	cnt=sum(u)
	score=0
	for idx,x in enumerate(u):
		score+=(idx+1)*100*x
		if x==P[idx][0]:
			score+=P[idx][1]  #bonus
	S.append( (cnt, score ) )


S2= filter(lambda x:x[1] >=G, S) 
heapq.heapify(S2)

v=heapq.heappop(S2)
print v[0]

Submission status: Time Limit Exceeded

Solution code:
import itertools, operator
def combinations_with_replacement_counts(n, r):
    size = n + r - 1
    for indices in itertools.combinations(range(size), n-1):
        starts = [0] + [index+1 for index in indices]
        stops = indices + (size,)
        yield tuple(map(operator.sub, stops, starts))

a = input().split(' ')
d = int(a[0])
g = int(a[1])
p = []
c = []
for i in range(d):
	a = input().split(' ')
	p.append(int(a[0]))
	c.append(int(a[1]))

end = False

for i in range(1, 1001):
	for j in list(combinations_with_replacement_counts(d, i)):
		score = 0
		go = True
		for l in range(len(j)):
			if j[l] > p[l]:
				go = False
				break
		if go == True:
			for l in range(len(j)):
				score += j[l] * 100 * (l + 1) + j[l]//p[l]*c[l]
			if score >= g:
				print (i)
				exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
d, g = list(map(int, input().split()))
pc = [list(map(int, input().split())) for _ in range(d)]

dp = defaultdict(int)
dp[0] = 0
for i, (p, c) in enumerate(pc):
    dp_cur = list(dp.items())
    for p_cur, n_cur in dp_cur:
        for n in range(1, p+1):
            if n < p:
                if dp[p_cur+n*100*(i+1)] == 0:
                    dp[p_cur+n*100*(i+1)] = n_cur+n
                else:
                    dp[p_cur+n*100*(i+1)] = min(dp[p_cur+n*100*(i+1)], n_cur+n)
                if p_cur+n*100*(i+1) > g:
                    break
            else:
                if dp[p_cur+n*100*(i+1)+c] == 0:
                    dp[p_cur+n*100*(i+1)+c] = n_cur+n
                else:
                    dp[p_cur+n*100*(i+1)+c] = min(dp[p_cur+n*100*(i+1)+c], n_cur+n)

# print(dp)
ans = 10**9
v = 0
for p, n in list(dp.items()):
    if p < g:
        continue
    else:
        ans = min(ans, n)
print(ans)