Corjuc Eunice: Pagină nouă: 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 fi...

2024-01-04T20:53:57Z

Pagină nouă: 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 fi...

New page

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>

1656 - Unu Zero - Revision history