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):
def main():
  D, G = list(map(int, input().split()))
  P = []
  for i in range(1, D+1):
    P.append(tuple(map(int, input().split())))

  # print(D, G, P)
  minp = float('inf')
  for bit in range(1 << D):
    total = 0
    num_p = 0
    bset = set()
    for i in range(D):
      mask = 1 << i
      if bit & mask:
        total += P[i][1] + 100*(i+1)*P[i][0]
        num_p += P[i][0]
        bset.add(i)

    # print(f'bset:{bset}, num_p:{num_p}')

    res = G - total
    if res <= 0:
      if num_p < minp:
        minp = num_p
      continue

    for i in reversed(sorted(set([i for i in range(D)]) - bset)):
      maxv = 100*(i+1) * (P[i][0]-1)

      if res <= maxv:
        num_take = max(min(bisect.bisect(list(range(0, maxv+100*(i+1), 100*(i+1))), res)-1, P[i][0]-1), 1)
        # print(i, list(range(0, maxv, 100*(i+1))))
        # print(f'res:{res} so solve {100*(i+1)} * {num_take}')
        num_p += num_take
        res -= 100*(i+1)*num_take
        if num_p < minp:
          minp = num_p
        break

      res -= maxv
      # print(f'solve {i+1} * {P[i][0]-1}')
      num_p += (P[i][0]-1)

  print(minp)


if(__name__ == '__main__'):
  main()

def main():
  D, G = list(map(int, input().split()))
  P = []
  for i in range(1, D+1):
    P.append(tuple(map(int, input().split())))

  # print(D, G, P)
  minp = float('inf')
  for bit in range(1 << D):
    total = 0
    num_p = 0
    bset = set()
    for i in range(D):
      mask = 1 << i
      if bit & mask:
        total += P[i][1] + 100*(i+1)*P[i][0]
        num_p += P[i][0]
        bset.add(i)

    # print(f'bset:{bset}, num_p:{num_p}')

    res = G - total
    if res <= 0:
      if num_p < minp:
        minp = num_p
      continue

    for i in reversed(sorted(set([i for i in range(D)]) - bset)):
      maxv = 100*(i+1) * (P[i][0]-1)

      if res <= maxv:
        num_take = max(min(bisect.bisect(list(range(0, maxv+100*(i+1), 100*(i+1))), res)-1, P[i][0]-1), 1)
        # print(i, list(range(0, maxv, 100*(i+1))))
        # print(f'res:{res} so solve {100*(i+1)} * {num_take}')
        num_p += num_take
        res -= 100*(i+1)*num_take
        if num_p < minp:
          minp = num_p
        break

      res -= maxv
      # print(f'solve {i+1} * {P[i][0]-1}')
      num_p += (P[i][0]-1)

  print(minp)


if(__name__ == '__main__'):
  main()

import bisect


def main():
  D, G = list(map(int, input().split()))
  P = []
  for i in range(1, D+1):
    P.append(tuple(map(int, input().split())))

  # print(D, G, P)
  minp = float('inf')
  for bit in range(1 << D):
    total = 0
    num_p = 0
    bset = set()
    for i in range(D):
      mask = 1 << i
      if bit & mask:
        total += P[i][1] + 100*(i+1)*P[i][0]
        num_p += P[i][0]
        bset.add(i)

    # print(f'bset:{bset}, num_p:{num_p}')

    res = G - total
    if res <= 0:
      if num_p < minp:
        minp = num_p
      continue

    for i in reversed(sorted(set([i for i in range(D)]) - bset)):
      maxv = 100*(i+1) * (P[i][0]-1)

      if res <= maxv:
        num_take = max(min(bisect.bisect(list(range(0, maxv+100*(i+1), 100*(i+1))), res)-1, P[i][0]-1), 1)
        # print(i, list(range(0, maxv, 100*(i+1))))
        # print(f'res:{res} so solve {100*(i+1)} * {num_take}')
        num_p += num_take
        res -= 100*(i+1)*num_take
        if num_p < minp:
          minp = num_p
        break

      res -= maxv
      # print(f'solve {i+1} * {P[i][0]-1}')
      num_p += (P[i][0]-1)

  print(minp)


if(__name__ == '__main__'):
  main()

Verdicts: Runtime Error

Runtime Error

Accepted