Rezumat problemă

Permutare2

#2128

Definim o permutare dublă de ordin n ca fiind un șir format din primele 2n numere naturale nenule: (a[1], a[2], ... , a[n], a[n+1], a[n+2], ... , a[2n]). Această permutare dublă este de trei ori în creștere, dacă sunt adevărate următoarele trei proprietăți:

1. secvența formată din primele n elemente este crescătoare: a[1]<a[2]< ... < a[n]
2. secvența formată din ultimele n elemente este crescătoare: a[n+1]<a[n+2]< ... < a[2n]
3. perechile ordonate formate din elementele aflate pe poziții identice ale celor două secvențe sunt de asemenea în ordine crescătoare: a[1]<a[n+1], a[2]<a[n+2], ... , a[n]<a[2n].

Pentru simplificare în continuare permutarea dublă de trei ori în creștere se va numi permutare. Vom considera toate permutările de ordin n ordonate lexicografic, numerotate începând cu 1.

Există două tipuri de întrebări:

1. Ce permutare se află pe o poziție dată?
2. Pe ce poziție se află o permutare dată?

Să se răspundă corect la un set de întrebări.

OJI 2017, Clasele XI-XII

Fișiere Candale Silviu (silviu) Szabo Zoltan concurs

Clasa 11 Programare dinamică Probleme diverse de programare dinamică

Rezolvă

Detalii

Problema	Permutare2	Operații I/O	permutare2.in/permutare2.out
Limita timp	1.5 secunde	Limita memorie	Total: 64 MB / Stivă 32 MB
Id soluție	#62048294	Utilizator	Sipos Tudor (TudorSipos)
Fișier	permutare2.cpp	Dimensiune	4.58 KB
Data încărcării	04 Ianuarie 2026, 22:30	Scor/rezultat	50 puncte

Evaluare

Mesaj compilare

permutare2.cpp: In function 'll countWays(int, int)':
permutare2.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i == 2 * N)

                  ^
permutare2.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         return (j == N) ? 1 : 0;

                      ^
permutare2.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (res != -1)

                 ^
permutare2.cpp:26:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j < N) {

             ^
permutare2.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ((i - j) < N) {

                   ^
permutare2.cpp: In function 'std::vector<int> unrankPermutation(int, ll)':
permutare2.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i < 2 * N) {

                    ^
permutare2.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (j < N && 2 * j + 1 >= i) {

                 ^
permutare2.cpp: In function 'll rankPermutation(int, const std::vector<int>&)':
permutare2.cpp:95:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         bool actualIsOne = (pos[val] <= N); // if val is in first half

                                         ^
permutare2.cpp: In function 'int main()':
permutare2.cpp:139:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (unsigned int i = 0; i < (int)ans.size(); ++i) {

                                                        ^

Rezultat evaluare

Cum funcționează evaluarea?