Enunțul problemei 100m, de clasa a 10-a, dată în 2017 la ONI, se găsește pe InfoArena și PbInfo.
Rezumat
În problema 100m, ni se cere să determinăm numărul modalităților în care cei $n$ concurenți ai unei probe de 100 metri pot trece linia de finish, știind că între aceștia pot exista și egalități. De exemplu, pentru $n = 3$, numerotând concurenții cu $1$, $2$, $3$, vom obține următoarele clasamente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
(1) (2) (3) (1) (3) (2) (2) (1) (3) (2) (3) (1) (3) (1) (2) (3) (2) (1) (1 = 2) (3) (3) (1 = 2) (1 = 3) (2) (2) (1 = 3) (2 = 3) (1) (1) (2 = 3) (1 = 2 = 3) |
Soluție
Această problemă este o aplicație obișnuită la Numerele lui Stirling de speța a II-a. Vom considera, pe rând, toate partițiile mulțimii $\{1, 2, \ldots, n\}$ în $1, 2, \ldots, n$ submulțimi. Pentru fiecare partiție, submulțimea $i$ reprezintă grupul de concurenți care s-au clasat pe poziția $i$ (fiind la egalitate). De exemplu, partiția $\{1\}, \{2, 5\}, \{4\}, \{3, 6, 7\}$ are semnificația:
Concurentul $1$ s-a clasat pe prima poziție, concurenții $2$ și $5$ pe a doua poziție, fiind la egalitate, concurentul $4$ pe a treia poziție, iar concurenții $3$, $6$ și $7$ au terminat proba simultan, situându-se pe ultima poziție.
Pe fiecare astfel de partiție de $k$ submulțimi o putem permuta în toate modurile posibile ($k!$), pentru că acele grupuri de sportivi pot sosi în orice ordine. Pentru punctajul maxim vom precalcula eficient numere lui Stirling, cât și factorialul corespunzător fiecărui $k$. De asemenea, vom avea în vedere utilizarea aritmeticii modulare, deoarece rezultatul trebuie afișat modulo $666013$.
Sursă C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <fstream> #define NMAX 5010 #define MOD 666013 std::ifstream fin("100m.in"); std::ofstream fout("100m.out"); int n; long long int sol; long long int fact[NMAX]; long long int stir[2][NMAX]; int main() { fin >> n; bool ind = false; stir[ind][0] = 1; for (int i = 1; i <= n; i++, ind ^= true, stir[0][0] = stir[1][0] = 0) for (int j = 1; j <= i; j++) stir[!ind][j] = (stir[ind][j - 1] + stir[ind][j] * j) % MOD; fact[1] = 1; for (int i = 2; i <= n; i++) fact[i] = fact[i - 1] * i % MOD; for (int i = 1; i <= n; i++) sol = (sol + stir[ind][i] * fact[i]) % MOD; fout << sol << '\n'; fout.close(); return 0; } |
Dacă ai vreo nedumerire cu privire la problema 100m, lasă un comentariu și te voi ajuta 🙂
Îți place conținutul acestui site?
Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!