Lista de probleme 82

Filtrare

Fie a = (a[1], a[2], ..., a[n]) un șir de n numere întregi. Pentru fiecare k ∈ {1,2, ...,n}, definim min[k] = min{a[1], a[2], ... ,a[k]} și max[k] = max{a[1], a[2], ...,a[k]}. Astfel, asociem șirului a un alt șir de intervale închise minmax = ([min[1], max[1]], [min[2], max[2]], ..., [min[n], max[n]]). Vom spune că șirul a este un șir cromatic dacă și numai dacă elementele șirului minmax sunt distincte două câte două, adică nu există două intervale identice în șir. Dându-se un șir a, nu neapărat cromatic, să se determine:

  • Numărul de șiruri cromatice NSC ce se pot forma prin rearanjarea elementelor șirului a. Întrucât acest număr poate fi foarte mare, se cere NSC modulo 1.000.000.007.
  • Știind că șirul a este cromatic, să se determine poziția p ∈ {1, 2, ..., NSC} a șirului a în lista ordonată lexicografic a tuturor permutărilor cromatice ale lui a.
  • Dat fiind q ∈ {1, 2, ..., NSC}, să se determine cel de-al q-lea șir cromatic în ordine lexicografică ce se poate obține prin rearanjarea elementelor șirului a.

OJI 2025, clasele 11-12

Bomboane6 C++

#4820

RAU-Gigel își serbează ziua alături de colegii săi de la clubul de informatică și vrea să le împartă bomboane. El are un număr dat de bomboane și ar vrea să știe dacă îi ajung și, dacă da, în câte moduri le poate împărți. Dar nu își amintește câți colegi are la cerc, are însă o informație care ar putea să îl ajute.

Du-te sus!