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):
D,G = map(int, input().split())
PC = [tuple(map(int, input().split())) for _ in range(D)]

print(PC)


comp = [100*(i+1)*PC[i][0] + PC[i][1] for i in range(D)]



ans = sum([PC[i][0] for i in range(D)])
for bit in range(1<<D):
    
    
    point = 0
    prob = 0
    
    print("init",bit,ans,prob,point)
    
    for j in range(D-1, -1, -1):
        if bit & (1<<j):
            point += comp[j]
            prob += PC[j][0]

    
    if point >= G:
        ans = min(ans,prob)
        continue
    
    
    else:
        for j in range(D-1, -1, -1):
            if bit & (1<<j):
                continue
            else:
                if point + 100*(j+1)*(PC[j][0]-1) < G:
                    point += 100*(j+1)*(PC[j][0]-1)
                    prob += (PC[j][0]-1)
                else:
                    temp = (G-point)//(100*(j+1)) + bool((G-point)%(100*(j+1)))
                    point += 100*(j+1)*temp
                    prob += temp
        
            if point >= G:
                ans = min(ans,prob)
                break
            

print(ans)


D,G = 5,25000
prob_num = [20,40,50,30,1]
comp = [1000,1000,1000,1000,1000,1000]

comp_point = []
for i in range(D):
    comp_point.append((100*(i+1)*prob_num[i]+comp[i]))


res = G
ans = 0
while res>0:
    req_prob = []
    temp_min = []
    temp_value = []
    for i in range(D):
        if prob_num[i] == 0:
            req_prob.append(10000000)
        elif res>=100*(i+1)*prob_num[i]:
            req_prob.append(prob_num[i])
        else:
            req_prob.append((res//(100*(i+1))) + bool(res%(100*(i+1))))
            
    for i in range(D):
        temp_min.append(min(res,comp_point[i]))
        
    for i in range(D):
        temp_value.append(temp_min[i]/req_prob[i])
        
    choice = temp_value.index(max(temp_value))
    
    ans += req_prob[choice]
    if 100*(choice+1)*req_prob[choice] < comp_point[choice]:

        res -= 100*(choice+1)*req_prob[choice]
    else:
        res -= comp_point[choice]
    prob_num[choice] -= req_prob[choice]
    
#    print(ans,res)
    
print(ans)

D,G = map(int, input().split())
prob_num = []
bonus = []
comp_pt = []
for i in range(D):
    p,b = map(int, input().split())
    prob_num.append(p)
    bonus.append(b)
    comp_pt.append(100*(i+1)*p+b)

def dfs(hascomp:str, target:int, prob:int, depth:int) -> int:
    if target <= 0:
        
        return prob
    
    elif depth == D:
        for i in range(D-1,-1,-1):
            if hascomp[i] == "n":
                if target <= 100*(i+1)*(prob_num[i]-1):
                    prob += (target//(100*(i+1)))+bool(target%(100*(i+1)))
                    print(hascomp, depth, prob)
                    return prob
                
                else:
                    prob += (prob_num[i]-1)
                    target -= 100*(i+1)*(prob_num[i]-1)
                    
        if target > 0:
            
            return 10**5
        
    else:
        new_tar = target-comp_pt[depth]
        new_prob = prob + prob_num[depth]
        return min(dfs(hascomp+"y",new_tar, new_prob, depth+1),
                   dfs(hascomp+"n",target, prob, depth+1))
        

ans = dfs("",G,0,0)
print(ans)

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

d,g = li()
pc = []
for _ in range(d):
    pc.append(tuple(li()))
    
ans = 10**10
for bit in range(1<<d):
    point = 0
    probs = 0
    for b in range(d):
        if bit & (1<<b):
            point += (100*(b+1)*pc[b][0] + pc[b][1])
            probs += pc[b][0]
            
    if point >= g:
        ans = min(ans, probs)
           
    else:

        res = g-point
        for q in range(d-1, -1, -1):
            if bit & (1<<q):
                continue
            
            if 100*(q+1)*(pc[q][0]-1) >= res:
                probs += -(-res // (100*(q+1)))
                res = 0
                
            else:
                res -= 100*(q+1)*(pc[q][0]-1)
                probs += pc[q][0]
        
        if res == 0:        
            ans = min(ans,probs)

            
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted