Problem p04016 (python)

Fixed submission:
import sys
input = sys.stdin.readline

def digit_sum(n, b):
    res = 0
    while n > 0:
        res += n % b
        n //= b
    return res

def main():
    n = int(input())
    s = int(input())
    ans = -1

    if n < s:
        ans = -1

    elif n == s:
        ans = n + 1

    else:
        key = []
        start, first = n, 1

        for i in range(1, n):
            first = digit_sum(n, start)
            end = start - n // i // (i + 1)
            if start == end+1:
                judge = start
                break

            while end > 1:
                if digit_sum(n, end) == i * (start - end) + first:
                    end -= 1
                    continue
                break
            next_start = end
            value = digit_sum(n, start)
            end = value + (start - end - 1) * i
            key.append((start, value, end, i, first))
            judge = start
            start = next_start
            if start == 1:
                break

        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for index, start, end, i, first in reversed(key):
                if end < s or s < start:
                    continue
                if (s - start) % i:
                    continue
                ans = index - (s - first) // i
                break

    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def digit_sum(n, b):
    res = 0
    while n > 0:
        res += n % b
        n //= b
    return res

def main():
    n = int(input())
    s = int(input())
    
    ans = -1
    if n == s:
        ans = n + 1
    else:
        for b in range(2, int(n**0.5) + 1):
            if digit_sum(n, b) == s:
                ans = b
                break
        
        else:
            for p in range(1, int(n**0.5)+1):
                b = (n - s) // p + 1
                if digit_sum(n, b) == s:
                    ans = b
                    break
    
    print(ans)



if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def digit_sum(n, b):
    if b == 1:
        return n
    res = 0
    while n > 0:
        res += n % b
        n //= b
    return res

def main():
    n = int(input())
    s = int(input())
    ans = -1
    if n < s:
        ans = -1
    elif n == s:
        ans = n + 1
    else:
        key = []
        start, first = n, 1

        for i in range(1, n):
            first = digit_sum(n, start)
            end = start - n // i // (i + 1)
            if start == end+1:
                judge = start
                break
            while end > 1:
                if digit_sum(n, end) == i * (start - end) + first:
                    end -= 1
                    continue
                break
            next_start = end - 1
            end = digit_sum(n, end)
            key.append((start, end, i, first))
            start = next_start
            judge = end
        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for start, end, i, first in reversed(key):
                if end < s:
                    continue
                if (s - first) % i:
                    continue
                ans = start - (s - first) // i
                break
    print(ans)
    
    for i in range(2, ans):
        if digit_sum(n, i) == s:
            print("WA")
            print(i)
            print(3/0)
            break


def judge():
    n = int(input())
    for i in range(2, min(n+5, 1000)):
        ans = digit_sum(n, i)
        print(str(i).zfill(3), ans)
    
#judge()
main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def digit_sum(n, b):
    if n < b:
        return n
    res = n % b + digit_sum(n // b, b)
    return res

def main():
    n = int(input())
    s = int(input())
    if n < s:
        ans = -1
    elif n == s:
        ans = n + 1
    else:
        key = []
        start, first = n, 1

        for i in range(1, n):
            first = digit_sum(n, start)
            end = start - n // i // (i + 1)
            if start == end:
                judge = end
                break
            while True:
                if digit_sum(n, end) == i * (start - end) + first:
                    end -= 1
                    continue
                break
            next_start = end - 1
            end = digit_sum(n, end)
            key.append((start, end, i, first))
            start = next_start
        for i in range(2, judge + 1):
            sub = digit_sum(n, i)
            if sub == s:
                ans = i
                break
        else:
            for start, end, i, first in reversed(key):
                if end < s:
                    continue
                if (s - first) % i:
                    continue
                ans = start - (s - first) // i
                break
    try:
        print(ans)
    except:
        print(-1)


def judge():
    n = int(input())
    for i in range(2, min(n+5, 1000)):
        ans = digit_sum(n, i)
        print(str(i).zfill(3), ans)
    
#judge()
main()