1656 - Unu Zero

Se consideră un şir format din N+2 cifre binare, care conţine cel puţin o cifră 1 şi cel puţin trei cifre 0; prima şi ultima cifră a şirului sunt 0.

Numim 1-secvenţă o succesiune formată numai din cifre 1, aflate pe poziţii consecutive în acest şir, delimitată de câte o cifră 0.

Corina construieşte un astfel de şir, în care numărul de cifre 1 ale fiecărei 1-secvenţe să fie cuprins între două numere naturale date, p şi q (p ≤ q).

Cerința

Scrieţi un program care să determine un număr natural K, egal cu restul împărţirii la 666013 a numărului de şiruri distincte, de tipul celui construit de Corina.

Date de intrare

Fişierul de intrare input.txt conţine pe prima linie numărul natural N, iar pe cea de a doua linie numerele naturale p şi q ( p ≤ q ), separate printr-un spaţiu.

Date de ieșire

Fişierul de ieşire output.txt va conţine pe prima linie numărul natural K cerut.

Restricții și precizări

• 1 ≤ p ≤ q < N < 1.000.000

Exemplul 1

input.txt:

5

2 3

output.txt:

8

Explicație:

0000110

0001100

0001110

0011000

0011100

0110000

0110110

0111000

Exemplul 2

input.txt:

999999999

2 3

Output:

Constrangeri neindeplinite

Rezolvare

mod = 666013

def ver(n, p, q):
    if not(1<=n<=1000000):
        print("Constrangeri neindeplinite")
        exit()
    if not(1<=p<=1000000):
        print("Constrangeri neindeplinite")
        exit()
    if not(1<=q<=1000000):
        print("Constrangeri neindeplinite")
        exit()
    if not(p>=q):
        print("Constrangeri neindeplinite")
        exit()
    if not(q>=n):
        print("Constrangeri neindeplinite")
        exit()

def main():
    with open("input.txt", "r") as in_file, open("output.txt", "w") as out_file:
        
        n=int(in_file.readline().strip())
        a, b = map(int, in_file.readline().split())

        ver(n,a, b)
        
        z = [0] * (n + 1)
        s = [0] * (n + 1)
        u = [0] * (n + 1)

        z[0] = 1
        s[0] = 1

        for i in range(1, n + 1):
            z[i] = z[i - 1] + u[i - 1]  # daca punem 0
            z[i] %= mod

            if i - a >= 0:
                if i - b - 1 >= 0:
                    u[i] = s[i - a] - s[i - b - 1]
                else:
                    u[i] = s[i - a]

            if u[i] < 0:
                u[i] += mod
            u[i] %= mod

            s[i] = s[i - 1] + z[i]
            s[i] %= mod

        result = (z[n] + u[n] - 1 + (z[n] + u[n] - 1 < 0) * mod) % mod
        out_file.write(str(result) + '\n')


if __name__ == "__main__":
    main()