Problem p03290 (python)

Fixed submission:
import numpy as np

D,G = map(int, input().split())
P = []
C = []

for i in range(D):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

cnt = np.zeros(D,dtype=int)
P = np.array(P)
C = np.array(C)

ans = sum(P)
cnt_tar = 0

ind_list = np.arange(D)

for bit_seed in range(2**D):

    s_bit = (format(bit_seed, '#016b'))[::-1]
    bit_list = np.array(list(s_bit[:D]),dtype=int)

    cnt = P*bit_list
    num_base = np.sum(cnt)

    point_base_array = (P * (ind_list+1) * 100 + C) * bit_list
    point_base = np.sum(point_base_array)
#    print(point_base_array)

    if point_base >= G:
        num = num_base
        ans = min(ans,num)
    elif num_base > ans:
        continue
    else:
        for i,bit in enumerate(bit_list):
            if bit == 0:
                tar = i

        point_max = point_base + P[tar]*(tar+1)*100 + C[tar]
        if point_max >= G:

            tar_min = (G-point_base) // ((tar+1)*100)
            point = point_base + P[tar]*(tar+1)*100*tar_min

            if point < G:
                tar_min += 1

            if tar_min < P[tar]:
                num = num_base + tar_min
            else:
                num = num_base + P[tar]
            ans = min(ans,num)

print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

D,G = map(int, input().split())
P = []
C = []

for i in range(D):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

cnt = np.zeros(D,dtype=int)
P = np.array(P)
C = np.array(C)

ans = sum(P)
cnt_tar = 0

ind_list = np.arange(D)

if D < 11:
    for i in range(D):
        tar = i

        ind_list = list(range(D))
        ind_list.remove(tar)
        ind_list = np.array(ind_list)

        P_part = np.hstack((P[:tar], P[tar+1:]))
        C_part = np.hstack((C[:tar], C[tar+1:]))

        cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
        point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

        bit_list = np.ones(D-1,dtype=int)
        point_part_max = np.sum(((ind_list+1) * 100 * P_part + C_part)*bit_list)

        cnt_tar_min = max(0,(G - point_part_max)//((tar+1)*100))

        if cnt_tar_min > P[tar]:
            continue
        for cnt_tar in range(cnt_tar_min,P[tar]+1):
            point_base = cnt_tar*(tar+1)*100

            num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

            if point_base >= G or num_base >= ans:
                num = num_base
                ans = min(ans,num)
                break
            elif point_base + point_part_max >= G:

                for bit_seed in range(2**(D-1)):

                    s_bit = (format(bit_seed, '#011b'))[::-1]
                    bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                    cnt_part = P_part*bit_list
                    num = num_base + np.sum(cnt_part)
                    if num > ans:
                        continue

                    point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list
                    point = point_base + np.sum(point_part)

                    if point >= G:
                        ans = min(ans,num)

    print(ans)
    exit()

for bit_seed in range(2**D):

    s_bit = (format(bit_seed, '#016b'))[::-1]
    bit_list = np.array(list(s_bit[:D]),dtype=int)

    cnt = P*bit_list
    num_base = np.sum(cnt)

    point_base_array = (P * (ind_list+1) * 100 + C) * bit_list
    point_base = np.sum(point_base_array)
#    print(point_base_array)

    if point_base >= G:
        num = num_base
        ans = min(ans,num)
    elif num_base > ans:
        continue
    else:
        for i,bit in enumerate(bit_list):
            if bit == 0:
                tar = i

        point_max = point_base + P[tar]*(tar+1)*100 + C[tar]
        if point_max >= G:

            tar_min = (G-point_base) // ((tar+1)*100)
            point = point_base + P[tar]*(tar+1)*100

            if point < G:
                tar_min += 1

            if tar_min < P[tar]:
                num = num_base + tar_min
            else:
                num = num_base + P[tar]
            ans = min(ans,num)

print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

D,G = map(int, input().split())
P = []
C = []

for i in range(D):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

cnt = np.zeros(D,dtype=int)
P = np.array(P)
C = np.array(C)

ans = sum(P)
cnt_tar = 0

ind_list = np.arange(D)

if D < 10:
    for i in range(D):
        tar = i

        ind_list = list(range(D))
        ind_list.remove(tar)
        ind_list = np.array(ind_list)

        P_part = np.hstack((P[:tar], P[tar+1:]))
        C_part = np.hstack((C[:tar], C[tar+1:]))

        cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
        point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

        bit_list = np.ones(D-1,dtype=int)
        point_part_max = np.sum(((ind_list+1) * 100 * P_part + C_part)*bit_list)

        cnt_tar_min = max(0,(G - point_part_max)//((tar+1)*100))

        if cnt_tar_min > P[tar]:
            continue
        for cnt_tar in range(cnt_tar_min,P[tar]+1):
            point_base = cnt_tar*(tar+1)*100

            num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

            if point_base >= G or num_base >= ans:
                num = num_base
                ans = min(ans,num)
                break
            elif point_base + point_part_max >= G:

                for bit_seed in range(2**(D-1)):

                    s_bit = (format(bit_seed, '#011b'))[::-1]
                    bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                    cnt_part = P_part*bit_list
                    num = num_base + np.sum(cnt_part)
                    if num > ans:
                        continue

                    point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list
                    point = point_base + np.sum(point_part)

                    if point >= G:
                        ans = min(ans,num)

    print(ans)
    exit()

for bit_seed in range(2**D):

    s_bit = (format(bit_seed, '#016b'))[::-1]
    bit_list = np.array(list(s_bit[:D]),dtype=int)

    cnt = P*bit_list
    num_base = np.sum(cnt)

    point_base_array = (P * (ind_list+1) * 100 + C) * bit_list
    point_base = np.sum(point_base_array)
#    print(point_base_array)

    if point_base >= G:
        num = num_base
        ans = min(ans,num)
    elif num_base > ans:
        continue
    else:
        for i,bit in enumerate(bit_list):
            if bit == 0:
                tar = i

        point_max = point_base + P[tar]*(tar+1)*100 + C[tar]
        if point_max >= G:

            tar_min = (G-point_base) // ((tar+1)*100)
            point = point_base + P[tar]*(tar+1)*100

            if point < G:
                tar_min += 1

            if tar_min < P[tar]:
                num = num_base + tar_min
            else:
                num = num_base + P[tar]
            ans = min(ans,num)

print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

D,G = map(int, input().split())
P = []
C = []

for i in range(D):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

cnt = np.zeros(D,dtype=int)
P = np.array(P)
C = np.array(C)

ans = sum(P)
cnt_tar = 0

ind_list = np.arange(D)

if D < 8:
    for i in range(D):
        tar = i

        ind_list = list(range(D))
        ind_list.remove(tar)
        ind_list = np.array(ind_list)

        P_part = np.hstack((P[:tar], P[tar+1:]))
        C_part = np.hstack((C[:tar], C[tar+1:]))

        cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
        point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

        bit_list = np.ones(D-1,dtype=int)
        point_part_max = np.sum(((ind_list+1) * 100 * P_part + C_part)*bit_list)

        cnt_tar_min = max(0,(G - point_part_max)//((tar+1)*100))

        if cnt_tar_min > P[tar]:
            continue
        for cnt_tar in range(cnt_tar_min,P[tar]+1):
            point_base = cnt_tar*(tar+1)*100

            num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

            if point_base >= G or num_base >= ans:
                num = num_base
                ans = min(ans,num)
                break
            elif point_base + point_part_max >= G:

                for bit_seed in range(2**(D-1)):

                    s_bit = (format(bit_seed, '#011b'))[::-1]
                    bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                    cnt_part = P_part*bit_list
                    num = num_base + np.sum(cnt_part)
                    if num > ans:
                        continue

                    point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list
                    point = point_base + np.sum(point_part)

                    if point >= G:
                        ans = min(ans,num)

    print(ans)
    exit()

for bit_seed in range(2**D):

    s_bit = (format(bit_seed, '#016b'))[::-1]
    bit_list = np.array(list(s_bit[:D]),dtype=int)

    cnt = P*bit_list
    num_base = np.sum(cnt)

    point_base_array = (P * (ind_list+1) * 100 + C) * bit_list
    point_base = np.sum(point_base_array)
#    print(point_base_array)

    if point_base >= G:
        num = num_base
        ans = min(ans,num)
    elif num_base > ans:
        continue
    else:
        for i,bit in enumerate(bit_list):
            if bit == 0:
                tar = i

        point_max = point_base + P[tar]*(tar+1)*100 + C[tar]
        if point_max >= G:

            tar_min = (G-point_base) // ((tar+1)*100)
            point = point_base + P[tar]*(tar+1)*100

            if point < G:
                tar_min += 1

            if tar_min < P[tar]:
                num = num_base + tar_min
            else:
                num = num_base + P[tar]
            ans = min(ans,num)

print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

D,G = map(int, input().split())
P = []
C = []

for i in range(D):
#    p,c = min(100,(i+1)*20),1000*(i+1)#map(int,input().split())
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

cnt = [0 for _ in range(D)]

ans = sum(P)
cnt_tar = 0

for i in range(D):
    tar = i

    ind_list = list(range(D))
    ind_list.remove(tar)
    ind_list = np.array(ind_list)

    P_part = np.array(P[:tar] + P[tar+1:])
    C_part = np.array(C[:tar] + C[tar+1:])

    cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
    point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

    bit_list = np.ones(D-1,dtype=int)
    point_part_max = np.sum(((ind_list+1) * 100 * P_part + C_part)*bit_list)

    cnt_tar_min = max(0,(G - point_part_max)//((tar+1)*100))

    if cnt_tar_min > P[tar]:
        continue
    for cnt_tar in range(cnt_tar_min,P[tar]+1):
        point_base = cnt_tar*(tar+1)*100

        num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

        if point_base >= G or num_base >= ans:
            num = num_base
            ans = min(ans,num)
            break
        elif point_base + point_part_max >= G:

            for bit_seed in range(2**(D-1)):

                s_bit = (format(bit_seed, '#011b'))[::-1]
                bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                cnt_part = P_part*bit_list
                num = num_base + np.sum(cnt_part)
                if num > ans:
                    continue

                point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list
                point = point_base + np.sum(point_part)

                if point >= G:
                    ans = min(ans,num)

print(ans)
#     while cnt_part != P_part:
#     ind = 0

#     cnt = kuriage(cnt,P,ind,tar,C,G)
#     print(cnt)
#     if cnt[tar] == -1:
#         cnt = [0 for _ in range(D)]
#         tar += 1

#     if point_over(cnt,P,C,G) and ans > sum(cnt):
#         ans = min(ans, sum(cnt))
# #            print(ans)

# print(ans)


# def kuriage(cnt,P,ind,tar,C,G):

#     if cnt[ind] == 0:
#         cnt[ind:ind+1] = P[ind:ind+1]
#     elif cnt[ind] == P[ind]:
#         if 0 in cnt[:tar] and 0 in cnt[tar+1:]:
#             if ind+1 == tar:
#                 kuriage(cnt,P,ind+2, tar, C, G)
#             else:
#                 kuriage(cnt,P,ind+1, tar, C, G)
#         else:
#             if C[tar] != P[tar]:
#                 C[tar] = C[tar] + 1
#             else:
#                 C[tar] = -1
#     return cnt
# def point_over(cnt,P,C,G):
#     point = 0
#     for i in range(len(P)):
#         point += cnt[i]*100*(i+1)
#         if cnt[i] == P[i]:
#             point += C[i]

#         if point >= G:
#             return True

#     if point < G:
#         return False

# def point(cnt,P,C):
#     point = 0

#     for i,cnt_s in enumerate(cnt):
#         print(cnt_s,'ok')
#         if cnt_s == 0:
#             point += 0
#         else:
#             point += cnt[i]*100*(i+1) + C[i]
#     return point

Buggy submission (verdict: Runtime Error):
import numpy as np

D,G = map(int, input().split())
P = []
C = []

for i in range(D):
#    p,c = min(100,(i+1)*20),1000*(i+1)#map(int,input().split())
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

cnt = [0 for _ in range(D)]

ans = sum(P)
cnt_tar = 0

for i in range(D):
    tar = i

    ind_list = list(range(D))
    ind_list.remove(tar)
    ind_list = np.array(ind_list)

    P_part = np.array(P[:tar] + P[tar+1:])
    C_part = np.array(C[:tar] + C[tar+1:])

    cnt_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]
    point_part = np.zeros(D-1,dtype=int)#[0 for _ in range(D-1)]

    bit_list = np.ones(D-1,dtype=int)
    point_part_max = np.sum(((ind_list+1) * 100 * P_part + C_part)*bit_list)

    cnt_tar_min = max(0,(G - point_part_max)//((tar+1)*100))

    for cnt_tar in range(cnt_tar_min,P[tar]+1):
        point_base = cnt_tar*(tar+1)*100

        num_base   = cnt_tar + C[tar]*max(0,cnt_tar-P[tar] + 1)

        if point_base >= G or num_base >= ans:
            num = num_base
            ans = min(ans,num)
            break
        elif point_base + point_part_max >= G:

            for bit_seed in range(2**(D-1)):

                s_bit = (format(bit_seed, '#011b'))[::-1]
                bit_list = np.array(list(s_bit[:D-1]),dtype=int)

                cnt_part = P_part*bit_list
                num = num_base + np.sum(cnt_part)
                if num > ans:
                    continue

                point_part = cnt_part * (ind_list+1) * 100 + C_part*bit_list
                point = point_base + np.sum(point_part)

                if point >= G:
                    ans = min(ans,num)

print(ans)
#     while cnt_part != P_part:
#     ind = 0

#     cnt = kuriage(cnt,P,ind,tar,C,G)
#     print(cnt)
#     if cnt[tar] == -1:
#         cnt = [0 for _ in range(D)]
#         tar += 1

#     if point_over(cnt,P,C,G) and ans > sum(cnt):
#         ans = min(ans, sum(cnt))
# #            print(ans)

# print(ans)


# def kuriage(cnt,P,ind,tar,C,G):

#     if cnt[ind] == 0:
#         cnt[ind:ind+1] = P[ind:ind+1]
#     elif cnt[ind] == P[ind]:
#         if 0 in cnt[:tar] and 0 in cnt[tar+1:]:
#             if ind+1 == tar:
#                 kuriage(cnt,P,ind+2, tar, C, G)
#             else:
#                 kuriage(cnt,P,ind+1, tar, C, G)
#         else:
#             if C[tar] != P[tar]:
#                 C[tar] = C[tar] + 1
#             else:
#                 C[tar] = -1
#     return cnt
# def point_over(cnt,P,C,G):
#     point = 0
#     for i in range(len(P)):
#         point += cnt[i]*100*(i+1)
#         if cnt[i] == P[i]:
#             point += C[i]

#         if point >= G:
#             return True

#     if point < G:
#         return False

# def point(cnt,P,C):
#     point = 0

#     for i,cnt_s in enumerate(cnt):
#         print(cnt_s,'ok')
#         if cnt_s == 0:
#             point += 0
#         else:
#             point += cnt[i]*100*(i+1) + C[i]
#     return point