Editing 1675 - Calc (section)

==Rezolvare==
<syntaxhighlight lang="python">
MODULO = 1000 * 1000 * 1000 + 7


def read_input():
    with open("calc.in", "r") as f:
        tip = int(f.readline().strip())
        n = int(f.readline().strip())
        s = f.readline().strip()
    return tip, n, s


def write_output(prev, next):
    with open("calc.out", "w") as f:
        f.write(f"{prev}\n{next}\n")


def compute_prev(s):
    n = len(s)
    prev = list(s)
    if s[n - 1] == "1" and s[n - 2] == "1":
        prev[n - 1] = prev[n - 2] = "0"
    else:
        i = n - 2
        while i >= 0 and s[i] == "0":
            i -= 1
        if i < 0:
            prev = "-1"
        else:
            prev[i] = "0"
            for j in range(i + 2, n):
                prev[j] = "1"
    return "".join(prev)


def compute_next(s):
    n = len(s)
    next = list(s)
    if s[n - 1] == "0" and s[n - 2] == "0":
        next[n - 1] = next[n - 2] = "1"
    else:
        i = n - 1
        while i >= 0 and s[i] == "1":
            i -= 1
        if i < 0:
            next = "-1"
        else:
            next[i - 1] = "1"
            next[i] = "0"
            oldi = i
            for j in range(i + 1, n):
                next[j] = "0"
            if (n - 1 - oldi) % 2 == 0:
                next[n - 1] = "1"
    return "".join(next)


def compute_fibonacci(n):
    if n <= 1:
        return 1
    a, b = 1, 1
    for i in range(2, n + 1):
        c = (a + b) % MODULO
        a, b = b, c
    return b

def validate_input(tip: int, N: int, S: str) -> bool:
    if tip not in (1, 2):
        print("tip trebuie sa fie 1 sau 2")
        return False
    if not (1 <= N <= 100000):
        print("N trebuie sa fie intre 1 si 100000")
        return False
    if len(S) != N or not set(S).issubset({'0', '1'}):
        print("S trebuie sa fie un sir de N caractere '0' sau '1'")
        return False
    print("Input valid")
    return True

if __name__ == "__main__":
    tip, n, s = read_input()
    if not validate_input(tip, n, s):
        exit(1)
    if tip == 1:
        result = compute_fibonacci(n)
        write_output(result, result)
        return

    if n == 1:
        write_output("-1", "-1")
        return

    prev = compute_prev(s)
    next = compute_next(s)
    write_output(prev, next)


</syntaxhighlight>