Fișierul intrare/ieșire 100m2.in, 100m2.out Sursă ONI 2017, clasa a 10-a
Autor Ciprian Cheșcă Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.2 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

100m2 (clasa a 10-a)

Notă: aceasta este problema 100m cu o limită mai strînsă de timp.

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 100m2.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 100m2.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.in 100m.out Explicatii
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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii