#2428
sortari
Balaurului Arhirel nu îi plac prea mult şirurile care nu sunt ordonate. Din acest motiv, nu poate să suporte permutările de N
elemente, aşa că se decide să le sorteze şi pentru asta inventează o metodă proprie de sortare.
El ia iniţial un şir S
care reprezintă o permutare de ordin N
. Caută în şirul S
cel mai mic (min
) şi cel mai mare element (max
). Să considerăm că min
se află în şirul S
pe poziţia pmin
, iar max
pe poziţia pmax
. Să notăm cu x
minimul dintre pmin
şi pmax
, iar cu y
maximul dintre pmin
şi pmax
. Şirul S
a fost astfel partiționat în alte trei şiruri, S1
, S2
, S3
care pot avea fiecare zero elemente, un element sau mai multe elemente. Şirul S1
începe la prima poziţie din şir şi se termină la poziţia x-1
. Şirul S2
începe la poziţia x+1
şi se termină la poziţia y-1
. Şirul S3
începe la poziţia y+1
şi se termină la ultima poziţie din şir.
Balaurul Arhirel mută valoarea min
la capătul din stânga al lui S
, iar valoarea max
la capătul din dreapta al şirului S
şi reia sortarea pentru fiecare din şirurile S1
, S2
, S3
.
Evident, această metodă nu va funcţiona întotdeauna pentru sortarea unei permutări.
Spre exemplu, pentru şirul S = (3 4 1 6 5 2)
, se găseşte min = 1
şi max = 6
, iar S1 = (3 4)
, S2 = ()
, S3 = (5 2)
. Se mută min
şi max
la capetele lui S
: S = (1 3 4 5 2 6)
şi se procedează la sortarea pe rând a şirurilor S1
, S2
, S3
. S1
este sortat, S2
nu are elemente, iar S3
va deveni S3 = (2 5)
. În final, S = (1 3 4 2 5 6)
.
Ajutaţi-l pe Balaurul Arhirel să afle câte dintre permutările de N
elemente pot fi sortate prin metoda sa.
ONI 2004 clasa a X-a
Problema | sortari | Operații I/O |
![]() sortari.in /sortari.out
|
---|---|---|---|
Limita timp | 0.2 secunde | Limita memorie |
Total: 64 MB
/
Stivă 8 MB
|
Id soluție | #42640703 | Utilizator | |
Fișier | sortari.cpp | Dimensiune | 581 B |
Data încărcării | 13 Martie 2023, 14:41 | Scor / rezultat | 90 puncte |
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | 0.032 secunde | Raspuns gresit. | 10 | 0 | ||
1 | 0.032 secunde | OK. | 10 | 10 | ||
2 | 0.032 secunde | OK. | 10 | 10 | ||
3 | 0.032 secunde | OK. | 10 | 10 | ||
4 | 0.032 secunde | OK. | 10 | 10 | ||
5 | 0.032 secunde | OK. | 10 | 10 | ||
6 | 0.032 secunde | OK. | 10 | 10 | ||
7 | 0.032 secunde | OK. | 10 | 10 | ||
8 | 0.032 secunde | OK. | 10 | 10 | ||
9 | 0.032 secunde | OK. | 10 | 10 | ||
Punctaj total | 90 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema sortari face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.