Editing 1656 - Unu Zero

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

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

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

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

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

= Date de ieșire =
Fişierul de ieşire <code>output.txt</code> va conţine pe prima linie numărul natural <code>K</code> cerut.

= Restricții și precizări =

* <code>1 ≤ p ≤ q < N < 1.000.000</code>

== Exemplul 1 ==
input.txt:

5

2 3

output.txt:

8

Explicație:

<code>0000110</code>

<code>0001100</code>

<code>0001110</code>

<code>0011000</code>

<code>0011100</code>

<code>0110000</code>

<code>0110110</code>

<code>0111000</code>

== 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>