Fişierul intrare/ieşire:100m.in, 100m.outSursăONI 2017, clasa a 10-a
AutorCiprian ChescaAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.5 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

100m

Proba de 100 metri plat este una dintre cele mai populare şi prestigioase probe din cadrul oricărui concurs de atletism. Recordul modial al acestei probe este deţinut în prezent de sportivul jamaican Usain Bolt cu timpul de 9.58 secunde. Uneori lupta dintre sportivi este atât de strânsă încât diferenţierea dintre atleţi se poate face doar cu ajutorul camerelor de luat vederi ce surprind finish-ul atleţilor. Au existat cazuri când doi sau mai multi atleţi au fost declaraţi la egalitate.

Cerinţă

Considerând N atleţi, ce participă la o cursă de 100 metri plat, identificaţi prin numerele 1, 2, ..., N, să se scrie un program care determină numărul P al clasamentelor distincte care pot fi obţinute după finalizarea cursei.
De exemplu, pentru N = 2, se pot obţine 3 clasamente distincte: (1,2), (2,1),(1=2); unde (1=2) reprezintă situaţia când ambii atleţi s-au clasat la egalitate.

Date de intrare

Fişierul de intrare 100m.in conţine pe prima linie numărul natural N, cu semnificaţia de mai sus.

Date de ieşire

Fişierul de ieşire 100m.out va conţine pe prima linie restul împărţirii numărului P la 666013.

Restricţii

  • 2 ≤ N ≤ 5.000
  • Două clasamente se consideră distincte dacă diferă prin cel puţin o poziţie
  • Pentru teste în valoare de 32 de puncte N ≤ 500

Exemplu

100m.in100m.outExplicaţie
3
13
N = 3 atleţi.
Numerotând atleţii cu 1, 2 şi 3 există 13 clasamente distincte:
(1, 2, 3); (1, 3, 2); (2, 1, 3); (2, 3, 1); (3, 1, 2); (3, 2, 1)
(1 şi (2 = 3)); (2 şi (1 = 3)); (3 şi (1 = 2)); ((2 = 3) şi 1); ((1 = 3) şi 2); ((1 = 2) şi 3); (1 = 2 = 3).
Prin (i = j) am notat posibilitatea ca atleţii i şi j să termine cursa în acelaşi timp.
Prin (i = j = k) am notat posibilitatea ca atleţii i, j şi k să termine cursa în acelaşi timp.
1771
74140
N = 1771 atleţi.
Numărul de clasamente distincte în care atleţii pot termina cursa, modulo
666013, este 74140.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?