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 math
length, goal = map(int, input().split(" "))
problems, bonus = [], []
for i in range(length):
    a, b = map(int, input().split(" "))
    problems.append(a)
    bonus.append(b)
problems = problems[::-1]
bonus = bonus[::-1]
answer = float("inf")
for bit in range(length ** 2):
    temp_ans = 0
    temp_sum = 0
    for i in range(length):
        temp_score = (length - i) * 100
        if bit & (1 << i):
            temp_ans += problems[i]
            temp_sum += bonus[i] + temp_score * problems[i]
    print(bit, temp_ans, temp_sum)
    if temp_sum >= goal:
        answer = min(answer, temp_ans)
    else:
        for i in range(length):
            temp_score = (length - i) * 100
            if not(bit & (1 << i)):
                if temp_score * (problems[i] - 1) + temp_sum >= goal:
                    temp_ans += int(math.ceil((goal - temp_sum) / temp_score))
                    print(math.ceil((goal - temp_sum) / temp_score))
                    answer = min(answer, temp_ans)
                    break
                else:
                    temp_ans += problems[i] - 1
                    temp_sum += temp_score * (problems[i] - 1)
        if temp_sum >= goal:
            answer = min(answer, temp_ans)
print(answer)

import math
length, goal = map(int, input().split(" "))
problems, bonus = [], []
for i in range(length):
    a, b = map(int, input().split(" "))
    problems.append(a)
    bonus.append(b)
problems = problems[::-1]
bonus = bonus[::-1]
answer = float("inf")
for bit in range(length ** 2):
    temp_ans = 0
    temp_sum = 0
    for i in range(length):
        temp_score = (length - i) * 100
        if bit & (1 << i):
            temp_ans += problems[i]
            temp_sum += bonus[i] + temp_score * problems[i]
    print(bit, temp_ans, temp_sum)
    if temp_sum >= goal:
        answer = min(answer, temp_ans)
    else:
        for i in range(length):
            temp_score = (length - i) * 100
            if not(bit & (1 << i)):
                if temp_score * (problems[i] - 1) + temp_sum >= goal:
                    temp_ans += int(math.ceil((goal - temp_sum) / temp_score))
                    
                    answer = min(answer, temp_ans)
                    break
                else:
                    temp_ans += problems[i] - 1
                    temp_sum += temp_score * (problems[i] - 1)
        if temp_sum >= goal:
            answer = min(answer, temp_ans)
print(answer)

import math
length, goal = map(int, input().split(" "))
nums = []
sumall = []
for i in range(length):
    a, b = map(int, input().split(" "))
    nums.append(a)
    sumall.append(a * (i + 1) * 100 + b)
answer = float("inf")
for bit in range(2 ** length):
    temp = []
    for i in range(length - 1, -1, -1):
        if bit & (1 << i):
            temp.append(i)
    temp_length = len(temp)
    for tempbit in range(2 ** temp_length):
        temp_sum = 0
        choosed = 0
        for i in range(temp_length):
            if tempbit & (1 << i):
                temp_sum += sumall[temp[i]]
                choosed += nums[temp[i]]
                if temp_sum >= goal:
                    answer = min(answer, choosed)
                    break
            else:
                if temp_sum + (nums[temp[i]] - 1) * (temp[i] + 1) * 100 >= goal:
                    answer = min(answer, choosed + int(math.ceil((goal - temp_sum) / (100 * (temp[i] + 1)))) )
                    break
                temp_sum += (nums[temp[i]] - 1) * (temp[i] + 1) * 100
                choosed += nums[temp[i]] - 1
        # print(bin(bit), bin(tempbit), temp_sum, choosed, answer)
    # print(answer, bin(bit))
print(answer)


Verdicts: Wrong Answer

Wrong Answer

Accepted