Problem: 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?

Submission attempts (in order):
# -*- coding: utf-8 -*-
import itertools

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

pi = []
ci = []
score_i_c = []
score_i_h = []
for i in range(D):
    p_t, c_t = map(int, input().split())
    pi.append(p_t)
    ci.append(c_t)
    tmp = p_t * 100 * (i + 1) + c_t
    score_i_c.append((i,tmp,p_t))
    tmp = (p_t - 1) * 100 * (i + 1)
    score_i_h.append((i,tmp,p_t))


step1_list = []
for i,score,num in score_i_h:
    if score >= G:
        step1_list.append((i,score,num))

sum_list = []
if len(step1_list) > 0:
    min_i , _, _ = step1_list[-1]
    for i , score, num in step1_list:
        tmp_score = 0
        tmp_num = 0
        for i in range(pi[min_i]):
            if tmp_score >= G:
                break
            else:
                tmp_score += (min_i+1) * 100
                tmp_num  += 1
        sum_list.append(tmp_num)
    print(min(sum_list))
    exit()


step1_list = []
for i in range(D):
    tmp = itertools.combinations(score_i_c, i+1)
    step1_list.extend(list(tmp))


sum_list = []
for l in step1_list:
    numbers = []
    sum_score = 0
    sum_num = 0
    for i,score,num in l:
        numbers.append(i)
        sum_score += score
        sum_num += num

    if sum_score >= G:
        sum_list.append((numbers,sum_score,sum_num))
#
# print(step1_list)
# print(sum_list)

min_numbers = []
min_score = 0
min_num = 10000
for i,score,num in sum_list:
    if num < min_num:
        min_numbers = i
        min_score = score
        min_num = num

# print(min_numbers,min_score,min_num)

ans_list = []
# min_i = min_numbers[-1]
for min_i in min_numbers:
    tmp_score = min_score - score_i_c[min_i][1]
    tmp_num = min_num - score_i_c[min_i][2]

    for i in range(pi[min_i]):
        if tmp_score >= G:
            break
        else:
            tmp_score += (min_i+1) * 100
            tmp_num  += 1

    ans_list.append(tmp_num)

# print(ans_list)

print(min(ans_list))


# -*- coding: utf-8 -*-
import itertools

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

pi = []
ci = []
score_i_c = []
score_i_h = []
for i in range(D):
    p_t, c_t = map(int, input().split())
    pi.append(p_t)
    ci.append(c_t)
    tmp = p_t * 100 * (i + 1) + c_t
    score_i_c.append((i,tmp,p_t))
    tmp = (p_t - 1) * 100 * (i + 1)
    score_i_h.append((i,tmp,p_t))


step1_list = []
for i,score,num in score_i_h:
    if score >= G:
        step1_list.append((i,score,num))

if len(step1_list) > 0:
    min_i , _, _ = step1_list[-1]

    tmp_score = 0
    tmp_num = 0
    for i in range(pi[min_i]):
        if tmp_score >= G:
            break
        else:
            tmp_score += (min_i+1) * 100
            tmp_num  += 1

    print(tmp_num)
    exit()


step1_list = []
for i in range(D):
    tmp = itertools.combinations(score_i_c, i+1)
    step1_list.extend(list(tmp))

sum_list = []
for l in step1_list:
    numbers = []
    sum_score = 0
    sum_num = 0
    for i,score,num in l:
        numbers.append(i)
        sum_score += score
        sum_num += num

    if sum_score >= G:
        sum_list.append((numbers,sum_score,sum_num))
#
# print(step1_list)
# print(sum_list)

min_numbers = []
min_score = 0
min_num = 10000
for i,score,num in sum_list:
    if num < min_num:
        min_numbers = i
        min_score = score
        min_num = num

# print(min_numbers,min_score,min_num)

ans_list = []
# min_i = min_numbers[-1]
for min_i in min_numbers:
    tmp_score = min_score - score_i_c[min_i][1]
    tmp_num = min_num - score_i_c[min_i][2]

    for i in range(pi[min_i]):
        if tmp_score >= G:
            break
        else:
            tmp_score += (min_i+1) * 100
            tmp_num  += 1

    ans_list.append(tmp_num)

# print(ans_list)

print(min(ans_list))


# -*- coding: utf-8 -*-
import itertools

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

pi = []
ci = []
score_i_c = []
score_i_h = []
for i in range(D):
    p_t, c_t = map(int, input().split())
    pi.append(p_t)
    ci.append(c_t)
    tmp = p_t * 100 * (i + 1) + c_t
    score_i_c.append((i,tmp,p_t))
    tmp = (p_t - 1) * 100 * (i + 1)
    score_i_h.append((i,tmp,p_t))


step1_list = []
for i,score,num in score_i_h:
    if score >= G:
        step1_list.append((i,score,num))

ans_list = []
if len(step1_list) > 0:
    min_i , _, _ = step1_list[-1]
    for i , score, num in step1_list:
        tmp_score = 0
        tmp_num = 0
        for i in range(pi[min_i]):
            if tmp_score >= G:
                break
            else:
                tmp_score += (min_i+1) * 100
                tmp_num  += 1
        ans_list.append(tmp_num)


step1_list = []
for i in range(D):
    tmp = itertools.combinations(score_i_c, i+1)
    step1_list.extend(list(tmp))


sum_list = []
for l in step1_list:
    numbers = []
    sum_score = 0
    sum_num = 0
    for i,score,num in l:
        numbers.append(i)
        sum_score += score
        sum_num += num

    if sum_score >= G:
        sum_list.append((numbers,sum_score,sum_num))
#
# print(step1_list)
# print(sum_list)

# min_numbers = []
# min_score = 0

# for i,score,num in sum_list:

#         min_numbers = i
#         min_score = score


# print(min_numbers,min_score,min_num)

# min_i = min_numbers[-1]
for min_numbers,min_score,min_num in sum_list:
    for min_i in min_numbers:
        tmp_score = min_score - score_i_c[min_i][1]
        tmp_num = min_num - score_i_c[min_i][2]

        for i in range(pi[min_i]):
            if tmp_score >= G:
                break
            tmp_score += (min_i+1) * 100
            tmp_num  += 1

        ans_list.append(tmp_num)

# print(ans_list)

print(min(ans_list))


Verdicts: Wrong Answer

Wrong Answer

Accepted