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

<syntaxhighlight lang="python3" line="1"> 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()

</syntaxhighlight>