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 = input().split(' ')
d,g = int(d),int(g)


def argmax(x):
	max_value = -1000000000
	index = 0
	for i,e in enumerate(x):
		if max_value < e:
			index = i
	return i

def compute(point,prob_num,bonus_point):
	return point*prob_num + bonus_point


point_list=[input().split(' ') for i in range(d)]
point_list = [[int(e) for e in point] for point in point_list]
efficiency = [((i+1)*100.*point[0]+ point[1])/point[0] for i,point in enumerate(point_list)]

count = 0

while g > 0:
	index = argmax(efficiency)
	element = point_list[index]
	element_point = compute((index+1)*100,element[0],element[1])
	tmp_g = g
	if g - element_point < -100:
		for i in range(element[0]-1):
			tmp_g -= (index+1)*100
			if tmp_g <= 0:
				count += i+1
				print(count)
				exit()
		tmp_g -= (index+1)*100
		tmp_g -= element[1]
		count += element[0]
		if tmp_g <= 0:
			print(count)
			exit()
	elif g - element_point == 0:
		count += element[0]
		print(count)
		exit()		
	else:
		count += element[0]
		g -= element_point
		del(point_list[index])
		del(efficiency[index])
print(count)



def argmax(x):
	max_value = -1000000000
	index = 0
	for i,e in enumerate(x):
		if max_value < e:
			index = i
	return i

def compute(point,prob_num,bonus_point):
	return point*prob_num + bonus_point


d,g = input().split(' ')
d,g = int(d),int(g)

point_list=[input().split(' ') for i in range(d)]
point_list = [[int(e) for e in point] for point in point_list]
efficiency = [((i+1)*100.*point[0]+ point[1])/point[0] for i,point in enumerate(point_list)]
points = [i*100 for i in range(1,d+1)]
count = 0

while g > 0:
	index = argmax(efficiency)
	element = point_list[index]
	element_point = compute((index+1)*100,element[0],element[1])
	tmp_g = g
	if g - element_point <= -100:
		for i in range(point_list[-1][0]-1):
			tmp_g -= points[-1]*100
			if tmp_g <= 0:
				count += i+1
				print(count)
				exit()
		tmp_g -= points[-1]*100
		tmp_g -= element[1]
		count += element[0]
		if tmp_g <= 0:
			print(count)
			exit()
	elif g - element_point == 0:
		count += element[0]
		print(count)
		exit()		
	else:
		count += element[0]
		g -= element_point
		del(point_list[index])
		del(efficiency[index])
		del(points[index])
print(count)



def argmax(x):
	max_value = -1000000000
	index = 0
	for i,e in enumerate(x):
		if max_value < e:
			index = i
	return i

def compute(point,prob_num,bonus_point):
	return point*prob_num + bonus_point


d,g = input().split(' ')
d,g = int(d),int(g)

point_list=[input().split(' ') for i in range(d)]
point_list = [[int(e) for e in point] for point in point_list]
efficiency = [((i+1)*100.*point[0]+ point[1])/point[0] for i,point in enumerate(point_list)]

count = 0

while g > 0:
	index = argmax(efficiency)
	element = point_list[index]
	element_point = compute((index+1)*100,element[0],element[1])
	tmp_g = g
	if g - element_point <= -100:
		for i in range(element[0]-1):
			tmp_g -= (index+1)*100
			if tmp_g <= 0:
				count += i+1
				print(count)
				exit()
		tmp_g -= (index+1)*100
		tmp_g -= element[1]
		count += element[0]
		if tmp_g <= 0:
			print(count)
			exit()
	elif g - element_point == 0:
		count += element[0]
		print(count)
		exit()		
	else:
		count += element[0]
		g -= element_point
		del(point_list[index])
		del(efficiency[index])
print(count)



D, G = map(int, input().split())
Q = []
for i in range(D):
    p, c = map(int, input().split())
    Q.append([p, c,(i+1)*100])
ans = 10**18
for i in range(2**D):
    state = format(i,'0%ib'%(D))
    value = 0
    count = 0
    for s,(p,c,v) in zip(state,Q):
        if s == '1':
            value += p*v + c
            count += p
    if value >= G:
        ans = min(ans,count)
    else:
        for s,(p,c,v) in zip(reversed(state),reversed(Q)):
            if s == '1':
                continue
            if (G-value) > v*(p-1):
                value += v*(p-1)
                count += p-1
            else:
                if (G-value)%v == 0:
                    c = (G-value)//v
                else:
                    c = int((G-value)/v)+1
                value += v*c
                count += c
                ans = min(ans,count)
                break
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted