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	#57704996	Utilizator	Burlacu Mihaela (MihaelaBurlacu)
Fișier	cromatic.cpp	Dimensiune	1.62 KB
Data încărcării	11 Aprilie 2025, 09:55	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

cromatic.cpp: In function 'void solve_c2()':
cromatic.cpp:2:23: error: 'a' was not declared in this scope
     if (!is_chromatic(a)) {

                       ^
cromatic.cpp:2:24: error: 'is_chromatic' was not declared in this scope
     if (!is_chromatic(a)) {

                        ^
cromatic.cpp:3:9: error: 'fout' was not declared in this scope
         fout << 0 << "\n";

         ^
cromatic.cpp:7:5: error: 'vector' was not declared in this scope
     vector<int> sorted_a = a;

     ^
cromatic.cpp:7:12: error: expected primary-expression before 'int'
     vector<int> sorted_a = a;

            ^
cromatic.cpp:7:12: error: expected ';' before 'int'
cromatic.cpp:8:10: error: 'sorted_a' was not declared in this scope
     sort(sorted_a.begin(), sorted_a.end());

          ^
cromatic.cpp:8:42: error: 'sort' was not declared in this scope
     sort(sorted_a.begin(), sorted_a.end());

                                          ^
cromatic.cpp:10:52: error: 'a' was not declared in this scope
     int k = find(sorted_a.begin(), sorted_a.end(), a[0]) - sorted_a.begin();

                                                    ^
cromatic.cpp:10:56: error: 'find' was not declared in this scope
     int k = find(sorted_a.begin(), sorted_a.end(), a[0]) - sorted_a.begin();

                                                        ^
cromatic.cpp:15:37: error: 'n' was not declared in this scope
         position = (position + comb(n - 1, i)) % MOD;

                                     ^
cromatic.cpp:15:45: error: 'comb' was not declared in this scope
         position = (position + comb(n - 1, i)) % MOD;

                                             ^
cromatic.cpp:15:50: error: 'MOD' was not declared in this scope
         position = (position + comb(n - 1, i)) % MOD;

                                                  ^
cromatic.cpp:19:12: error: expected primary-expression before 'int'
     vector<int> less, greater;

            ^
cromatic.cpp:19:12: error: expected ';' before 'int'
cromatic.cpp:20:25: error: 'n' was not declared in this scope
     for (int i = 1; i < n; ++i) {

                         ^
cromatic.cpp:21:26: error: 'less' was not declared in this scope
         if (a[i] < a[0]) less.push_back(a[i]);

                          ^
cromatic.cpp:22:14: error: 'greater' was not declared in this scope
         else greater.push_back(a[i]);

              ^
cromatic.cpp:25:10: error: 'less' was not declared in this scope
     sort(less.begin(), less.end(), greater<int>());

          ^
cromatic.cpp:25:36: error: 'greater' was not declared in this scope
     sort(less.begin(), less.end(), greater<int>());

                                    ^
cromatic.cpp:25:44: error: expected primary-expression before 'int'
     sort(less.begin(), less.end(), greater<int>());

                                            ^
cromatic.cpp:29:12: error: expected primary-expression before 'bool'
     vector<bool> used(n - 1, false);

            ^
cromatic.cpp:29:12: error: expected ';' before 'bool'
cromatic.cpp:30:12: error: expected primary-expression before 'int'
     vector<int> combined = less;

            ^
cromatic.cpp:30:12: error: expected ';' before 'int'
cromatic.cpp:31:5: error: 'combined' was not declared in this scope
     combined.insert(combined.end(), greater.begin(), greater.end());

     ^
cromatic.cpp:33:25: error: 'n' was not declared in this scope
     for (int i = 1; i < n; ++i) {

                         ^
cromatic.cpp:35:17: error: 'used' was not declared in this scope
             if (used[j]) continue;

                 ^
cromatic.cpp: In lambda function:
cromatic.cpp:39:41: error: 'used' was not declared in this scope
                     return x < a[0] && !used[find(combined.begin(), combined.end(), x) - combined.begin()];

                                         ^
cromatic.cpp: In function 'void solve_c2()':
cromatic.cpp:40:18: error: 'count_if' was not declared in this scope
                 });

                  ^
cromatic.cpp:41:70: error: 'comb' was not declared in this scope
                 position = (position + comb(remaining, remaining_less)) % MOD;

                                                                      ^
cromatic.cpp:41:75: error: 'MOD' was not declared in this scope
                 position = (position + comb(remaining, remaining_less)) % MOD;

                                                                           ^
cromatic.cpp:43:17: error: 'used' was not declared in this scope
                 used[j] = true;

                 ^
cromatic.cpp:49:5: error: 'fout' was not declared in this scope
     fout << (position + 1) % MOD << "\n";

     ^
cromatic.cpp:49:30: error: 'MOD' was not declared in this scope
     fout << (position + 1) % MOD << "\n";

                              ^
cromatic.cpp:28:9: warning: unused variable 'l' [-Wunused-variable]
     int l = less.size(), g = greater.size();

         ^

Cum funcționează evaluarea?