Rezumat problemă

cromatic

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

• 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

Fișiere Pracsiu Dan (dnprx) Szabo Zoltan concurs

Clasa 10 Probleme diverse Combinatorică

Rezolvă

Detalii

Problema	cromatic	Operații I/O	cromatic.in/cromatic.out
Limita timp	1.5 secunde	Limita memorie	Total: 256 MB / Stivă 64 MB
Id soluție	#58440911	Utilizator	Raduta Mihail (Mihailraduta)
Fișier	cromatic.cpp	Dimensiune	8.06 KB
Data încărcării	04 Iunie 2025, 16:42	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

cromatic.cpp: In function 'long long int combinations(int, int)':
cromatic.cpp:36:18: error: expected unqualified-id before '__int128'
         unsigned __int128 temp_res = (unsigned __int128)res * (n - i + 1);

                  ^
cromatic.cpp:37:13: error: 'temp_res' was not declared in this scope
         if (temp_res / (n - i + 1) != res && (n-i+1 !=0) ) { // Verificare simplă de overflow

             ^
cromatic.cpp: In function 'int main()':
cromatic.cpp:248:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("cromatic.in", "r", stdin);

                                       ^
cromatic.cpp:249:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("cromatic.out", "w", stdout);

                                         ^

Cum funcționează evaluarea?