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	#63298391	Utilizator	Gliggy Gliggy (Gliggy)
Fișier	permutare2.cpp	Dimensiune	3.48 KB
Data încărcării	25 Februarie 2026, 12:20	Scor/rezultat	0 puncte

Evaluare

Mesaj compilare

permutare2.cpp: In function 'std::vector<int> kthPermutation(int, long long int)':
permutare2.cpp:39:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int idx = 0; idx < available.size(); idx++) {

                                                ^
permutare2.cpp:42:18: warning: variable 'placeFirstHalf' set but not used [-Wunused-but-set-variable]
             bool placeFirstHalf = true;

                  ^
permutare2.cpp: In function 'long long int rankPermutation(int, const std::vector<int>&)':
permutare2.cpp:72:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int idx = 0; idx < available.size(); idx++) {

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

                                          ^

Rezultat evaluare

Cum funcționează evaluarea?