TnT/Multi_CodeNet4Repair huggingface dataset:
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 itertools
import math

D, G = map(int, input().split())
p = [0] * D
c = [0] * D
com = [0] * D
for i in range(D):
    p[i], c[i] = map(int, input().split())
    com[i] = [100 * (i+1) * p[i] + c[i], p[i]]

l = list(itertools.product(range(2), repeat=D))
score_list = []
for i in range(len(l)):
    tmp1 = 0
    tmp2 = []
    tmp3 = -1
    tmp5 = 0
    for j in range(D):
        if l[i][j] == 0:
            tmp2.append(j)
            pass
        else:
            tmp1 += com[j][0]
            tmp5 += com[j][1]
    if len(tmp2) != 0:
        tmp3 = tmp2[-1]
    if tmp3 != -1:
        tmp4 = tmp1 + (tmp3+1) * 100 * (p[tmp3]-1)
    else:
        tmp4 = tmp1
    
    score_list.append([tmp1, tmp3, tmp4, tmp5])

#print(score_list)

ans_list = []

for i in range(len(score_list)):
    if score_list[i][1] != -1:
        if score_list[i][0]<= G and score_list[i][2] >= G:
            tmp = math.ceil((G - score_list[i][0]) / ((score_list[i][1]+1)*100))
            ans = score_list[i][3] + tmp
            ans_list.append(ans)
            print(score_list[i][3], ans)
    else:
        if score_list[i][0]>= G:
            ans_list.append(score_list[i][3])

#print(ans_list)
print(min(ans_list))



import itertools
D, G = map(int, input().split())
p = [0] * D
c = [0] * D
pc = [0] * D
for i in range(D):
    p[i], c[i] = map(int, input().split())

l = list(itertools.product(range(2), repeat=D))

comp = []
for i in range(len(l)-1):
    score = 0
    count = 0
    m = -100
    for j in range(D):
        if l[i][j] == 1:
            score += (j+1) * 100 * p[j] + c[j]
            count += p[j]
        elif l[i][j] == 0:
            m = max(m, j)
    tmp = [score, count]
    comp.append(tmp)
    for j in range(p[m]-1):
        score += (m+1) * 100 * 1
        count += 1
        tmp = [score, count]
        comp.append(tmp)

score = 0
count = 0
for i in range(D):
    score += (i+1) * 100 * p[i] + c[i]
    count += p[i]
tmp = [score, count]
comp.append(tmp)    

#print(comp)

ans = []
for i in range(len(comp)):
    if comp[i][0] >= G:
        ans.append(comp[i][1])

ans = min(ans)
print(ans)


Verdicts: Wrong Answer

Accepted
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())
G //= 100
pc = []
for d in range(D):
  p, c = map(int, input().split())
  pc.append([p, c//100])


ans = 10 ** 4

for i in range(2**D):
  points = 0
  num = 0
  idx = -1
  for d in range(D):
    
    if i>>d & 1:
      points += pc[d][0]*(d+1) + pc[d][1]
      num += pc[d][0]
    else:
      idx = d
  if points >= G:
    ans = min(ans, num)
  elif idx >= 0: 
    num_add = - (- (G - points) // (idx + 1))
    print((-(G-points)) // (idx+1))
    if num_add <= pc[idx][0]:
      ans = min(ans, num + num_add)

print(ans)


D, G = map(int, input().split())
G //= 100
pc = []
for d in range(D):
  p, c = map(int, input().split())
  pc.append([p, c//100])


ans = 10 ** 4

for i in range(2**D):
  points = 0
  num = 0
  idx = -1
  for d in range(D):
    
    if i>>d & 1:
      points += pc[d][0]*(d+1) + pc[d][1]
      num += pc[d][0]
    else:
      idx = d
  if points >= G:
    ans = min(ans, num)
  elif idx >= 0: 
    num_add = - (- (G - points) // (idx + 1))
    if num_add <= pc[idx][0]:
      ans = min(ans, num + num_add)

print(ans)

Verdicts: Wrong Answer

Accepted
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())
p = [0]*int(D)
c = [0]*int(D)
for i in range(D):
  p[i],c[i] = map(int,input().split())
total = 0
for i in range(D):
  total += p[i] * (i+1) * 100 + c[i]
ans = sum(p)
j = 0
pi = p[j]
while total>=G:
  if pi==0 and j<(D-1):
    j += 1
    pi = p[j]
  if pi==p[j]:
    total -= c[j]
  total -= (j+1)*100
  pi -= 1
  ans -= 1
print(ans+1)

D,G = map(int,input().split())
p = [0]*int(D)
c = [0]*int(D)
for i in range(D):
  p[i],c[i] = map(int,input().split())
ans = 1e9
for i in range(2**D):
  s = 0
  num = 0
  rest_max = -1
  for j in range(D):
    if (i>>j)&1:
      s += 100 * (j+1) * p[j] + c[j]
      num += p[j]
    else:
      rest_max = j
  if s<G:
    s1 = 100 * (rest_max + 1)
    need = int((G - s + s1 - 1) / s1)
    if need >= p[rest_max]:
      continue
    num += need
  ans = min(ans, num)
print(ans)

Verdicts: Wrong Answer

Accepted
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())
p = []
c = []
su = []
ans = 1000
for i in range(d):
  a,b = map(int, input().split())
  p.append(a)
  c.append(b)
  su.append(a*100*(i+1)+b)
bit = [1,2,4,8,16,32,64,128,256,512]
for i in range(1024):
  count = 0
  for j in range(d):
    if i & bit[j] == 0:
      continue
    score += su[j]
    count += p[j]
  if score < g:
    continue
  for j in range(d):
    if i & bit[j] == 0 or score - su[j] >= g:
      continue
    rest = g - (score - su[j])
    count_tmp = count - p[j] + math.ceil(rest / ((d+i)*100))
    ans = min(ans, count_tmp)
print(ans)

import math
d, g = map(int, input().split())
p = []
c = []
su = []
ans = 1000
for i in range(d):
  a,b = map(int, input().split())
  p.append(a)
  c.append(b)
  su.append(a*100*(i+1)+b)
bit = [1,2,4,8,16,32,64,128,256,512]
for i in range(1024):
  count = 0
  for j in range(d):
    if i & bit[j] == 0:
      continue
    score += su[j]
    count += p[j]
  if score < g:
    continue
  for j in range(d):
    if i & bit[j] == 0 or score - su[j] >= g:
      continue
    rest = g - (score - su[j])
    count_tmp = count - p[j] + math.ceil(rest / ((d+i)*100))
    ans = min(ans, count_tmp)
print(ans)

import math
d, g = map(int, input().split())
p = []
c = []
su = []
ans = 1000
for i in range(d):
  a,b = map(int, input().split())
  p.append(a)
  c.append(b)
  su.append(a*100*(i+1)+b)
bit = [1,2,4,8,16,32,64,128,256,512]
for i in range(int(math.pow(2,d))):
  count = 0
  score = 0
  for j in range(d):
    if i & bit[j] == 0:
      continue
    score += su[j]
    count += p[j]
  if score < g:
    continue
  for j in range(d):
    if i & bit[j] == 0 or score - su[j] >= g:
      continue
    rest = g - (score - su[j])
    count_tmp = min(count , count - p[j] + math.ceil(rest / ((j+1)*100)))
    ans = min(ans, count_tmp)
print(ans)

Verdicts: Runtime Error

Runtime Error

Accepted
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=[list(map(int,input().split())) for i in range(D)]
print(pc)
ans=G // 100

for i in range(2**D):
    score=0
    b=0
    cnt=0
    for j in range(D):
        if ((i>>j)&1):
            score+=100*(j+1)*pc[j][0]+pc[j][1]
            cnt+=pc[j][0]
        else:
            b=j
    for k in range(pc[b][0]):
        print(ans)
        if score>=G and cnt<ans:
            ans=cnt
        score+=(b+1)*100
        cnt+=1
print(ans)

D,G=map(int,input().split())
pc=[list(map(int,input().split())) for i in range(D)]
print(pc)
ans=G // 100

for i in range(2**D):
    score=0
    b=0
    cnt=0
    for j in range(D):
        if ((i>>j)&1):
            score+=100*(j+1)*pc[j][0]+pc[j][1]
            cnt+=pc[j][0]
        else:
            b=j
    for k in range(pc[b][0]):
        if score>=G and cnt<ans:
            ans=cnt
        score+=(b+1)*100
        cnt+=1
print(ans)


D,G=map(int,input().split())
pc=[list(map(int,input().split())) for i in range(D)]
ans=G // 100

for i in range(2**D):
    score=0
    b=0
    cnt=0
    for j in range(D):
        if ((i>>j)&1):
            score+=100*(j+1)*pc[j][0]+pc[j][1]
            cnt+=pc[j][0]
        else:
            b=j
    for k in range(pc[b][0]):
        if score>=G and cnt<ans:
            ans=cnt
        score+=(b+1)*100
        cnt+=1
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Accepted
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 itertools
D, G = map(int, input().split())
score_list = []
for i in range(D):
    p, c = map(int, input().split())
    score_list.append([(i + 1) * 100] * (p - 1) + [c + (i + 1) * 100])
full_score = [sum(i) for i in score_list]
per = list(itertools.permutations(range(D)))
ans = 10000
print(score_list)

for k in per:
    pro = 0
    sco = 0
    for i in k:
        if G >= sco + full_score[i]:
            sco += full_score[i]
            pro += len(score_list[i])
        else:
            for j in score_list[i]:
                sco += j
                pro += 1
                if sco >= G:
                    break
                else:
                    continue
        if sco >= G:
            break
        else:
            continue
    if ans > pro:
        ans = pro
    else:
        continue
print(ans)

D, G = map(int, input().split())
score_list = []
for i in range(D):
    p, c = map(int, input().split())
    score_list.append([(i + 1) * 100] * (p - 1) + [c + (i + 1) * 100])
full_score = [sum(i) for i in score_list]
sol = [format(i, 'b').zfill(D) for i in range(2 ** D)]
ans = []

for i in sol:
    problem = 0
    score = 0
    for j in range(D):
        if i[j] == '1':
            score += full_score[j]
            problem += len(score_list[j])
        else:
            continue
    if score >= G:
        ans.append(problem)
    else:
        if score + full_score[i.rfind('0')] < G:
            continue
        else:
            while score < G:
                score += score_list[i.rfind('0')][0]
                problem += 1
            ans.append(problem)

print(min(ans))

Verdicts: Wrong Answer

Accepted
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 = [0]+[list(map(int,input().split())) for _ in range(D)]

def dfs(d, g):
    if(d == 0):
        return 1e9

    c = min(g//(100*d), PC[d][0])
    s = 100*d*c
    if c == PC[d][0]:
        s += PC[d][1]
    if s<g:
        c += f(d-1, g-s)
    return min(c, f(d-1,g))

print(dfs(D, G))

D, G = map(int, input().split())
PC = [0]+[list(map(int,input().split())) for _ in range(D)]
print(1e9)

def dfs(d, g):
    if(d == 0):
        return 1e9

    c = min(g//(100*d), PC[d][0])
    s = 100*d*c
    if c == PC[d][0]:
        s += PC[d][1]
    if s<g:
        c += f(d-1, g-s)
    return min(c, f(d-1,g))

print(dfs(D, G))

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

def dfs(d, g):
    # if(d == 0):
    #     return 1e9

    c = min(g//(100*d), PC[d][0])
    s = 100*d*c
    if c == PC[d][0]:
        s += PC[d][1]
    if s<g:
        c += f(d-1, g-s)
    return min(c, f(d-1,g))

print(dfs(D, G))

D, G = map(int, input().split())
PC = [0]+[list(map(int,input().split())) for _ in range(D)]
print(1e9)

def dfs(d, g):
    # if(d == 0):
    #     return 1e9

    c = min(g//(100*d), PC[d][0])
    s = 100*d*c
    if c == PC[d][0]:
        s += PC[d][1]
    if s<g:
        c += f(d-1, g-s)
    return min(c, f(d-1,g))

print(dfs(D, G))

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

def dfs(d, g):
    if(d == 0):
        return 1e9

    c = min(g//(100*d), PC[d][0])
    s = 100*d*c
    if c == PC[d][0]:
        s += PC[d][1]
    if s<g:
        c += dfs(d-1, g-s)
    return min(c, dfs(d-1,g))

print(dfs(D, G))

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted
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):
x = [list(map(int, input().split())) for i in range(d)]
ans2=float('inf')

for i in range(2**d):
    v=[0]*d
    ans=0
    ans1=0
    for j in range(d):
        if (i>>j)&1==1:
            ans+=(x[j][0]*100*(j+1))+x[j][1]
            ans1+=x[j][0]
            v[j]=1


    if ans<g:
        for k in range(d):
            if v[d-k-1]==0:
                if g-ans<=(x[d-k-1][0]-1)*100*(d-k):
                    w=-(-(g-ans)//(100*(d-k)))

                    ans2=min(ans2,ans1+w)
                else:
                    break
    else:
        ans2=min(ans2,ans1)
print(ans2)

d,g= map(int, input().split())
x = [list(map(int, input().split())) for i in range(d)]
ans2=float('inf')

for i in range(2**d):
    v=[0]*d
    ans=0
    ans1=0
    for j in range(d):
        if (i>>j)&1==1:
            ans+=(x[j][0]*100*(j+1))+x[j][1]
            ans1+=x[j][0]
            v[j]=1


    if ans<g:
        for k in range(d):
            if v[d-k-1]==0:
                if g-ans<=(x[d-k-1][0]-1)*100*(d-k):
                    w=-(-(g-ans)//(100*(d-k)))

                    ans2=min(ans2,ans1+w)
                else:
                    break
    else:
        ans2=min(ans2,ans1)
print(ans2)

Verdicts: Runtime Error

Accepted
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):
from collections import deque
import itertools, math
d,g = list(map(int,input().split()))
pc = [list(map(int,input().split())) for _ in range(d)]
g /= 100

pat = deque([[] for _ in range(3)])
for i in sorted(range(d),reverse=True):
  if pc[i][0]*(i+1) >= g:
    pat[0].append(i)
  elif pc[i][0]*(i+1) + pc[i][1]//100 >= g:
    pat[1].append(i)
  else:
    pat[2].append(i)

pat = deque(pat[0] + pat[1] + pat[2])

#ans = sum([pc[x][0] for x in range(d)])
ans = float('inf')

def dfs(i, point, cnt, pat):
  global ans
  if point < g:
    n = min(pc[i][0], math.ceil((g-point)/(i+1)) )
    point += n*(i+1)
    cnt += n
    if n == pc[i][0]:
      point += pc[i][1]//100
  print(i,point,cnt)  
  if point >= g:
    ans = min(ans, cnt)
    point = 0
    cnt = 0
  
  if len(pat) > 1:
    pat.popleft()
    dfs(pat[0], point, cnt, pat)

dfs(pat[0],0,0,pat)
print(ans)

from collections import deque
import itertools, math
d,g = list(map(int,input().split()))
pc = [list(map(int,input().split())) for _ in range(d)]
g /= 100

#ans = sum([pc[x][0] for x in range(d)])
ans = float('inf')
for bit in range(1<<d):
  cnt = 0
  point = 0
  pat = set(range(1,d+1))
  
  for i in range(d):
    if bit & (1<<i):
      point += pc[i][0]*(i+1) + pc[i][1]//100
      cnt += pc[i][0]
      pat.discard(i+1)
  
  if point < g:
      next = max(pat)
      n = min(pc[next-1][0], math.ceil((g - point)/(next)))
      cnt += n
      point += n*(next)
    
  if point >= g:
      print(ans,cnt)
      ans = min(ans,cnt)


print(ans)
  
  

d,g  = list(map(int,input().split()))
pc = [list(map(int,input().split())) for _ in range(d)]

ans = float('inf')

for bit in range(1<<d):
  sum = 0
  cnt = 0
  rem = set(range(d))
  for i in range(d):
    if bit & 1<<i:
      sum += pc[i][0]*(i+1)*100 + pc[i][1]
      cnt += pc[i][0]
      rem.discard(i)
    
  if sum < g:
    u = max(rem)
    n = min(pc[u][0],  -( -(g-sum)//((u+1)*100) ))
    cnt += n
    sum += n*(u+1)*100
    
  if sum >= g:
    ans = min(ans, cnt)
    

print(ans)

Verdicts: Wrong Answer

Wrong Answer

Accepted
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):
from math import ceil

D, G = [int(t) for t in input().split()]
p = []
c = []
for i in range(D):
    p_, c_ = [int(t) for t in input().split()]
    p.append(p_)
    c.append(c_)

print(p,c)

def solve(G, i):
    
    if i <= 0:
        return float('inf')
    
    n = min(ceil(G / (100 * i)), p[i - 1])
    s = 100 * i * n
    
    if n == p[i - 1]:
        s += c[i - 1]
    if G > s:
        n += solve(G - s, i - 1)
    return min(n, solve(G, i - 1))

print(solve(G, D))

from math import ceil
D,G = map(int,input().split())
list = [list(map(int,input().split())) for _ in range(D)]

def dfs(G,i):
    if i <= 0:
        return float('inf')
    n = min(ceil(G/(100*i)),list[i-1][0])
    s = 100*i*n
    if n == list[i-1][0]:
        s += list[i-1][1]
    if G > s:
        n += dfs(G-s,i-1)
    return min(n,dfs(G,i-1))

print(dfs(G,D))

Verdicts: Wrong Answer

Accepted
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())

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


ten = 0
c = 0
kei = 0

for i,k in enumerate(li[::-1]):
    for j in range(k[0]):
        ten += 100*(D-i)
        c+=1
        if j==k[0]-1:
            ten += k[1]
        if ten>=G:
            kei = c
            break
    else:continue
    break
     
num_min = 1001
ten2 = 0

for i in range(2**D):
    num_i = 0
    ten_i = 0
    for j in range(D):
        if (i>>j) & 1:
            num_i += li[j][0]
            ten_i += li[j][1]
    if ten_i < G:continue
    if num_i <= num_min:
        num_min=num_i
        ten2 = ten_i

if num_min < c:
    print(num_min)
else:print(c)

[D,G],*li = [list(map(int,i.split())) for i in open(0)]

ans = float('inf')

def dfs(i,ten,num,p):
    global ans
    if i==D:
        if ten >= G:
            ans = min(ans,num)
        else:
            for q in p:
                for r in range(li[q][0]):
                    ten += (q+1)*100
                    num += 1
                    if r==li[q][0]:
                        ten += li[q][1]
                    if ten >= G:
                        ans = min(ans,num)
                        break
                else:continue
                break
    else:
        dfs(i+1,ten+(i+1)*100*li[i][0]+li[i][1],num+li[i][0],p)
        dfs(i+1,ten,num,[i]+p)
dfs(0,0,0,[])
print(ans)

Verdicts: Wrong Answer

Accepted
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())
grid = [[0,0]]
for i in range(D):
    p,c = map(int, input().split())
    grid.append([p,c])

import itertools
kumi = list(itertools.product([0,1], repeat=D))
anls = []
fans = float('inf')
for item in kumi:
    count = 0
    ans = 0
    k = 0
    score = 0
    for i in item:
        count += 1
        if i == 1:
            score += grid[count][0]*100*count + grid[count][1]
            ans += grid[count][0]
        else:
            k = count

    if G <= score :
        fans = min(fans,ans)
    elif score+(k*100)*(grid[k][0]-1) >= G :
        a = int((G-score)/(k*100))
        if score+a*k*100=G:
            ans += a
        else:
            ans += (a+1)
        fans = min(fans,ans)
if fans != float('inf'):
    fans = int(fans)
print(fans)

D, G = map(int, input().split())
grid = [[0,0]]
for i in range(D):
    p,c = map(int, input().split())
    grid.append([p,c])

import itertools
kumi = list(itertools.product([0,1], repeat=D))
anls = []
fans = float('inf')
for item in kumi:
    count = 0
    ans = 0
    k = 0
    score = 0
    for i in item:
        count += 1
        if i == 1:
            score += grid[count][0]*100*count + grid[count][1]
            ans += grid[count][0]
        else:
            k = count

    if G <= score :
        fans = min(fans,ans)
    elif score+(k*100)*(grid[k][0]-1) >= G :
        a = int((G-score)/(k*100))
        if score+a*k*100==G:
            ans += a
        else:
            ans += (a+1)
        fans = min(fans,ans)
if fans != float('inf'):
    fans = int(fans)
print(fans)



Verdicts: Runtime Error

Accepted
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 = []

L = []

t = 10 ** 9
m = 0

for i in range(1,D + 1):
  p,c = map(int,input().split())
  s = 0
  pc = []
  for j in range(p):
    s += i * 100
    if j == p - 1:
      s += c
      L.append([j + 1,s])
    if s >= G and j + 1 < t:
      t = j + 1
    pc.append([j + 1,s])
  PC.append(pc)

def recur(problems):
　
  if len(problems) == D:
    ans = 10 ** 9
    score = 0
    times = 0
    
    for j in range(D):
      if problems[j] == 1:
        score += L[j][1]
        times += L[j][0]
    
    if score >= G:
      ans = min(ans,times)
      return ans
    
    
    else:
      remain = G - score
      if remain <= max([L[i][1] for i in range(D) if problems[i] == 0]):
        for k in range(D):
          if problems[k] == 0:
            for l in range(len(PC[k])):
              if remain <= PC[k][l][1] and ans >= PC[k][l][0]:
                ans = PC[k][l][0]
        ans += times
        return ans
      else:
        return 10 ** 9
  
  else:
    
    ret1 = recur(problems + [1])
    
    ret2 = recur(problems + [0])
    
    return min(ret1,ret2)

print(recur([]))

import math
D, G = map(int, input().split())

PC = []
for _ in range(D):
    p, c = map(int, input().split())
    PC.append([p, c])

ans = 10 ** 9


for i in range(2 ** D):
    score = 0
    time = 0
    maxj = -1
    
    for j in range(D):
    
        if ((i >> j) & 1):
            score += (j + 1) * PC[j][0] * 100 + PC[j][1]
            time += PC[j][0]
        
        
        else:
            maxj = max(maxj,j)
    
    if maxj == -1:
      ans = min(ans, time)
    
    elif score + (maxj + 1) * (PC[maxj][0] - 1) * 100 >= G:
        
        
        time += max(0, math.ceil((G - score) / (maxj + 1) / 100))
        
        ans = min(ans, time)

print(ans)



Verdicts: Runtime Error

Accepted
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 = [int(s) for s in input().split()]
problems = [[int(s) for s in input().split()] for _ in range(D)]

result = 10 ** 8

for i in range(2 ** D):
    cnt_problem = 0
    cnt_score = 0
    for j in range(D):
        if i << j:
            cnt_score += problems[j][1] + 100 * (j + 1) * problems[j][0]
            cnt_problem += problems[j][0]

    for j in reversed(range(D)):
        if not i << j:
            for k in range(1, problems[j][0]):
                if cnt_score >= G:
                    break
                else:
                    cnt_score += problems[j][1]
                    cnt_problem += 1
    result = min(cnt_problem, result)

print(result)


D, G = [int(s) for s in input().split()]
problems = [[int(s) for s in input().split()] for _ in range(D)]

result = 10 ** 8

for i in range(2 ** D):
    cnt_problem = 0
    cnt_score = 0
    for j in range(D):
        if i >> j & 1:
            cnt_score += problems[j][1] + 100 * (j + 1) * problems[j][0]
            cnt_problem += problems[j][0]

    for j in reversed(range(D)):
        if not i >> j & 1:
            for _ in range(problems[j][0]):
                if cnt_score >= G:
                    break
                else:
                    cnt_score += 100 * (j + 1)
                    cnt_problem += 1
    result = min(cnt_problem, result)

print(result)


Verdicts: Wrong Answer

Accepted
Problem: The _ABC number_ of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:    * 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)   * T_i = `A` (T_i is the i-th character of T from the beginning.)   * T_j = `B`   * T_k = `C`  For example, when T = `ABCBC`, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.  You are given a string S. Each character of S is `A`, `B`, `C` or `?`.  Let Q be the number of occurrences of `?` in S. We can make 3^Q strings by replacing each occurrence of `?` in S with `A`, `B` or `C`. Find the sum of the ABC numbers of all these strings.  This sum can be extremely large, so print the sum modulo 10^9 + 7.

Submission attempts (in order):

#     if n-r<r: r=n-r
#     if r == 0: return 1
#     if r == 1: return n
# 

#     denominator = [k + 1 for k in range(r)]
# 
#     for p in range(2,r+1):


#             offset = (n - r) % p
#             for k in range(p-1,r,p):
#                 numerator[k - offset] /= pivot

# 
#     result = 1
#     for k in range(r):
#         if numerator[k] > 1:
#             result *= int(numerator[k]) %mod
# 
#     return result % mod

A=list(input())
n=len(A)
mod=10**9+7
ans=0
numa= A[0]=="A" 
numa_= A[0]=="?"
numc=A[2:].count("C")
numc_= A[2:].count("?")

for i in range(1,n-1):
    #print(numa,numa_,numc,numc_)
    apro=cpro=0
    if A[i]=="B" or A[i]=="?":
        # for k in range(numa_+1):
        
        # for k in range(numc_+1):
        #     cpro+= (((C(numc_,k)*pow(2,numc_-k,mod))%mod)*(numc+k))%mod
        
        apro= (3*numa+numa_)*3**(numa_-1)
        cpro= (3*numc+numc_)*3**(numc_-1)
        ans+= (apro*cpro)%mod
        ans%=mod
    if A[i] == "A":
        numa+=1
    if A[i]=="?":
        numa_+=1
    if A[i+1] =="C":
        numc-=1
    if A[i+1]=="?":
        numc_-=1
print(ans)



#     if n-r<r: r=n-r
#     if r == 0: return 1
#     if r == 1: return n
# 

#     denominator = [k + 1 for k in range(r)]
# 
#     for p in range(2,r+1):


#             offset = (n - r) % p
#             for k in range(p-1,r,p):
#                 numerator[k - offset] /= pivot

# 
#     result = 1
#     for k in range(r):
#         if numerator[k] > 1:
#             result *= int(numerator[k]) %mod
# 
#     return result % mod

A=list(input())
n=len(A)
mod=10**9+7
ans=0
numa= A[0]=="A" 
numa_= A[0]=="?"
numc=A[2:].count("C")
numc_= A[2:].count("?")

for i in range(1,n-1):
    #print(numa,numa_,numc,numc_)
    apro=cpro=0
    if A[i]=="B" or A[i]=="?":
        # for k in range(numa_+1):
        
        # for k in range(numc_+1):
        #     cpro+= (((C(numc_,k)*pow(2,numc_-k,mod))%mod)*(numc+k))%mod
        
        apro= ((3*numa+numa_)*pow(3,(numa_-1),mod))%mod
        cpro= ((3*numc+numc_)*pow(3,(numc_-1),mod))%mod
        ans+= (apro*cpro)%mod
        ans%=mod
    if A[i] == "A":
        numa+=1
    if A[i]=="?":
        numa_+=1
    if A[i+1] =="C":
        numc-=1
    if A[i+1]=="?":
        numc_-=1
print(ans)


Verdicts: Runtime Error

Accepted
Problem: The _ABC number_ of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:    * 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)   * T_i = `A` (T_i is the i-th character of T from the beginning.)   * T_j = `B`   * T_k = `C`  For example, when T = `ABCBC`, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.  You are given a string S. Each character of S is `A`, `B`, `C` or `?`.  Let Q be the number of occurrences of `?` in S. We can make 3^Q strings by replacing each occurrence of `?` in S with `A`, `B` or `C`. Find the sum of the ABC numbers of all these strings.  This sum can be extremely large, so print the sum modulo 10^9 + 7.

Submission attempts (in order):
S = input()
N = len(S)
mod = 10**9+7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 0
for i in range(N):
    if S[i] == "?":
        numofABC = (numofABC*3+numofAB) % mod
        numofAB = (numofAB*3+numofA) % mod
        numofA = (numofA * 3 + 1) % mod
        numofquestion += 1
    elif S[i] == "C":
        numofABC = (numofAB+numofABC) % mod
    elif S[i] == "B":
        numofAB = (numofAB + numofA) % mod
    else:
        numofA += (numofquestion**3) % mod
print(numofABC)


S = input()
N = len(S)
mod = 10**9+7
numofA = 0
numofAB = 0
numofABC = 0
numofquestion = 1
for i in range(N):
    if S[i] == "?":
        numofABC = (numofABC*3+numofAB) % mod
        numofAB = (numofAB*3+numofA) % mod
        numofA = (numofquestion + numofA*3) % mod
        numofquestion = (numofquestion * 3) % mod
    elif S[i] == "C":
        numofABC = (numofAB+numofABC) % mod
    elif S[i] == "B":
        numofAB = (numofAB + numofA) % mod
    else:
        numofA = (numofquestion + numofA) % mod
print(numofABC)


Verdicts: Wrong Answer

Accepted
Problem: The _ABC number_ of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:    * 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)   * T_i = `A` (T_i is the i-th character of T from the beginning.)   * T_j = `B`   * T_k = `C`  For example, when T = `ABCBC`, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.  You are given a string S. Each character of S is `A`, `B`, `C` or `?`.  Let Q be the number of occurrences of `?` in S. We can make 3^Q strings by replacing each occurrence of `?` in S with `A`, `B` or `C`. Find the sum of the ABC numbers of all these strings.  This sum can be extremely large, so print the sum modulo 10^9 + 7.

Submission attempts (in order):
# coding: utf-8
# Your code here!

MOD = 1000000007
S = input()

def add(a,b):
    a += b
    if a >= MOD:
        a -= MOD
    return a

dp = [[0 for i in range(5)] for j in range(2000000)]

dp[0][0] = 1

for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = add(dp[i+1][j], dp[i][j] * 3 % MOD)
        else:
            dp[i+1][j] = add(dp[i+1][j], dp[i][j])
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] = add(dp[i+1][1], dp[i][0])
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] = add(dp[i+1][2], dp[i][1])
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] = add(dp[i+1][3], dp[i][2])

print(dp[len(S)][3])

# coding: utf-8
# Your code here!

MOD = 1000000007
S = input()

def add(a,b):
    a += b
    if a >= MOD:
        a -= MOD
    return a

dp = [[0 for i in range(5)] for j in range(200000)]

dp[0][0] = 1

for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = add(dp[i+1][j], dp[i][j] * 3 % MOD)
        else:
            dp[i+1][j] = add(dp[i+1][j], dp[i][j])
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] = add(dp[i+1][1], dp[i][0])
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] = add(dp[i+1][2], dp[i][1])
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] = add(dp[i+1][3], dp[i][2])

print(dp[len(S)][3])

Verdicts: Time Limit Exceeded

Accepted
Problem: The _ABC number_ of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:    * 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)   * T_i = `A` (T_i is the i-th character of T from the beginning.)   * T_j = `B`   * T_k = `C`  For example, when T = `ABCBC`, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.  You are given a string S. Each character of S is `A`, `B`, `C` or `?`.  Let Q be the number of occurrences of `?` in S. We can make 3^Q strings by replacing each occurrence of `?` in S with `A`, `B` or `C`. Find the sum of the ABC numbers of all these strings.  This sum can be extremely large, so print the sum modulo 10^9 + 7.

Submission attempts (in order):
def get_input(inp):
  li = inp.split("\n")

  def inner():
    return li.pop(0)
  return inner

INPUT="""????C?????B??????A???????"""
input = get_input(INPUT)

s = input().strip()
MOD = pow(10, 9) + 7




dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
dp[0][0] = 1

for i, _s in enumerate(s):
  if _s == '?':
    dp[0][i+1] += dp[0][i] * 3 % MOD
    dp[1][i+1] += dp[1][i] * 3 % MOD
    dp[2][i+1] += dp[2][i] * 3 % MOD
    dp[3][i+1] += dp[3][i] * 3 % MOD
    dp[0][i+1] %= MOD
    dp[1][i+1] %= MOD
    dp[2][i+1] %= MOD
    dp[3][i+1] %= MOD
  else:
    dp[0][i+1] += dp[0][i]
    dp[1][i+1] += dp[1][i]
    dp[2][i+1] += dp[2][i]
    dp[3][i+1] += dp[3][i]
    dp[0][i+1] %= MOD
    dp[1][i+1] %= MOD
    dp[2][i+1] %= MOD
    dp[3][i+1] %= MOD
  if _s == 'A' or _s == '?':
    dp[1][i+1] += dp[0][i]
    dp[1][i+1] %= MOD
  if _s == 'B' or _s == '?':
    dp[2][i+1] += dp[1][i]
    dp[2][i+1] %= MOD
  if _s == 'C' or _s == '?':
    dp[3][i+1] += dp[2][i]
    dp[3][i+1] %= MOD

print(dp[3][-1])


s = input().strip()
MOD = pow(10, 9) + 7




dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
dp[0][0] = 1

for i, _s in enumerate(s):
  if _s == '?':
    dp[0][i+1] += dp[0][i] * 3 % MOD
    dp[1][i+1] += dp[1][i] * 3 % MOD
    dp[2][i+1] += dp[2][i] * 3 % MOD
    dp[3][i+1] += dp[3][i] * 3 % MOD
    dp[0][i+1] %= MOD
    dp[1][i+1] %= MOD
    dp[2][i+1] %= MOD
    dp[3][i+1] %= MOD
  else:
    dp[0][i+1] += dp[0][i]
    dp[1][i+1] += dp[1][i]
    dp[2][i+1] += dp[2][i]
    dp[3][i+1] += dp[3][i]
    dp[0][i+1] %= MOD
    dp[1][i+1] %= MOD
    dp[2][i+1] %= MOD
    dp[3][i+1] %= MOD
  if _s == 'A' or _s == '?':
    dp[1][i+1] += dp[0][i]
    dp[1][i+1] %= MOD
  if _s == 'B' or _s == '?':
    dp[2][i+1] += dp[1][i]
    dp[2][i+1] %= MOD
  if _s == 'C' or _s == '?':
    dp[3][i+1] += dp[2][i]
    dp[3][i+1] %= MOD

print(dp[3][-1])


Verdicts: Wrong Answer

Accepted
Problem: The _ABC number_ of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:    * 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)   * T_i = `A` (T_i is the i-th character of T from the beginning.)   * T_j = `B`   * T_k = `C`  For example, when T = `ABCBC`, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.  You are given a string S. Each character of S is `A`, `B`, `C` or `?`.  Let Q be the number of occurrences of `?` in S. We can make 3^Q strings by replacing each occurrence of `?` in S with `A`, `B` or `C`. Find the sum of the ABC numbers of all these strings.  This sum can be extremely large, so print the sum modulo 10^9 + 7.

Submission attempts (in order):
S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

S_list = [{"bA": t_A, "bQ": t_Q, "aC": t_C, "aQ": N_Q - t_Q}]
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    ba_dic = {}
    ba_dic["bA"] = t_A
    ba_dic["bQ"] = t_Q
    if(S[i:i + 1] == "?"):
        ba_dic["aQ"] = N_Q - t_Q - 1
    else:
        ba_dic["aQ"] = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    ba_dic["aC"] = t_C

    S_list.append(ba_dic)

ans = 0
for i in range(len(S)):
    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue

    bA = S_list[i]["bA"]
    bQ = S_list[i]["bQ"]
    aC = S_list[i]["aC"]
    aQ = S_list[i]["aQ"]

    tmp = 9 * bA * aC + bQ * aQ + 3 * (bA * aQ + bQ * aC)
    ans += tmp * int(3**(bQ + aQ - 2))
    ans = ans % max_S

print(ans)

S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

S_list = [{"bA": t_A, "bQ": t_Q, "aC": t_C, "aQ": N_Q - t_Q}]
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    ba_dic = {}
    ba_dic["bA"] = t_A
    ba_dic["bQ"] = t_Q
    if(S[i:i + 1] == "?"):
        ba_dic["aQ"] = N_Q - t_Q - 1
    else:
        ba_dic["aQ"] = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    ba_dic["aC"] = t_C

    S_list.append(ba_dic)

ans = 0
for i in range(len(S)):
    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue

    bA = S_list[i]["bA"]
    bQ = S_list[i]["bQ"]
    aC = S_list[i]["aC"]
    aQ = S_list[i]["aQ"]

    tmp = 9 * bA * aC + bQ * aQ + 3 * (bA * aQ + bQ * aC)
    kk = tmp * int(3**(bQ + aQ - 2))
    ans = ans % max_S

print(ans)

S = input()

d = [0, 0, 0, 1]

max_ans = 10**9 + 7

for c in reversed(S):
    # print(c, d)
    m = [c == "A", c == "B", c == "C", c == "?"]
    if(m[3] is True):
        tmp = 3
    else:
        tmp = 1

    for j in range(3):
        d[j] = (tmp * d[j] + int(m[j] or m[3]) * d[j + 1]) % max_ans
    d[3] = (tmp * d[3]) % max_ans

print(d[0])

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: The _ABC number_ of a string T is the number of triples of integers (i, j, k) that satisfy all of the following conditions:    * 1 ≤ i < j < k ≤ |T| (|T| is the length of T.)   * T_i = `A` (T_i is the i-th character of T from the beginning.)   * T_j = `B`   * T_k = `C`  For example, when T = `ABCBC`, there are three triples of integers (i, j, k) that satisfy the conditions: (1, 2, 3), (1, 2, 5), (1, 4, 5). Thus, the ABC number of T is 3.  You are given a string S. Each character of S is `A`, `B`, `C` or `?`.  Let Q be the number of occurrences of `?` in S. We can make 3^Q strings by replacing each occurrence of `?` in S with `A`, `B` or `C`. Find the sum of the ABC numbers of all these strings.  This sum can be extremely large, so print the sum modulo 10^9 + 7.

Submission attempts (in order):
s = input()
dp = [[1, 0, 0, 0]]
for s in S:
    tmp = [0, 0, 0, 0]
    if s == 'A' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[1] += dp[-1][0]
    if s == 'B' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[2] += dp[-1][1]
    if s == 'C' or s == '?':
        tmp[0] += dp[-1][0]
        tmp[1] += dp[-1][1]
        tmp[2] += dp[-1][2]
        tmp[3] += dp[-1][3]
        tmp[3] += dp[-1][2]
    dp.append(tmp)
print(dp[-1][-1]%(10**9+7))

def main():
    S = input()
    mod = 10**9+7
    dp0 = 1
    dp1 = 0
    dp2 = 0
    dp3 = 0

    for s in S:
        tmp0 = dp0
        tmp1 = dp1
        tmp2 = dp2
        tmp3 = dp3

        if s == '?':
            tmp0 += 2*dp0 % mod
            tmp1 += (2*dp1 + dp0) % mod
            tmp2 += (2*dp2 + dp1) % mod
            tmp3 += (2*dp3 + dp2) % mod
        elif s == 'A':
            tmp1 += dp0 % mod
        elif s == 'B':
            tmp2 += dp1 % mod
        elif s == 'C':
            tmp3 += dp2 % mod
        dp0 = tmp0
        dp1 = tmp1
        dp2 = tmp2
        dp3 = tmp3

    print(dp3%(mod))
if __name__ == '__main__':
    main()

Verdicts: Runtime Error

Accepted