#4817
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:
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
.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
.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
#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.
RAU-Coder 2025