La un concurs de dans participa
n perechi. Pentru fiecare pereche,
baiatul si fata au pe spate scris acelasi numar natural din multimea {1,
2, ..., 2n}.
Pot exista doua sau mai multe perechi care au pe spate acelasi numar.
Lânga un perete al salii de dans se afla un sir de scaune numerotate cu numerele
1, 2,
3, ..., 2n.
Dupa fiecare proba, perechile se aseaza astfel încât diferenta în valoare absoluta
dintre numerele asociate scaunelor alese de baiatul si fata din pereche sa fie
egala cu numarul scris pe spatele lor.
Cerinta Sa se scrie un program care sa determine numarul de modalitati distincte de
asezare a perechilor de dansatori care sa respecte regula din enunt.
Date de intrare Fisierul de intrare scaune.in
are pe prima linie numarul natural n.
Date de iesire
Fisierul de iesire scaune.out
va contine pe prima linie numarul cerut modulo 30103
(restul împartirii numarului cerut la 30103).
Restrictii si precizari 0<n<1001 n împartit la 4 da restul 0 sau 1.
Pe un scaun se poate aseza o singura persoana.
Doua modalitati de asezare pe scaune sunt considerate distincte daca exista
doua scaune pe aceeasi pozitie (unul în prima modalitate, celalalt în cea de-a
doua) cu numere diferite.
Exemplu
scaune.in
scaune.out
Explicatie
4
105
Doua
dintre cele 105 modalitati
de asezare sunt:
Perechea 1
are asociat numarul 1 si
poate sa se aseze pe scaunele 7,
8
Perechea 2 are asociat
numarul 2 si poate sa se
aseze pe scaunele 2, 4
Perechea 3 are asociat
numarul 3 si poate sa se
aseze pe scaunele 3, 6
Perechea 4 are asociat
numarul 4 si poate sa se
aseze pe scaunele 1, 5
Perechea 1 are asociat
numarul 4 si poate sa se aseze pe scaunele 1,
3
Perechea 2 are asociat numarul 2 si poate sa se aseze pe scaunele 2,
4
Perechea 3 are asociat numarul 4 si poate sa se aseze pe scaunele 5,
7
Perechea 4 are asociat numarul 2 si poate sa se aseze pe scaunele 6,
8
Doru Popescu
Anastasiu
C. N. "Radu Greceanu" Slatina
Contact: dopopan@yahoo.com