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:
import numpy as np

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)

cnt = np.zeros(D,dtype=int)
P = np.array(P)
C = np.array(C)

ans = sum(P)
cnt_tar = 0

ind_list = np.arange(D)

if D == 10:
    for i in range(D):
        tar = i

        ind_list = list(range(D))
        ind_list.remove(tar)
        ind_list = np.array(ind_list)

        P_part = np.hstack((P[:tar], P[tar+1:]))
        C_part = np.hstack((C[:tar], C[tar+1:]))

        cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
        point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

        bit_list = np.ones(D-1,dtype=int)
        point_part_max = np.sum(((ind_list+1) * 100 * P_part + C_part)*bit_list)

        cnt_tar_min = max(0,(G - point_part_max)//((tar+1)*100))

        if cnt_tar_min > P[tar]:
            continue
        for cnt_tar in range(cnt_tar_min,P[tar]+1):
            point_base = cnt_tar*(tar+1)*100

            num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

            if point_base >= G or num_base >= ans:
                num = num_base
                ans = min(ans,num)
                break
            elif point_base + point_part_max >= G:

                for bit_seed in range(2**(D-1)):

                    s_bit = (format(bit_seed, '#011b'))[::-1]
                    bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                    cnt_part = P_part*bit_list
                    num = num_base + np.sum(cnt_part)
                    if num > ans:
                        continue

                    point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list
                    point = point_base + np.sum(point_part)

                    if point >= G:
                        ans = min(ans,num)

    print(ans)
    exit()

for bit_seed in range(2**D):

    s_bit = (format(bit_seed, '#016b'))[::-1]
    bit_list = np.array(list(s_bit[:D]),dtype=int)

    cnt = P*bit_list
    num_base = np.sum(cnt)

    point_base_array = (P * (ind_list+1) * 100 + C) * bit_list
    point_base = np.sum(point_base_array)
#    print(point_base_array)

    if point_base >= G:
        num = num_base
        ans = min(ans,num)
    elif num_base > ans:
        continue
    else:
        for i,bit in enumerate(bit_list):
            if bit == 0:
                tar = i

        point_max = point_base + P[tar]*(tar+1)*100 + C[tar]
        if point_max >= G:

            tar_min = (G-point_base) // ((tar+1)*100)
            point = point_base + P[tar]*(tar+1)*100

            if point < G:
                tar_min += 1

            if tar_min < P[tar]:
                num = num_base + tar_min
            else:
                num = num_base + P[tar]
            ans = min(ans,num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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)

cnt = [0 for _ in range(D)]

ans = sum(P)
cnt_tar = 0

for i in range(D):
    tar = i

    ind_list = list(range(D))
    ind_list.remove(tar)
    ind_list = np.array(ind_list)

    P_part = np.array(P[:tar] + P[tar+1:])
    C_part = np.array(C[:tar] + C[tar+1:])

    cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
    point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

    bit_list = np.ones(D-1,dtype=int)
    point_part_max = np.sum(((ind_list+1) * 100 * P_part + C_part)*bit_list)

    for cnt_tar in range(P[tar]+1):
        point_base = cnt_tar*(tar+1)*100

        num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

        if point_base >= G or num_base >= ans:
            num = num_base
            ans = min(ans,num)
            break
        elif point_base + point_part_max >= G:

            for bit_seed in range(2**(D-1)):

                s_bit = (format(bit_seed, '#011b'))[::-1]
                bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                cnt_part = P_part*bit_list
                point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list

                num = num_base + np.sum(cnt_part)
                point = point_base + np.sum(point_part)

                if point >= G:
                    ans = min(ans,num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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)

cnt = [0 for _ in range(D)]

ans = sum(P)
cnt_tar = 0

for i in range(D):
    tar = i

    ind_list = list(range(D))
    ind_list.remove(tar)
    ind_list = np.array(ind_list)

    P_part = np.array(P[:tar] + P[tar+1:])
    C_part = np.array(C[:tar] + C[tar+1:])

    cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
    point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

    for cnt_tar in range(P[tar]+1):
        point_base = cnt_tar*(tar+1)*100

        num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

        if point_base >= G or num_base >= ans:
            num = num_base
            ans = min(ans,num)
            break
        else:

            bit_seeds = list(range(2**(D-1)))
            bit_seeds = bit_seeds[::-1]

            for bit_seed in bit_seeds:

                s_bit = (format(bit_seed, '#011b'))[::-1]
                bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                cnt_part = P_part*bit_list
                point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list

                num = num_base + np.sum(cnt_part)
                point = point_base + np.sum(point_part)

                if point >= G:
                    ans = min(ans,num)

                elif bit_seed == bit_seeds[0]:
                    break

print(ans)
#     while cnt_part != P_part:
#     ind = 0

#     cnt = kuriage(cnt,P,ind,tar,C,G)
#     print(cnt)
#     if cnt[tar] == -1:
#         cnt = [0 for _ in range(D)]
#         tar += 1

#     if point_over(cnt,P,C,G) and ans > sum(cnt):
#         ans = min(ans, sum(cnt))
# #            print(ans)

# print(ans)


# def kuriage(cnt,P,ind,tar,C,G):

#     if cnt[ind] == 0:
#         cnt[ind:ind+1] = P[ind:ind+1]
#     elif cnt[ind] == P[ind]:
#         if 0 in cnt[:tar] and 0 in cnt[tar+1:]:
#             if ind+1 == tar:
#                 kuriage(cnt,P,ind+2, tar, C, G)
#             else:
#                 kuriage(cnt,P,ind+1, tar, C, G)
#         else:
#             if C[tar] != P[tar]:
#                 C[tar] = C[tar] + 1
#             else:
#                 C[tar] = -1
#     return cnt
# def point_over(cnt,P,C,G):
#     point = 0
#     for i in range(len(P)):
#         point += cnt[i]*100*(i+1)
#         if cnt[i] == P[i]:
#             point += C[i]

#         if point >= G:
#             return True

#     if point < G:
#         return False

# def point(cnt,P,C):
#     point = 0

#     for i,cnt_s in enumerate(cnt):
#         print(cnt_s,'ok')
#         if cnt_s == 0:
#             point += 0
#         else:
#             point += cnt[i]*100*(i+1) + C[i]
#     return point

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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)

cnt = [0 for _ in range(D)]

ans = sum(P)
cnt_tar = 0

for i in range(D):
    tar = i

    ind_list = list(range(D))
    ind_list.remove(tar)
    ind_list = np.array(ind_list)

    P_part = np.array(P[:tar] + P[tar+1:])
    C_part = np.array(C[:tar] + C[tar+1:])

    cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
    point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

    for cnt_tar in range(P[tar]+1):
        point_base = cnt_tar*(tar+1)*100

        num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

        if point_base >= G:
            num = num_base
            ans = min(ans,num)
            break
        else:
            bit_seeds = list(range(2**(D-1)))
            bit_seeds = bit_seeds[::-1]

            for bit_seed in bit_seeds:

                s_bit = (format(bit_seed, '#011b'))[::-1]
                bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                cnt_part = P_part*bit_list
                point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list

                # for j in range(D-1):
                #     bit = int(s_bit[j:j+1])
                #     cnt_part[j]   = (P_part[j])*bit
                #     point_part[j] = (P_part[j]*(P.index(P_part[j])+1)*100 + C_part[j])*bit
                # print(cnt_part)

                num = num_base + np.sum(cnt_part)
                point = point_base + np.sum(point_part)

                if point >= G:
                    ans = min(ans,num)

                elif bit_seed == bit_seeds[0]:
                    break

print(ans)
#     while cnt_part != P_part:
#     ind = 0

#     cnt = kuriage(cnt,P,ind,tar,C,G)
#     print(cnt)
#     if cnt[tar] == -1:
#         cnt = [0 for _ in range(D)]
#         tar += 1

#     if point_over(cnt,P,C,G) and ans > sum(cnt):
#         ans = min(ans, sum(cnt))
# #            print(ans)

# print(ans)


# def kuriage(cnt,P,ind,tar,C,G):

#     if cnt[ind] == 0:
#         cnt[ind:ind+1] = P[ind:ind+1]
#     elif cnt[ind] == P[ind]:
#         if 0 in cnt[:tar] and 0 in cnt[tar+1:]:
#             if ind+1 == tar:
#                 kuriage(cnt,P,ind+2, tar, C, G)
#             else:
#                 kuriage(cnt,P,ind+1, tar, C, G)
#         else:
#             if C[tar] != P[tar]:
#                 C[tar] = C[tar] + 1
#             else:
#                 C[tar] = -1
#     return cnt
# def point_over(cnt,P,C,G):
#     point = 0
#     for i in range(len(P)):
#         point += cnt[i]*100*(i+1)
#         if cnt[i] == P[i]:
#             point += C[i]

#         if point >= G:
#             return True

#     if point < G:
#         return False

# def point(cnt,P,C):
#     point = 0

#     for i,cnt_s in enumerate(cnt):
#         print(cnt_s,'ok')
#         if cnt_s == 0:
#             point += 0
#         else:
#             point += cnt[i]*100*(i+1) + C[i]
#     return point

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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)

cnt = [0 for _ in range(D)]

ans = sum(P)
cnt_tar = 0

for i in range(D):
    tar = i

    ind_list = list(range(D))
    ind_list.remove(tar)
    ind_list = np.array(ind_list)

    P_part = np.array(P[:tar] + P[tar+1:])
    C_part = np.array(C[:tar] + C[tar+1:])

    cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
    point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

    for cnt_tar in range(P[tar]+1):
        point_base = cnt_tar*(tar+1)*100

        num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

        if point_base >= G:
            num = num_base
            ans = min(ans,num)
            break
        else:
            for bit_seed in range(2**(D-1)):

                s_bit = (format(bit_seed, '#011b'))[::-1]
                bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                cnt_part = P_part*bit_list
                point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list

                # for j in range(D-1):
                #     bit = int(s_bit[j:j+1])
                #     cnt_part[j]   = (P_part[j])*bit
                #     point_part[j] = (P_part[j]*(P.index(P_part[j])+1)*100 + C_part[j])*bit
                # print(cnt_part)

                num = num_base + sum(cnt_part)
                point = point_base + sum(point_part)
#                print(cnt_tar,cnt_part,point)
                if point >= G:
                    # print('point = ',point,'/',G)
                    # print(num)
                    ans = min(ans,num)

print(ans)

Submission status: Time Limit Exceeded

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)

cnt = [0 for _ in range(D)]

ans = sum(P)
cnt_tar = 0

for i in range(D):
    tar = i

    P_part = P[:tar] + P[tar+1:]
    C_part = C[:tar] + C[tar+1:]

    cnt_part = [0 for _ in range(D-1)]
    point_part = [0 for _ in range(D-1)]

    for cnt_tar in range(P[tar]+1):
        point_base = cnt_tar*(tar+1)*100

        num_base   = cnt_tar
        if cnt_tar == P[tar]:
            point_base += C[tar]

        if True:
#            print('point_base = ',point_base,)
            for bit_seed in range(2**(D-1)):

                s_bit = (format(bit_seed, '#011b'))[::-1]

                for j in range(D-1):
                    bit = int(s_bit[j:j+1])
                    cnt_part[j]   = (P_part[j])*bit
                    point_part[j] = (P_part[j]*(P.index(P_part[j])+1)*100 + C_part[j])*bit

                num = num_base + sum(cnt_part)
                point = point_base + sum(point_part)
#                print(cnt_tar,cnt_part,point)
                if point >= G:
                    # print('point = ',point,'/',G)
                    # print(num)
                    ans = min(ans,num)
        if point_base >= G:
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def kuriage(cnt,P,ind,tar,C,G):

    if cnt[ind] == 0:
        cnt[ind:ind+1] = P[ind:ind+1]
    elif cnt[ind] == P[ind]:
        if 0 in cnt[:tar] and 0 in cnt[tar+1:]:
            if ind+1 == tar:
                kuriage(cnt,P,ind+2, tar, C, G)
            else:
                kuriage(cnt,P,ind+1, tar, C, G)
        else:
            if C[tar] != P[tar]:
                C[tar] = C[tar] + 1
            else:
                C[tar] = -1
    return cnt
def point_over(cnt,P,C,G):
    point = 0
    for i in range(len(P)):
        point += cnt[i]*100*(i+1)
        if cnt[i] == P[i]:
            point += C[i]

        if point >= G:
            return True

    if point < G:
        return False

def point(cnt,P,C):
    point = 0

    for i,cnt_s in enumerate(cnt):
        print(cnt_s,'ok')
        if cnt_s == 0:
            point += 0
        else:
            point += cnt[i]*100*(i+1) + C[i]
    return point

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)

cnt = [0 for _ in range(D)]

ans = sum(P)
cnt_tar = 0

for i in range(D):
    tar = i

    P_part = P[:tar] + P[tar+1:]
    C_part = C[:tar] + C[tar+1:]

    cnt_part = [0 for _ in range(D-1)]
    point_part = [0 for _ in range(D-1)]

    for cnt_tar in range(P[tar]+1):
        point_base = cnt_tar*(tar+1)*100

        num_base   = cnt_tar
        if cnt_tar == P[tar]:
            point_base += C[tar]

        if True:
#            print('point_base = ',point_base,)
            for bit_seed in range(2**(D-1)):

                s_bit = (format(bit_seed, '#011b'))[::-1]

                for j in range(D-1):
                    bit = int(s_bit[j:j+1])
                    cnt_part[j]   = (P_part[j])*bit
                    point_part[j] = (P_part[j]*(P.index(P_part[j])+1)*100 + C_part[j])*bit

                num = num_base + sum(cnt_part)
                point = point_base + sum(point_part)
#                print(cnt_tar,cnt_part,point)
                if point >= G:
                    # print('point = ',point,'/',G)
                    # print(num)
                    ans = min(ans,num)

print(ans)
#     while cnt_part != P_part:
#     ind = 0

#     cnt = kuriage(cnt,P,ind,tar,C,G)
#     print(cnt)
#     if cnt[tar] == -1:
#         cnt = [0 for _ in range(D)]
#         tar += 1

#     if point_over(cnt,P,C,G) and ans > sum(cnt):
#         ans = min(ans, sum(cnt))
# #            print(ans)

# print(ans)

Submission status: Time Limit Exceeded

Solution code:
def kuriage(cnt,P,ind,C,G):
    if cnt[ind] < P[ind]:
        if point(cnt,P,C,G) + (P[ind] - cnt[ind]) * (ind+1) * 100 + C[i] < G:
            cnt[ind:ind+1] = P[ind:ind+1]
        else:
            cnt[ind] = cnt[ind] + 1
        return cnt
    else:#cnt[ind] == P[ind]
        cnt[ind] = 0
        return kuriage(cnt, P, ind+1, C, G)

def point_over(cnt,P,C,G):
    point = 0
    for i in range(len(P)):
        point += cnt[i]*100*(i+1)
        if cnt[i] == P[i]:
            point += C[i]

        if point >= G:
            return True

    if point < G:
        return False

def point(cnt,P,C,G):
    point = 0
    for i in range(len(P)):
        point += cnt[i]*100*(i+1)
        if cnt[i] == P[i]:
            point += C[i]

    return point

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)

cnt = [0 for _ in range(D)]

ans = sum(P)
while cnt != P:
    ind = 0
    cnt = kuriage(cnt,P,ind,C,G)
#    print(cnt,sum(cnt),point(cnt,P,C,G)-25000)

    if point_over(cnt,P,C,G) and ans > sum(cnt):
        ans = min(ans, sum(cnt))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dfs(i,total_p,total_q):
    if total_q >= min(ans):
        return

    if total_p >= g:
        ans.append(total_q)
        return

    if i == d:
        return

    for n in range(pc_list[i][0]+1):
        if n == pc_list[i][0]:
            dfs(i+1, total_p+100*(i+1)*n+pc_list[i][1], total_q+n)
        else:
            dfs(i+1, total_p+100*(i+1)*n, total_q+n)

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

dfs(0,0,0)
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
n,g = map(int,input().split())
lis = []
mon = []
for i in range(n):
  a,b = map(int,input().split())
  lis.append([a,b])
score = {(0,0)}
for i in range(n):
  gone = set()
  for nu,cou in score:
    for j in range(lis[i][0]+1):
      if j != lis[i][0]:
        gone.add((nu+(i+1) * 100 * j,cou + j))
      else:
        gone.add((nu+(i+1) * 100 * j + lis[i][1],cou + j))
  score = gone
ans = 10 ** 12
for nu,num in score:
  if nu >= g:
    ans = min(ans,num)
print(ans)

Submission status: Time Limit Exceeded

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)):
    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 ls_count[i].sum() >=  min:
            continue
        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: Time Limit Exceeded

Solution code:
import itertools
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
    flag = 0
    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) and (flag == 0):
            for j in range(P[-i][0]):
                if score >= G:
                    break
                score += 100 * (D - i + 1)
                num += 1
            flag = 1
                        
    if score >= G:
        min_num = min(num, min_num)

print(min_num)

Submission status: Time Limit Exceeded

Solution code:
import itertools
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
    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: Time Limit Exceeded

Solution code:
# encoding: utf-8
D_MAX = 10
P_MAX = 100

num_and_pnt = lambda x: [int(x[0]), int(x[1]) // 100]
D, G = num_and_pnt(input().split())
# [pi, ci]
pc = [num_and_pnt(input().split()) + [i] for i in range(D)]
# pc.sort(key=lambda x: -((x[2] + 1) * x[0] + x[1]))

# depth-first-like search
G_tab = [(x[2] + 1) * x[0] + x[1] for x in pc]
cnt_tab = [x[0] for x in pc]
G_stack = G_tab[0]
cnt_stack = cnt_tab[0]
order = [0]

mincnt = D_MAX * P_MAX
while True:
    ## deepth increament (continue)
    if G_stack < G:
        # append lowest item (always break?)
        for i in range(D):
            if i not in order: break
        order.append(i)
        G_stack += G_tab[i]
        cnt_stack += cnt_tab[i]
        continue
    ## skip check
    idx_tmp = order[-1]
    G_tmp = G_stack - G_tab[idx_tmp]
    cnt_tmp = cnt_stack - cnt_tab[idx_tmp]
    if cnt_tmp < mincnt:
        ## evaluate cnt_last
        x = pc[order[-1]]
        cnt_last = x[0]
        for i in range(x[0]):
            cnt_last -= 1
            G_last = (x[2] + 1) * cnt_last
            # print("##", cnt_last, G_tmp + G_last, G)
            if G_tmp + G_last < G: break
        cnt_last += 1
        ## update mincnt
        # print("#", order, cnt_tmp, cnt_last, G - G_tmp, "/", mincnt)
        if cnt_tmp + cnt_last < mincnt: mincnt = cnt_tmp + cnt_last
    ## next node
    order_last = order[-1] + 1
    while True:
        if order_last > D - 1:
            idx_tmp = order[-1]
            G_stack -= G_tab[idx_tmp]
            cnt_stack -= cnt_tab[idx_tmp]
            order.pop()
            if len(order) < 1: break # end
            order_last = order[-1] + 1
            continue
        elif order_last in order:
            order_last = order_last + 1
            continue
        else:
            idx_tmp = order[-1]
            G_stack += (G_tab[order_last] - G_tab[idx_tmp])
            cnt_stack += (cnt_tab[order_last] - cnt_tab[idx_tmp])
            order[-1] = order_last
            break
    ## escape
    if len(order) < 1: break # end

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
D_MAX = 10
P_MAX = 100

num_and_pnt = lambda x: [int(x[0]), int(x[1]) // 100]
D, G = num_and_pnt(input().split())
# [pi, ci]
pc = [num_and_pnt(input().split()) + [i] for i in range(D)]
pc.sort(key=lambda x: -((x[2] + 1) * x[0] + x[1]))

# depth-first-like search
G_tab = [(x[2] + 1) * x[0] + x[1] for x in pc]
cnt_tab = [x[0] for x in pc]
G_stack = [G_tab[0]]
cnt_stack = [cnt_tab[0]]
order = [0]

mincnt = D_MAX * P_MAX
while True:
    ## deepth increament (continue)
    if sum(G_stack) < G:
        # append lowest item (always break?)
        for i in range(D):
            if i not in order: break
        order.append(i)
        G_stack.append(G_tab[i])
        cnt_stack.append(cnt_tab[i])
        continue
    ## skip check
    G_tmp = sum(G_stack[:-1])
    cnt_tmp = sum(cnt_stack[:-1])
    if cnt_tmp < mincnt:
        ## evaluate cnt_last
        idx = order[-1]
        x = pc[idx]
        cnt_last = x[0]
        for i in range(x[0]):
            cnt_last -= 1
            G_last = (x[2] + 1) * cnt_last
            # print("##", cnt_last, G_tmp + G_last, G)
            if G_tmp + G_last < G: break
        cnt_last += 1
        ## update mincnt
        # print("#", order, cnt_tmp, cnt_last, G - G_tmp, "/", mincnt)
        if cnt_tmp + cnt_last < mincnt: mincnt = cnt_tmp + cnt_last
    ## next node
    order_last = order[-1] + 1
    while True:
        if order_last > D - 1:
            G_stack.pop()
            cnt_stack.pop()
            order.pop()
            if len(order) < 1: break # end
            order_last = order[-1] + 1
            continue
        elif order_last in order:
            order_last = order_last + 1
            continue
        else:
            order[-1] = order_last
            G_stack[-1] = G_tab[order_last]
            cnt_stack[-1] = cnt_tab[order_last]
            break
    ## escape
    if len(order) < 1: break # end

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
D_MAX = 10
P_MAX = 100

num_and_pnt = lambda x: [int(x[0]), int(x[1]) // 100]
D, G = num_and_pnt(input().split())
# [pi, ci]
pc = [num_and_pnt(input().split()) for i in range(D)]

# depth-first-like search
G_tab = [(i + 1) * x[0] + x[1] for i, x in enumerate(pc)]
cnt_tab = [x[0] for x in pc]
G_stack = [G_tab[0]]
cnt_stack = [cnt_tab[0]]
order = [0]

mincnt = D_MAX * P_MAX
while True:
    ## deepth increament (continue)
    if sum(G_stack) < G:
        # append lowest item (always break?)
        for i in range(D):
            if i not in order: break
        order.append(i)
        G_stack.append(G_tab[i])
        cnt_stack.append(cnt_tab[i])
        continue
    ## escape
    G_tmp = sum(G_stack[:-1])
    cnt_tmp = sum(cnt_stack[:-1])
    if cnt_tmp < mincnt:
        ## evaluate cnt_last
        idx = order[-1]
        x = pc[idx]
        cnt_last = x[0]
        for i in range(x[0]):
            cnt_last -= 1
            G_last = (idx + 1) * cnt_last
            # print("##", cnt_last, G_tmp + G_last, G)
            if G_tmp + G_last < G: break
        cnt_last += 1
        ## update mincnt
        # print("#", order, cnt_tmp, cnt_last, G - G_tmp, "/", mincnt)
        if cnt_tmp + cnt_last < mincnt: mincnt = cnt_tmp + cnt_last
    ## next node
    order_last = order[-1] + 1
    while True:
        if order_last > D - 1:
            G_stack.pop()
            cnt_stack.pop()
            order.pop()
            if len(order) < 1: break # end
            order_last = order[-1] + 1
            continue
        elif order_last in order:
            order_last = order_last + 1
            continue
        else:
            order[-1] = order_last
            G_stack[-1] = G_tab[order_last]
            cnt_stack[-1] = cnt_tab[order_last]
            break
    ## escape
    if len(order) < 1: break # end

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
def after_explain():
    d, g = map(int, input().split())
    a = []
    b = []
    for i in range(d):
        p, c = map(int, input().split())
        a.append(p)
        b.append(c)

    mincnt = 999999999
    for i in range(1 << 2 * d):
        score = 0
        cnt = 0
        for j in range(d):
            if i & (1 << j):
                score += a[j]*(j+1)*100 + b[j]
                cnt += a[j]

        for j in range(d-1, -1, -1):
            if not(i & (1 << j)):
                if score > g:
                    break
                s = g - score
                if s % ((j+1)*100) == 0:
                    c = min(a[j], s // ((j + 1) * 100))
                    cnt += c
                    score += c * ((j + 1) * 100)
                else:
                    c = min(a[j], s // ((j + 1) * 100))
                    cnt += c + 1
                    score += (c+1) * ((j + 1) * 100)
                break
        if score < g:
            continue
        if cnt < mincnt:
            mincnt = cnt
    return mincnt

print(after_explain())

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 )

  score_freqs = {}
  for score, freq in ps_next:
    if score_freqs.get(score) is None:
      score_freqs[score] = []
    score_freqs[score].append( freq )

  ps_next = [[score, min(freqs)] for score, freqs in score_freqs.items()]
  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] )