Fie numarul natural N
si sirul 1,1,
2, 2,
3, 3,
..., N, N
(sir crescator de lungime 2N,
in care fiecare numar intre 1
si N apare de exact doua ori).
Cu numerele acestui sir construim doua noi siruri de lungime N.
Fiecare numar din sirul initial se va depune fie in primul sir, fie in al doilea,
astfel incat cele doua siruri rezultate sa fie ordonate crescator.
De exemplu, pentru N=4 si sirul
initial 1,1,2,2,3,3,4,4,
putem construi de exemplu sirurile 1,1,3,4
si 2,2,3,4
sau sirurile 1,2,3,3
si 1,2,4,4.
Cerinta
Sa se determine numarul
de posibilitati de impartire a sirului initial in doua siruri de lungimi egale
cu N, astfel incat ambele siruri
sa fie crescatoare (nu neaparat strict), iar primul sir sa fie intotdeauna mai
mic sau egal din punct de vedere lexicografic decat al doilea. Pentru ca acest
numar poate fi mare, se va determina numarul modulo 7001.
Date de intrare
Fisierul sir.in
contine pe prima linie numarul natural N.
Date de iesire
Fisierul sir.out
va contine o singura linie pe care va fi scris un singur numar natural, reprezentand
numarul total de posibilitati, modulo 7001.
Restrictii şi precizari
2
<= N <= 80
Date doua siruri
de lungime N, a
= a1, a2, ..., aN si b
= b1, b2, ..., bN, spunem ca sirul a
este mai mic lexicografic decat b,
daca exista 1 <= k <= N
astfel incat a1=b1,
a2=b2,
..., ak-1=bk-1
si ak < bk.
Doua siruri de lungime N sunt
egale lexicografic daca ele coincid.
Exemplu
sir.in
sir.out
Explicatii
3
4
Sirul initial 1,
1, 2, 2, 3, 3 poate fi impartit in 4
moduri (4 mod 7001 = 4):
1,1,2 2,3,3
1,2,2 1,3,3
1,2,3 1,2,3
1,1,3 2,2,3
prof. Dan
Pracsiu
Gr. Sc. Ind. “Stefan Procopiu” Vaslui
Contact : dpracsiu@yahoo.com