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	#63581865	Utilizator	Rotaru Elena (elena_rotaru)
Fișier	cromatic.cpp	Dimensiune	3.53 KB
Data încărcării	10 Martie 2026, 12:17	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

cromatic.cpp:4:18: warning: multi-character character constant [-Wmultichar]
 const int MOD = 1'000'000'007;

                  ^
cromatic.cpp:4:26: warning: missing terminating ' character [enabled by default]
 const int MOD = 1'000'000'007;

                          ^
cromatic.cpp:4:1: error: missing terminating ' character
 const int MOD = 1'000'000'007;

 ^
cromatic.cpp:4:18: error: expected ',' or ';' before '\x303030'
 const int MOD = 1'000'000'007;

                  ^
cromatic.cpp:7:16: error: 'MAXN' was not declared in this scope
 long long fact[MAXN], invfact[MAXN];

                ^
cromatic.cpp:7:31: error: 'MAXN' was not declared in this scope
 long long fact[MAXN], invfact[MAXN];

                               ^
cromatic.cpp: In function 'long long int C(int, int)':
cromatic.cpp:23:12: error: 'fact' was not declared in this scope
     return fact[n]*invfact[k]%MOD*invfact[n-k]%MOD;

            ^
cromatic.cpp:23:20: error: 'invfact' was not declared in this scope
     return fact[n]*invfact[k]%MOD*invfact[n-k]%MOD;

                    ^
cromatic.cpp: In function 'int main()':
cromatic.cpp:31:5: error: 'fact' was not declared in this scope
     fact[0]=1;

     ^
cromatic.cpp:32:19: error: 'MAXN' was not declared in this scope
     for(int i=1;i<MAXN;i++) fact[i]=fact[i-1]*i%MOD;

                   ^
cromatic.cpp:33:5: error: 'invfact' was not declared in this scope
     invfact[MAXN-1]=modpow(fact[MAXN-1], MOD-2);

     ^
cromatic.cpp:33:13: error: 'MAXN' was not declared in this scope
     invfact[MAXN-1]=modpow(fact[MAXN-1], MOD-2);

             ^
cromatic.cpp: In function 'long long int C(int, int)':
cromatic.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

 ^

Cum funcționează evaluarea?