Rezolvare completă PbInfo #2193 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ța

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 și precizări

  • 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

Exemplul 1:

100m.in

3

100m.out

13

Explicație

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.

Exemplul 2:

100m.in

1771

100m.out

74140

Explicație

N = 1771 atleți. Numărul de clasamente distincte în care atleții pot termina cursa, modulo 666013, este 74140.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema 100m:

// Sursa cu numere Stirling de speta a doua - prof. Chesca Ciprian
// H(n) = S(n,1)1! + S(n,2)2! + ... + S(n,n-1)(n-1)! + S(n,n)n!

#include <fstream>
#define M 666013
#define nmax 5001

using namespace std;

long long n,H=0,a[nmax+1],b[nmax+1],f=1;

ifstream fin("100m.in");
ofstream fout("100m.out");



int main()
{
    int i,j;
    fin>>n;


    a[0]=1;b[0]=1;

    for(i=1;i<n;i++)
        {
        for(j=1;j<=i;j++)
            b[j]=((j+1)*a[j]+a[j-1])%M;

        for(j=0;j<=i;j++)
            a[j]=b[j];
        }

    for(i=1;i<=n;i++)
        {
        H=(H+b[i-1]*f)%M;
        f=f*(i+1)%M;
        }

    fout<<H<<"\n";

    fin.close();
    fout.close();

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2193 100m

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2193 100m de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!