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):
import sys

sys_input = sys.stdin.readline

D, G = map(int, sys_input().split())
pc_list = [tuple(map(int, sys_input().split())) for _ in range(D)]

# WIP
temp_min_score = 10000000000000000
combi_min = []
n_solved = 10000000000
for i in range(1 << D):
    score_per_combi = 0
    combi = []
    tmp_n_solved = 0
    
    for j in range(D):
        if (i >> j) & 1:
            p = pc_list[j][0]
            c = pc_list[j][1]
            score_per_combi += (j + 1) * 100 * p + c
            combi.append(j)
            tmp_n_solved += p
    if tmp_n_solved == 0:
        continue
    if score_per_combi >= G and tmp_n_solved < n_solved:
        temp_min_score = score_per_combi
        combi_min = combi
        n_solved = tmp_n_solved

# problems are already sorted
# -> check the problems were oversolved
tmp_reduced = temp_min_score
for problem_idx in combi_min:
    for solved_num in range(pc_list[problem_idx][0]):
        if solved_num == 1:
            c = pc_list[problem_idx][1]
            diff = (problem_idx + 1) * 100 + c
            tmp_reduced -= diff
        else:
            diff = (problem_idx + 1) * 100
            tmp_reduced -= diff
        n_solved -= 1
        
        if tmp_reduced < G:
            print(n_solved + 1)
            exit()

print(n_solved)


import sys

sys_input = sys.stdin.readline

D, G = map(int, sys_input().split())
pc_list = [tuple(map(int, sys_input().split())) for _ in range(D)]

n_solved = 10000000000
for i in range(1 << D):
    score_per_combi = 0
    combi = []
    tmp_n_solved = 0

    for j in range(D):
        if (i >> j) & 1:
            p = pc_list[j][0]
            c = pc_list[j][1]
            score_per_combi += (j + 1) * 100 * p + c
            combi.append(j)
            tmp_n_solved += p

    if tmp_n_solved == 0:
        continue
    if score_per_combi < G:
        continue

    # problems are already sorted
    # -> check if these were oversolved
    for problem_idx in combi:
        for solved_num in range(pc_list[problem_idx][0]):
            diff = None
            if solved_num == 1:
                c = pc_list[problem_idx][1]
                diff = (problem_idx + 1) * 100 + c
                score_per_combi -= diff
            else:
                diff = (problem_idx + 1) * 100
                score_per_combi -= diff
            tmp_n_solved -= 1

            if score_per_combi < G:
                tmp_n_solved += 1
                score_per_combi += diff
                break
            
            else:
                continue
            
            break

    # Check if mininum n_solved are updated
    if tmp_n_solved < n_solved:
        n_solved = tmp_n_solved

print(n_solved)


# AC
import math

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

min_n_solved = 1000000000
for p_combi in range(1 << D):
    tmp_score = 0
    n_solved = 0
    selected_p_idxs = []  # Selected indexes of problems
    for digit in range(D):
        if (p_combi >> digit) & 1:
            
            
            tmp_score += \
                100 * (digit+1) * p_c_list[digit][0] + p_c_list[digit][1]
            n_solved += p_c_list[digit][0]
            selected_p_idxs.append(digit)
    score_diff = tmp_score - G
    # print('1:', n_solved, 'score_diff:', score_diff)
    if score_diff >= 0:
        # Fine-tuning to reduce "n_solved" problems over solved
        # "selected_p_idxs" were already sorted by probrems
        # from low points to high
        p_idx_lowest = selected_p_idxs[0]
        score_per_p = 100 * (p_idx_lowest + 1)
        # if score_diff - bonus_point > 0
        n_oversolved = None
        score_diff_wo_bonus = score_diff - p_c_list[p_idx_lowest][1]
        if score_diff_wo_bonus > 0:
            n_oversolved = round(score_diff_wo_bonus / score_per_p)
            if n_oversolved < p_c_list[p_idx_lowest][0]:
                n_solved -= n_oversolved
        # print('2:', n_solved)
    else:
        not_selected_p_idxs = \
            [p_idx for p_idx in range(D) if p_idx not in selected_p_idxs]
        not_selected_p_idxs = sorted(not_selected_p_idxs, reverse=True)
        # Select a problem index
        # which have highest point in not_selected_p_idxes
        not_selected_p_idx_highest = not_selected_p_idxs[0]
        num_p = p_c_list[not_selected_p_idx_highest][0]
        addable_score = \
            100 * num_p * (not_selected_p_idx_highest + 1)
        if score_diff + addable_score > 0:
            score_per_p = 100 * (not_selected_p_idx_highest + 1)
            n_undersolved = math.ceil(abs(score_diff) / score_per_p)
            if n_undersolved < num_p:
                n_solved += n_undersolved
            # print('3:', n_solved)
    if n_solved > 0 and score_diff >= 0:
        min_n_solved = min(n_solved, min_n_solved)

print(min_n_solved)

Verdicts: Wrong Answer

Wrong Answer

Accepted