TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.readline().split(),dtype=np.int64)

a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]

print(neg,zero,pos)
def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


left=-10**18
right=10**18

while left+1<right:
    x=(left+right)//2
    out=count(x)
    print(out)
    if out>=k:
        right=x
    if out<k:
        left=x

print(right)


import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.readline().split(),dtype=int)

a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]

print(neg,zero,pos)
def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


left=-10**18
right=10**18

while left+1<right:
    x=(left+right)//2
    out=count(x)
    print(out)
    if out>=k:
        right=x
    if out<k:
        left=x

print(right)


import sys

n=sys.stdin.readline().rstrip()[::-1]
to=0
num=len(n)
m=0

for i in range(num):
    k=int(n[i])
    k+=m
    if k==5:
        if int(n[i+1])>=5:
            to+=10-k
            m=1
        else:
            to+=k
            m=0
    if k<5:
        to+=k
        m=0
    elif k>5:
        to+=10-k
        m=1
        if i==num-1:
            to+=1
        
print(to)


import numpy as np
import sys

n,k,*a=map(int,sys.stdin.readlines().split())
a=np.array(a,dtype=np.int64)

print(n,k,a)

a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]

print(np.searchsorted(a,0//pos,side='right').sum())

def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


left=-10**18
right=10**18

while left+1<right:
    x=(left+right)//2
    cnt=count(x)
    if cnt>=k:
        right=x
    if cnt<k:
        left=x

print(right)


import numpy as np
import sys

n,k=map(int,sys.stdin.readline().split())
a=np.array(sys.stdin.read().split(),dtype=np.int64)

a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]

def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2


left=-10**18
right=10**18

while left+1<right:
    x=(left+right)//2
    out=count(x)
    if out>=k:
        right=x
    if out<k:
        left=x

print(right)


Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
N,K = map(int,input().split())
a = list(map(int,input().split())

d = []
for i in range(N):
  for j in range(N):
    if j == i:
      continue
    else:
      d.append(a[i]*a[j])
      
print(sorted(d)[K-1])

N,K = map(int,input().split())
a = list(map(int),input().split())

d = []
for i in range(N):
  for j in range(N):
    if j == i:
      continue
    else:
      d.append(a[i]*a[j])
      
print(sorted(d)[K-1])

import numpy as np

N,K = map(int,input().split())
a = list(map(int, input().split()))

b = np.tile(a,N).reshape(N,-1).astype('float128')
c = np.tril(b * b.T, k=-1)
d = c + np.tri(N).T * np.max(c)

print(d)
print(int(sorted(d.flatten())[K-1]))

N,K = map(int,input().split())
a = list(map(int,input().split()))

d = []
for i in range(N):
  for j in range(N):
    if j == i:
      continue
    else:
      d.append(a[i]*a[j])
      
print(sorted(d)[K-1])

import numpy as np
N,K = map(int,input().split())
a = np.array(input().split(),np.int64)
zero = a[a==0]
pos = a[a>0]
neg = a[a<0]

def f(x):
    count = 0
    c = x // pos
    count += np.searchsorted(a, c, side='right').sum()
    count += N*len(zero) if x >= 0 else 0
    c = -(-x // neg)
    count += (N - np.searchsorted(a, c, side='left')).sum()
    count -= a[a*a <= x].size
    count //= 2
    return count

right = 10**18
left = -10**18
while right-left>1:
    mid = (right + left)//2
    if f(mid)<K:
        left = mid
    else:
        right = mid
        
print(right)

N,K = map(int,input().split())
a = list(map(int,input().split()))

d_plus = sorted([i for i in a if i>=0])
d_minus = sorted([i for i in a if i<0])

d = []
if len(d_plus)*len(d_minus) <= K:
  for i in d_plus:
    for j in d_minus:
      d.append(i*j)
  print(sorted(d)[K-1])
else:
  for i in range(len(d_plus)):
    for j in range(len(d_plus)):
      if i==j:
        continue
      else:
        d.append(d_plus[i]*d_plus[j])
  for i in range(len(d_minus)):
    for j in range(len(d_minus)):
      if i==j:
        continue
      else:
        d.append(d_minus[i]*d_minus[j])
  print(sorted(d)[K-1-len(d_plus)*len(d_minus)])
      

import numpy as np
N,K = map(int,input().split())
a = np.array(input().split(),np.int64)
a = np.sort(a)
zero = a[a==0]
pos = a[a>0]
neg = a[a<0]

def f(x):
    count = 0
    c = x // pos
    count += np.searchsorted(a, c, side='right').sum()
    count += N*len(zero) if x >= 0 else 0
    c = -(-x // neg)
    count += (N - np.searchsorted(a, c, side='left')).sum()
    count -= a[a*a <= x].size
    count //= 2
    return count

right = 10**18
left = -10**18
while right-left>1:
    mid = (right + left)//2
    if f(mid)<K:
        left = mid
    else:
        right = mid
        
print(right)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
def main():
  import sys
  import numpy as np

  sr = lambda: sys.stdin.readline().rstrip()
  ir = lambda: int(sr())
  lr = lambda: list(map(int, sr().split()))

  N, M = lr()
  A = np.array(lr())
  A.sort()
  Am=A[A<0]
  Az=A[A==0]
  Ap=A[A>0]
  l1=len(Az)
  l2=len(Am)

  def shake_cnt(x):
    X =np.searchsorted(Ap, x/Ap)
    print(X)
    Y =np.searchsorted(Am, -x/Am,side='right')
    if x<=0:
      ans=l1*N
    else:
      ans=0
    return N*(N-1)//2 - ans - X.sum() -l2+Y.sum()
      

  right = 10**6
  left = 0
  while right > left + 1:
      mid = (right+left) // 2
      if shake_cnt(mid) >= M:
        left = mid
      else:
        right = mid
  
  print(right)
if __name__=='__main__':
  main()


def main():
    import numpy as np
    from bisect import bisect_left,bisect_right
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=np.array(A)
    A=np.sort(A)
    Ap=A[A>0]
    Az=A[A==0]
    Am=A[A<0]   
    lm,lz,lp=len(Am),len(Az),len(Ap)
    Am2=Am**2
    Ap2=Ap**2
    
    def cnt_product(x): 
        if x<0:
            X=np.searchsorted(Am,x//Ap,side='right')
            #print(X)
            return X.sum()
        
        else:
            ans=lz*(n-lz)+lz*(lz-1)//2+lp*lm

            X=np.searchsorted(Ap,x//Ap,side='right')
            Xd=np.count_nonzero(Ap2<=x)

            Y=np.searchsorted(Am,(-x-1)//(-Am),side='right')
            Yd=np.count_nonzero(Am2<=x)
            
            ans+=(X.sum()-Xd+lm**2-Y.sum()-Yd)//2
            return ans

    left=-10**18
    right=10**18
    while right-left>1:
        mid=(left+right)//2
        if cnt_product(mid)<k:
            left=mid
        else:
            right=mid
    print(right)

if __name__=='__main__':
    main()

Verdicts: Wrong Answer

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
import math
import itertools
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,k=map(int,input().split())
a=list(map(int, input().split()))
a=sorted(a)
mlist=[]
zlist=[]
plist=[]
for i in a:
  if i<0:
    mlist.append(i)
  elif i==0:
    zlist.append(i)
  else:
    plist.append(i)
mnum=len(mlist)
znum=len(zlist)
pnum=len(plist)
mans=mnum*pnum
zans=znum*(pnum+mnum)
if znum>=2:
  zans+=combinations_count(znum,2)
pans=0
if pnum>=2:
  pans+=combinations_count(pnum,2)
if mnum>=2:
  pans+=combinations_count(mnum,2)

if k<mans:
  ans=[]
  l=mlist[0]*plist[-1]
  r=mlist[-1]*plist[0]
  while True:
    x=(l+r)//2
    c=0
    for m in mlist:
      for p in plist[::-1]:
        if m*p<x:
          c+=1
        else:
          break
    if c<k:
      l=x
    else:
      r=x
    if r==l+1:
      break
  print(l)
elif k<mans+zans:
  print(0)
else:
  k=k-(mans+zans)
  mlist=mlist[::-1]
  if mnum<2:
    l=plist[0]*plist[1]
    r=plist[-1]*plist[-2]
  elif pnum<2:
    l=mlist[0]*mlist[1]
    r=mlist[-1]*mlist[-2]
  else:
    if mlist[0]*mlist[1]<plist[0]*plist[1]:
      l=mlist[0]*mlist[1]
    else:
      l=plist[0]*plist[1]
    if mlist[-1]*mlist[-2]>plist[-1]*plist[-2]:
      r=mlist[-1]*mlist[-2]
    else:
      r=plist[-1]*plist[-2]
  #print(k)
  while True:
    x=(l+r)//2
    c=0
    max=0
    if mnum>=2:
      for i,m in enumerate(mlist[:-1]):
        for j in mlist[i:]:
          n=m*j
          if n<x:
            c+=1
            if n>=max:max=n
          else:
            break
    if pnum>=2:
      for i,p in enumerate(plist[:-1]):
        for j in plist[i:]:
          n=p*j
          if n<x:
            c+=1
            if n>=max:max=n
          else:
            break
    #print("c"+str(c))
    if c<k:
      l=x
      #print("l"+str(l))
    else:
      r=x
      #print("r"+str(r))
    if r==l+1:
      break
    if c==k:break
  print(l)

import numpy as np
import sys
 
n,k=map(int,sys.stdin.readline().split())
a=np.array(list(map(int, input().split())))
 
a.sort()
neg=a[a<0]
zero=a[a==0]
pos=a[a>0]
 
def count(x):
    cnt=0
    if x>=0:
        cnt+=len(zero)*n
    cnt+=np.searchsorted(a,x//pos,side='right').sum()
    cnt+=(n-np.searchsorted(a,(-x-1)//(-neg),side='right')).sum()
    cnt-=np.count_nonzero(a*a<=x)
    return cnt//2
 
 
left=-10**18
right=10**18
 
while left+1<right:
    x=(left+right)//2
    out=count(x)
    if out>=k:
        right=x
    if out<k:
        left=x
print(right)

Verdicts: Runtime Error

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
import sys
input = sys.stdin.readline
import numpy as np

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = np.array(sorted([abs(int(x)) for x in A if x < 0]), np.int64)
N_m = len(A_m)

A_p = np.array(sorted([int(x) for x in A if x > 0]), np.int64)
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = np.searchsorted(A_m, x / A_p, side="right").sum()
    return cnt

if K <= M:
    left = -1
    right = 10 ** 6
    
    left = -10 ** 18
    right = 10 ** 18
    while left + 1 < right:
        x = (left + right) // 2
        if cnt_M(x) >= K:
            right = x
        else:
            left = x
 
    print(-left)
    sys.exit()
K -= (M + Z)
def cnt_P(x):
    cnt = 0
    ng = 0
    cnt += np.searchsorted(A_m, x / A_m, side="right").sum()
    cnt += np.searchsorted(A_p, x / A_p, side="right").sum()
    ng = np.count_nonzero(A_m * A_m <= x) + np.count_nonzero(A_p * A_p <= x)
    return (cnt - ng) // 2

left = -1
right = 1 + 10 ** 18

left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if cnt_P(x) >= K:
        right = x
    else:
        left = x
 
print(right)


import sys
input = sys.stdin.readline
import numpy as np

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

A_m = np.array(sorted([abs(int(x)) for x in A if x < 0]), np.int64)
N_m = len(A_m)

A_p = np.array(sorted([int(x) for x in A if x > 0]), np.int64)
N_p = len(A_p)

M = N_m * N_p
P = (1 / 2) * (N_m) * (N_m - 1) + (1 / 2) * (N_p) * (N_p - 1)
Z = (1 / 2) * N * (N - 1) - (M + P)

if M < K <= M + Z:
    print(0)
    sys.exit()

def cnt_M(x):
    cnt = np.searchsorted(A_m, x // A_p, side="right").sum()
    return cnt >= M - K + 1

if K <= M:
    left = -1 -10 ** 18
    right = 1 + 10 ** 18
    while right - left> 1:
        mid = (left + right) // 2
        if cnt_M(mid):
            right = mid
        else:
            left = mid
 
    print(-right)
    sys.exit()

K -= (M + Z)
def cnt_P(x):
    cnt = 0
    ng = 0
    cnt += np.searchsorted(A_m, x // A_m, side="right").sum()
    cnt += np.searchsorted(A_p, x // A_p, side="right").sum()
    ng = np.count_nonzero(A_m * A_m <= x) + np.count_nonzero(A_p * A_p <= x)
    cnt = (cnt - ng) // 2
    return cnt >= K

left = -1 - 10 ** 18
right = 1 + 10 ** 18

while right - left > 1:
    mid = (left + right) // 2
    if cnt_P(mid):
        right = mid
    else:
        left = mid
print(right)

Verdicts: Wrong Answer

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
n,k=map(int,input().split())
a=np.sort(np.array(list((map(int,input().split())))))
q=len(a[a==0])
d=a[a<0]
e=a[a>0]
l,r=10**18,-10**18
while l-r>1:
    t=(l+r)//2
    p=0
    if t>=0:
        p+=q*n
    p+=np.searchsorted(a,t//e,side="right").sum()+(n-np.searchsorted(a,(-t-1)//(-d),side="right")).sum()
    p-=np.count_nonzero(a*a<=t)
    p//=2
    if p>=k:
        l=t
    else:
        r=t
print(r)

import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
n,k=map(int,input().split())
a=np.sort(np.array(list((map(int,input().split())))))
q=len(a[a==0])
d=a[a<0]
e=a[a>0]
l,r=10**18,-10**18
while l-r>1:
    t=(l+r)//2
    p=0
    if t>=0:
        p+=q*n
    p+=np.searchsorted(a,t//e,side="right").sum()+(n-np.searchsorted(a,(-t-1)//(-d),side="right")).sum()
    p-=np.count_nonzero(a*a<=t)
    p//=2
    if p>=k:
        l=t
    else:
        r=t
print(l)

Verdicts: Wrong Answer

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,K = map(int,input().split())
    a = np.array(list(map(int,input().split())))
    a.sort()
    posi,zero,nega = a[a>0],a[a==0],a[a<0]

    lp,lz,ln = len(posi),len(zero),len(nega)
    
    def ch(x):
        count = 0
        if x >= 0:
            count += lz*N
        count += np.searchsorted(a,x//posi,side="right").sum()
        count += (N-np.searchsorted(a,np.ceil(x//nega))).sum()
        count -= np.count_nonzero(a**2<=x)
        return count//2

    l,r = -10**18-1,10**18+1
    while r-l > 1:
        mid = (r+l)//2
        if ch(mid) >= K:
            r = mid
        else:
            l = mid

    print(r)
    
if __name__ == "__main__":
    main()


import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    
    posi,zero,nega = [],[],[]
    for num in a:
        if num > 0:
            posi.append(num)
        elif num == 0:
            zero.append(num)
        else:
            nega.append(num)
            
    lp,lz,ln = len(posi),len(zero),len(nega)
    posi.sort(),nega.sort()
    posi,zero,nega = np.array(posi),np.array(zero),np.array(nega)
    _nega = nega[::-1]*(-1)
    
    def ch(x):
        if x == 0:
            return (lz*(lz-1))//2+lz*(lp+ln)+lp*ln
        elif x > 0:
            count = (lz*(lz-1))//2+lz*(lp+ln)+lp*ln
            puse = np.searchsorted(posi,(x//posi),side="right")
            pdup = np.count_nonzero(posi**2<=x)
            nuse = np.searchsorted(_nega,x//_nega,side="right")
            ndup = np.count_nonzero(_nega**2<=x)
            return (np.sum(puse)+np.sum(nuse)-pdup-ndup)//2+count
        else:
            count = np.searchsorted(nega,x//posi,side="right")
            return np.sum(count)

    l,r = -10**18-1,10**18+1
    while r-l > 1:
        mid = (r+l)//2
        if ch(mid) >= K:
            r = mid
        else:
            l = mid
    print(r)
    
if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
n,k=map(int,input().split())
a=list(map(int,input().split()))
from math import log2
from bisect import bisect_left,bisect_right
a.sort()

mn=bisect_left(a,0)

zn=bisect_right(a,0)-mn

pn=n-mn-zn
am=a[:mn]
am=[-x for x in am[::-1]]
ap=a[mn+zn:]


def func(x):
    cnt=0
    if x>0:
        cnt+=mn*pn
        cnt+=(zn*(n-1+n-zn))//2
        cnt1=0
        for y in ap:
            cnt1+=bisect_left(ap,(x+y-1)//y)
            if y**2<x:cnt1-=1
        for y in am:
            cnt1+=bisect_left(am,(x+y-1)//y)
            if y**2<x:cnt1-=1
        cnt+=cnt1//2
    elif x<0:
        x=abs(x)
        for y in ap:
            cnt+=mn-bisect_right(am,(x+y-1)//y)
    elif x==0:
        cnt+=mn*pn
    return cnt<k

maxaa=max(abs(a[0]),abs(a[-1]))**2
l,r=-maxaa,maxaa
while r-l>1:
    x=(l+r)//2
    if func(x):
        l,r=x,r
    else:
        l,r=l,x
print(r if func(r) else l)



import numpy as np
n,k=map(int,input().split())
a=np.array(list(map(int,input().split())))
a.sort()
p=a[a>0]
z=np.count_nonzero(a==0)
m=a[a<0]
r=10**19
l=-r
while r-l>1:
    
    
    b=(l+r)//2
    c=0
    if b>=0:
        c+=z*n
    
    c+=a.searchsorted(b//p,side='right').sum()
    
    c+=n*len(m)-a.searchsorted(-(-b//m),side='left').sum()
    c-=np.count_nonzero(a*a<=b)
    if c//2>=k:
        r=b
    else:
        l=b
print(r)


Verdicts: Wrong Answer

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
import sys

N, K = map(int, input().split())
a = sorted(list(map(int, input().split())))
l = -(((1e18)+1)
r=(1e18)+1
while(l + 1 < r):
    x=(l + r) / 2
    total=0
    for i in range(N):
        if a[i] < 0:
            l=-1
            r=N
            while(l + 1 < r):
                c=(l + r) / 2
                if a[c] * a[i] < x:
                    r=c
                else:
                    l=c
            total += n - r
        else:
            l=-1
            r=N
            while(l + 1 < r):
                c=(l + r) / 2
                if a[c] * a[i] < x:
                    l=c
                else:
                    r=c
            total += r
        if a[i] * a[i] < x:
            total -= 1
    total /= 2
    if total < K:
        l=x
    else:
        r=x
print(l)


import numpy as np

n, k = map(int, input().split())

A = np.array(input().split(), np.int64)

A.sort()

posA = A[A > 0]
negA = A[A < 0]
zeros = (A==0).sum()

left = -10**18
right = 10**18

while left+1 < right:
    num = (left+right)//2
    
    less_count = 0
    
    if num >= 0:
        less_count += zeros * n
    
    limit_pair_for_pos = num // posA
    limit_idxs = np.searchsorted(A, limit_pair_for_pos, side='right')
    less_count += limit_idxs.sum()

    limit_pair_for_neg = -(num // -negA)
    limit_idxs = n - np.searchsorted(A, limit_pair_for_neg, side='left')
    less_count += limit_idxs.sum()

    duplicate_cases = (A**2 <= num).sum()
    less_count -= duplicate_cases
    less_count //= 2
    
    if less_count >= k:
        right = num
    else:
        left = num

print(right)


Verdicts: Runtime Error

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
import numpy as np
N,K = map(int,input().split())
A = np.array([int(i) for i in input().split()])

posi = A[A>0]
zero = A[A==0]
nega = A[A<0]


def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # count 0
    if x >= 0:
        cnt_tpl += len(zero) * N
    
    cnt_tpl += np.searchsorted(A, x//pos, side='right').sum()
    
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    # remove a^2
    cnt_tpl -= np.count_nonzero(A*A <= x)
    return cnt_tpl // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x
 
print(right)

import numpy as np
N,K = map(int,input().split())
A = np.array([int(i) for i in input().split()])

print(N,K,A)

A = np.sort(A)
posi = A[A>0]
zero = A[A==0]
nega = A[A<0]

def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # count 0
    if x >= 0:
        cnt_tpl += len(zero) * N
    
    cnt_tpl += np.searchsorted(A, x//posi, side='right').sum()
    
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-nega), side='right')).sum()
    # remove a^2
    cnt_tpl -= np.count_nonzero(A*A <= x)
    return cnt_tpl // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x

print(right)

import numpy as np
N,K = map(int,input().split())
A = np.array([int(i) for i in input().split()])


A = np.sort(A)
posi = A[A>0]
zero = A[A==0]
nega = A[A<0]

def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # count 0
    if x >= 0:
        cnt_tpl += len(zero) * N
    
    cnt_tpl += np.searchsorted(A, x//posi, side='right').sum()
    
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-nega), side='right')).sum()
    # remove a^2
    cnt_tpl -= np.count_nonzero(A*A <= x)
    return cnt_tpl // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x

print(right)

Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
from sys import stdin
#f_i = stdin
f_i = open('test_in_3')#

import numpy as np

N, K = map(int, f_i.readline().split())
A = np.array(f_i.read().split(), dtype=int)

A = np.sort(A)
zero_left = A.searchsorted(0, side='left')
zero_right = A.searchsorted(0, side='right')
zero_cnt = zero_right - zero_left
pos = A[zero_right:]
neg = A[:zero_left]

def f(x):
    cnt = 0
    
    if x >= 0:
        cnt += zero_cnt * N
    
    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    
    cnt -= np.count_nonzero(A ** 2 <= x)
    return cnt // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x

print(right)

from sys import stdin
f_i = stdin

import numpy as np

N, K = map(int, f_i.readline().split())
A = np.array(f_i.read().split(), dtype=int)

A = np.sort(A)
zero_left = A.searchsorted(0, side='left')
zero_right = A.searchsorted(0, side='right')
zero_cnt = zero_right - zero_left
pos = A[zero_right:]
neg = A[:zero_left]

def f(x):
    cnt = 0
    
    if x >= 0:
        cnt += zero_cnt * N
    
    cnt += np.searchsorted(A, x // pos, side='right').sum()
    cnt += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    
    cnt -= np.count_nonzero(A ** 2 <= x)
    return cnt // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x

print(right)

Verdicts: Runtime Error

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
from bisect import bisect_left

n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if mc * pc < k <= mc * pc + z * (n-z) + z * (z-1) // 2:
    print(0)
    exit()

print('dummy')

from bisect import bisect_left

n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if mc * pc < k <= mc * pc + z * (n-z) + z * (z-1) // 2:
    print(0)

print('dummy')

import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)

a = np.sort(a)

u = a[a > 0]
d = a[a < 0]
z = len(a[a == 0])

if len(u) * len(d) < k <= len(u) * len(d) + z * (n-z) + z * (z-1) // 2:
    print(0)
    exit()

L = - 10 ** 18
H = 10 ** 18

while H - L > 1:
    M = (H + L) // 2
    count = 0
    if M > 0:
        count += z * n
    count += np.searchsorted(a, M // u, side='right').sum()
    count += (n - np.searchsorted(a, (- M - 1) // (- d), side='right')).sum()
    count -= np.count_nonzero(a * a <= M)
    count //= 2
    #print(count)
    if count >= k:
        H = M
    else:
        L = M

print(H)

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):

import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a) 
a.sort()

def count(x): 
  ans = 0
  for i in a:
    ans -= i * i <= x 
    if i == 0:
      if x >= 0:
        ans += n
    elif i > 0:
      ans += np.searchsorted(a, x // i, side="right") 
    else:
      ans += n - np.searchsorted(a, x // i, side="left")
  return ans // 2

ok = 10**18
ng = -ok - 1
while ok - ng > 1: 
  cen = (ok + ng) // 2
  if count(cen) >= k:
    ok = cen
  else:
    ng = cen
print(ok)


import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a) 
a.sort()

zero = np.count_nonzero(a == 0)
positive = a[a > 0] 
negative = a[a < 0]

def count(x): 
  ans = 0
  if x >= 0: 
    ans += n * zero
  ans += np.searchsorted(a, x // positive, side="right").sum() 
  ans += n * len(negative) - np.searchsorted(a, -(-x // negative), side="left").sum() 
  ans -= np.count_nonzero(a * a <= x) 
  return ans // 2

ok = 10**18
ng = -ok - 1
while ok - ng > 1: 
  cen = (ok + ng) // 2
  if count(cen) >= k:
    ok = cen
  else:
    ng = cen
print(ok)

Verdicts: Wrong Answer

Accepted
Problem: We have N integers A_1, A_2, ..., A_N.  There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Submission attempts (in order):
n = [int(_) for _ in list(input())]
a, b = 0, 1
for i in n:
    a, b = min(a+i, b+10-i), min(a+(i+1), b+10-(i+1))
print(a)

import numpy as np

def count_pair(x):
    cnt = 0
    cnt += (n-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        cnt += len(A_zero)*n
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt

n, k = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)


import numpy as np

def count_pair(x):
    cnt = 0
    cnt += (n-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        cnt += len(A_zero)*n
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt

n, k = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < k:
        l = c
    else:
        r = c
print(l)


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):
#from math import sqrt
#from heapq import heappush, heappop
#from collections import deque

#a, b = [int(v) for v in input().split()]

n = input()


count = 0
top = True
for i in n:
    i = int(i)
    if i <= 5:
        count += i
    else:
        if top:
            count += 1 + (10 - i)
        else:
            count += 10 - i
    top = False

print(count)


#from math import sqrt
#from heapq import heappush, heappop
#from collections import deque

#a, b = [int(v) for v in input().split()]

n = input()

flag = 0
count = 0
for i in range(len(n) - 1, -1, -1):
    c = n[i]
    v = int(c) + flag

    if v == 10:
        v = 0
        flag = 1
    else:
        flag = 0
    if v < 5:
        count += v
    elif v == 5:
        if i != 0 and int(n[i-1]) >= 5:
            flag = 1
        count += 5
    else:
        count += 10 - v
        flag = 1
print(count + flag)


Verdicts: Wrong Answer

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):



# in your code
import numpy as np
DBG=0
def p(*args, **kargs):
    if DBG:print(*args, **kargs)
read = input 
rn = lambda :list(map(int, read().split()))

def sol(s):
    dp = 0, 1 # n, n + 1
    for x in map(int, s):
        c, d = dp
    
        
        
        a = min(c + x,    d + 10 - x)# for ...n
        
        b = min(c + x + 1,d + 10 - 1 - x )# for ...(n+1)
        
        
        dp = a,b
        p(dp)
    return dp[0]
if DBG:
    pass
#     sol("100")



sol(read())




# in your code
import numpy as np
DBG=0
def p(*args, **kargs):
    if DBG:print(*args, **kargs)
read = input 
rn = lambda :list(map(int, read().split()))

def sol(s):
    dp = 0, 1 # n, n + 1
    for x in map(int, s):
        c, d = dp
    
        
        
        a = min(c + x,    d + 10 - x)# for ...n
        
        b = min(c + x + 1,d + 10 - 1 - x )# for ...(n+1)
        
        
        dp = a,b
        p(dp)
    return dp[0]
if DBG:
    pass
#     sol("100")



print(sol(read()))

Verdicts: Wrong Answer

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):
N = [int(x) for x in input()]+[0]
count = 0
for i in range(len(N)-1, 0, -1):
    if N[i] <= 4 or (N[i] == 5 and N[i-1] <= 4):
        count += N[i]
    else:
        count += 10 - N[i]
        N[i-1] = N[i-1] + 1
print(count)

N = list(map(int, input()))
N.insert(0, 0)
count = 0
for i in range(len(N)-1, -1, -1):
    if N[i] <= 4 or (N[i] == 5 and N[i-1] <= 4):
        count += N[i]
    else:
        count += 10 - N[i]
        N[i-1] = N[i-1] + 1
print(count)

Verdicts: Wrong Answer

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):
prev = 0
for i in range(len(N)):
  if 0 <= int(N[i]) + prev < 5:
    count += int(N[i]) + prev
    prev = 0
  elif 6 <= int(N[i]) + prev <= 9:
    count += 10 - (int(N[i]) + prev)
    prev = 1
  elif int(N[i]) + prev == 10:
    prev = 1
  else:
    if i < (len(N) - 1) and int(N[i+1]) < 5:
      count += 5
      prev = 0
    else:
      count += 5
      prev = 1
count = count + prev

N = input()
count = 0
prev = 0
for i in range(len(N)):
  if 0 <= int(N[i]) + prev < 6:
    count += int(N[i]) - prev
    prev = 0
  elif: 6 <= int(N[i]) + prev <= 9:
    count += 11 - (int(N[i]) - prev)
    prev = 1
  else:
    prev = 1
print(count)

N = input()
count = 0
prev = 0
for i in range(len(N)):
  if 0 <= int(N[i]) + prev < 6:
    count += int(N[i]) + prev
    prev = 0
  elif 6 <= int(N[i]) + prev <= 9:
    count += 11 - (int(N[i]) + prev)
    prev = 1
  else:
    prev = 1
count = count + prev
print(count)

N = input()
count = 0
prev = 0
for i in range(len(N)):
  if 0 <= int(N[i]) + prev < 5:
    count += int(N[i]) + prev
    prev = 0
  elif 6 <= int(N[i]) + prev <= 9:
    count += 10 - (int(N[i]) + prev)
    prev = 1
  elif int(N[i]) + prev == 10:
    prev = 1
  else:
    if (i < (len(N) - 1) and int(N[i+1]) < 5) or i == len(N) - 1:
      count += 5
      prev = 0
    else:
      count += 5
      prev = 1
count = count + prev
print(count)

Verdicts: Runtime Error

Runtime Error

Wrong Answer

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):
def main():
    import sys
    input = sys.stdin.readline

    N = list(map(int, list(input()[::-1]))) + [0]

    ans = 0
    for i in range(len(N)-1):
        if N[i] < 5:
            ans += N[i]
        elif N[i] > 5:
            ans += 10 - N[i]
            N[i+1] += 1
        else:
            ans += 5
            if N[i+1] >= 5:
                N[i+1] += 1

    print(ans + N[len(N)-1])

main()

def main():
    import sys
    input = sys.stdin.readline

    N = list(map(int, list(input()[::-1]))) + [0]

    ans = 0
    for i in range(len(N)-1):
        if N[i] < 5:
            ans += N[i]
        elif N[i] > 5:
            ans += 10 - N[i]
            N[i+1] += 1
        else:
            ans += 5
            if N[i+1] >= 5:
                N[i+1] += 1

    print(ans + N[len(N)-1])

main()

def main():
    import sys
    input = sys.stdin.readline

    N = list(map(int, list(input())))
    N = N[::-1] + [0]

    ans = 0
    for i in range(len(N)-1):
        if N[i] < 5:
            ans += N[i]
        elif N[i] > 5:
            ans += 10 - N[i]
            N[i+1] += 1
        else:
            ans += 5
            if N[i+1] >= 5:
                N[i+1] += 1

    print(ans + N[len(N)-1])

main()

def main():
    N = list(map(int, list(input())))
    N = N[::-1] + [0]

    ans = 0
    for i in range(len(N)-1):
        if N[i] < 5:
            ans += N[i]
        elif N[i] > 5:
            ans += 10 - N[i]
            N[i+1] += 1
        else:
            ans += 5
            if N[i+1] >= 5:
                N[i+1] += 1

    print(ans + N[len(N)-1])

main()

Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):
N = list(input())
X = [int(i) for i in N]
ans = 0 
kuri = 0
tmp = 0
c5 = 0
for x in X:
    if c5 == 1:
        if x < 5:
            ans += 5
            c5 = 0
        elif x >= 5:
            ans += 4
            kuri = 1
            c5 = 0
    if kuri == 0:
        if x < 5:
            ans += x
            c5 = 0
        elif x == 5:
            c5 = 1
        else:
            kuri = 1
            ans += 10 - x
            c5 = 0
    else:
        if x < 5:
            ans += x
            kuri = 0
            ans += 1
        else:
            ans += 9 - x
    print(ans)
if kuri == 1:
    ans += 1

print(ans)


N = list(input())
Y = [0]
for i in N:
    Y.append(int(i))
dp = [0 for i in range(len(N)+1)]
dp2 = [10 for i in range(len(N)+1)]
for i in range(1,len(N)+1):
    dp[i] = min(dp[i-1] + Y[i],dp2[i-1] + Y[i])
    dp2[i] = min(dp[i-1] + 1 + 10 - Y[i],dp2[i-1] - 1 + 10 - Y[i])
ans = min(dp[-1],dp2[-1])
#print(dp,dp2)
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):
def main():
    N = [int(x) for x in input()]
    dp0 = 0
    dp1 = 1
    for n in N:
        
        a = min(dp0 + n, dp1 + 10 - n)
        
        b = min(dp0 + n + 1, dp1 + 10 - (n+1))
        dp0, dp1 = a, b
    print(min(dp0, dp1))


if __name__ == '__main__':
    main()

def main():
    N = [int(x) for x in input()]
    dp0 = 0
    dp1 = 1
    for n in N:
        
        a = min(dp0 + n, dp1 + 10 - n)
        
        b = min(dp0 + n + 1, dp1 + 10 - (n+1))
        dp0, dp1 = a, b
        print(n, dp0, dp1)
    print(dp0)


if __name__ == '__main__':
    main()

def main():
    N = [int(x) for x in input()]
    dp0 = 0
    dp1 = 1
    for n in N:
        
        a = min(dp0 + n, dp1 + 10 - n)
        
        b = min(dp0 + n + 1, dp1 + 10 - (n+1))
        dp0, dp1 = a, b
        
    print(dp0)
 
 
if __name__ == '__main__':
    main()

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):
N=input()
inf=float("inf")
dp=[[inf]*(len(N)+1) for i in range(2)]
dp[0][0]=0
for i in range(len(N)):
   tmp=int(N[-1-i])
   dp[0][i+1]=min(dp[0][i],dp[1][i])+tmp
   dp[1][i+1]=min(dp[0][i]+11,dp[1][i]+9)-tmp
   print(dp[0][i+1],dp[1][i+1])
print(min(dp[0][-1],dp[1][-1]))

N=input()
inf=float("inf")
dp=[[inf]*(len(N)+1) for i in range(2)]
dp[0][0]=0
for i in range(len(N)):
   tmp=int(N[-1-i])
   dp[0][i+1]=min(dp[0][i],dp[1][i])+tmp
   dp[1][i+1]=min(dp[0][i]+11,dp[1][i]+9)-tmp
print(min(dp[0][-1],dp[1][-1]))

Verdicts: Wrong Answer

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):
#import sys
#input = sys.stdin.readline
def main():
    S = [ int(x) for x in input()]
    ans = 0
    N = len(S)
    l = 0
    r = 1
    d = dict()
    d[0] = 0
    d[1] = 1
    d[2] = 2
    d[3] = 3
    d[4] = 4
    d[5] = 5
    d[6] = 4
    d[7] = 3
    d[8] = 2
    d[9] = 1
    for i in range(N):
        if S[i] >= 5 and i < N-1:
            continue
        for s in range(l,i+1):
            if s == l and S[s] == 9:
                ans += 2
                continue
            ans += d[s]
        l = i
    print(ans)
            
if __name__ == '__main__':
    main()


def main():
    S = [ int(x) for x in input()]
    ans = 0
    N = len(S)
    l = 0
    r = 1
    d = dict()
    d[0] = 0
    d[1] = 1
    d[2] = 2
    d[3] = 3
    d[4] = 4
    d[5] = 5
    d[6] = 4
    d[7] = 3
    d[8] = 2
    d[9] = 1
    for i in range(N):
        if S[i] >= 5 and i < N-1:
            continue
        for s in range(l,r):
            if s == l and S[s] == 9:
                ans += 2
                continue
            ans += d[s]
    print(ans)
            
if __name__ == '__main__':
    main()

#import sys
#input = sys.stdin.readline
def main():
    S = [ int(x) for x in input()]
    ans = 0
    N = len(S)
    l = 0
    r = 1
    d = dict()
    d[0] = 0
    d[1] = 1
    d[2] = 2
    d[3] = 3
    d[4] = 4
    d[5] = 5
    d[6] = 4
    d[7] = 3
    d[8] = 2
    d[9] = 1
    for i in range(N):
        if S[i] >= 5 and i < N-1:
            continue
        for s in range(l,r):
            if s == l and S[s] == 9:
                ans += 2
                continue
            ans += d[s]
        l = i
    print(ans)
            
if __name__ == '__main__':
    main()


def main():
    S = list( map( int, list( input())))
    N = len(S)
    dp = [[0,0] for _ in range(N+1)]
    dp[0][1] = 2
    for i in range(N):
        s = S[i]
        dp[i+1][0] = min(dp[i][0] + s, dp[i][1]+s)
        dp[i+1][1] = min(dp[i][0] + 11-s, dp[i][1]+9-s)
        # dp[i+1][2] = min(dp[i][1], dp[i][2])+9-s
        
        
    print( min(dp[N][0], dp[N][1]))
if __name__ == '__main__':
    main()


Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Accepted
Problem: In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. _(Takoyaki is the name of a Japanese snack.)_  To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.  What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?  Assume that you have sufficient numbers of banknotes, and so does the clerk.

Submission attempts (in order):
N=input()
a=[]
s=len(N)

for i in range(s-1,-1,-1):
    a.append(int(N[i]))
a.append(0)
#print(a)

p=sum(a)
t=0
f=0
c=0
for i in range(len(a)-1):
    if a[i] <= 5:
        t+=a[i]
        if a[i] == 5 and a[i+1]>=5:a[i+1]+=1
        f=0
        
    else:
        c+=10-a[i]
        a[i+1] += 1
        f=1
        
    print(t+f+c)

N=input()
a=[]
s=len(N)

for i in range(s-1,-1,-1):
    a.append(int(N[i]))
a.append(0)
#print(a)

p=sum(a)
t=0
f=0
c=0
for i in range(len(a)-1):
    if a[i] <= 5:
        t+=a[i]
        if a[i] == 5 and a[i+1]>=5:a[i+1]+=1
        f=0
        
    else:
        c+=10-a[i]
        a[i+1] += 1
        f=1
        
print(t+f+c)

Verdicts: Wrong Answer

Accepted