#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
ID | Utilizator | Problema | Data încărcării | Stare | ||
---|---|---|---|---|---|---|
sortari | 16 Aprilie 2024, 13:36 | Evaluare finalizată | 100 | |||
sortari | 16 Aprilie 2024, 13:32 | Evaluare finalizată | 100 | |||
sortari | 16 Aprilie 2024, 13:32 | Evaluare finalizată | 20 | |||
sortari | 16 Aprilie 2024, 13:30 | Evaluare finalizată | 10 | |||
sortari | 15 Aprilie 2024, 20:01 | Evaluare finalizată | 100 | |||
sortari | 03 Aprilie 2024, 13:27 | Evaluare finalizată | 100 | |||
sortari | 20 Decembrie 2023, 20:06 | Evaluare finalizată | 100 | |||
sortari | 20 Decembrie 2023, 19:54 | Evaluare finalizată | 10 | |||
sortari | 10 Decembrie 2023, 23:02 | Evaluare finalizată | 100 | |||
sortari | 23 Noiembrie 2023, 19:36 | Evaluare finalizată | 100 | |||
sortari | 23 Noiembrie 2023, 19:17 | Evaluare finalizată | E.C | |||
sortari | 11 Septembrie 2023, 14:10 | Evaluare finalizată | 100 | |||
sortari | 07 August 2023, 15:57 | Evaluare finalizată | 100 | |||
sortari | 04 Iulie 2023, 07:37 | Evaluare finalizată | 100 | |||
sortari | 23 Aprilie 2023, 15:41 | Evaluare finalizată | 100 | |||
sortari | 23 Aprilie 2023, 15:38 | Evaluare finalizată | 0 | |||
sortari | 06 Aprilie 2023, 16:29 | Evaluare finalizată | 100 | |||
sortari | 13 Martie 2023, 20:58 | Evaluare finalizată | 100 | |||
sortari | 13 Martie 2023, 20:48 | Evaluare finalizată | 10 | |||
sortari | 13 Martie 2023, 14:42 | Evaluare finalizată | 100 | |||
sortari | 13 Martie 2023, 14:41 | Evaluare finalizată | 90 | |||
sortari | 13 Martie 2023, 14:35 | Evaluare finalizată | 100 | |||
sortari | 13 Martie 2023, 14:19 | Evaluare finalizată | 20 | |||
sortari | 23 Februarie 2023, 17:59 | Evaluare finalizată | 100 | |||
sortari | 22 Februarie 2023, 12:29 | Evaluare finalizată | 100 | |||
sortari | 20 Februarie 2023, 17:41 | Evaluare finalizată | 100 | |||
sortari | 20 Februarie 2023, 17:40 | Evaluare finalizată | 100 | |||
sortari | 20 Februarie 2023, 17:39 | Evaluare finalizată | 20 | |||
sortari | 05 Februarie 2023, 09:27 | Evaluare finalizată | 100 | |||
sortari | 05 Februarie 2023, 09:26 | Evaluare finalizată | 100 | |||
sortari | 25 Ianuarie 2023, 21:17 | Evaluare finalizată | 100 | |||
sortari | 04 Ianuarie 2023, 14:28 | Evaluare finalizată | 100 | |||
sortari | 04 Ianuarie 2023, 14:26 | Evaluare finalizată | 20 | |||
sortari | 04 Ianuarie 2023, 14:26 | Evaluare finalizată | 20 | |||
sortari | 04 Ianuarie 2023, 14:20 | Evaluare finalizată | 10 | |||
sortari | 04 Ianuarie 2023, 14:20 | Evaluare finalizată | 0 | |||
sortari | 04 Ianuarie 2023, 14:17 | Evaluare finalizată | 0 | |||
sortari | 04 Ianuarie 2023, 14:17 | Evaluare finalizată | 10 | |||
sortari | 04 Ianuarie 2023, 13:26 | Evaluare finalizată | E.C | |||
sortari | 02 Ianuarie 2023, 08:50 | Evaluare finalizată | 100 | |||
sortari | 31 Decembrie 2022, 15:10 | Evaluare finalizată | 100 | |||
sortari | 22 Decembrie 2022, 08:29 | Evaluare finalizată | 100 | |||
sortari | 22 Decembrie 2022, 08:28 | Evaluare finalizată | 100 | |||
sortari | 21 Decembrie 2022, 23:11 | Evaluare finalizată | 100 | |||
sortari | 21 Decembrie 2022, 23:10 | Evaluare finalizată | 70 | |||
sortari | 21 Decembrie 2022, 23:09 | Evaluare finalizată | 70 | |||
sortari | 21 Decembrie 2022, 22:35 | Evaluare finalizată | 100 | |||
sortari | 21 Decembrie 2022, 22:34 | Evaluare finalizată | 70 | |||
sortari | 21 Decembrie 2022, 22:32 | Evaluare finalizată | 10 | |||
sortari | 21 Decembrie 2022, 22:32 | Evaluare finalizată | E.C |