Problema 100m – ONI 2017, Clasa a 10-a

Enunțul problemei 100m, de clasa a 10-a, dată în 2017 la ONI, se găsește pe PbInfo și InfoArena.

Rezumat 100m

Î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:

Soluție 100m

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, ..., n} în 1, 2, …, 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 % 666013.

Sursă C++ 100m

Dacă ai vreo nedumerire cu privire la problema 100m, lasă un comentariu și te voi ajuta 🙂