Detalii evaluare #29223564

Rezumat problemă

#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.

Detalii

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 #29223564 Utilizator Lina Vlad (LinaVlad123)
Fișier sortari.cpp Dimensiune 629 B
Data încărcării 08 Aprilie 2021, 17:39 Scor / rezultat 100 puncte

Evaluare


Mesaj compilare


Rezultat evaluare

Test Timp Mesaj evaluare Scor posibil Scor obținut
0 0.024 secunde OK. 10 10
1 0 secunde OK. 10 10
2 0 secunde OK. 10 10
3 0 secunde OK. 10 10
4 0 secunde OK. 10 10
5 0 secunde OK. 10 10
6 0 secunde OK. 10 10
7 0.004 secunde OK. 10 10
8 0.008 secunde OK. 10 10
9 0.016 secunde OK. 10 10
Punctaj total 100

Cum funcționează evaluarea?

www.pbinfo.ro permite evaluarea a două tipuri de probleme:

  • probleme la care rezolvarea presupune scrierea unui program complet
  • probleme la care rezolvarea presupune scrierea unei secvențe de program - câteva instrucțiuni, o listă de declarații, una sau mai multe funcții, etc.

Problema sortari face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:

  • Programul sursă este compilat folosind compilatorul corespunzător. Dacă în urma compilării se obțin erori sau avertismente, acestea sunt afișate în această pagină.
  • Dacă programul a fost compilat, executabilul obținut va fi rulat, furnizându-i-se unul sau mai multe seturi de date de intrare, în concordanță cu restricțiile specifice problemei. Pentru fiecare set de date se obține un anumit punctaj, în raport cu corectitudinea soluției tale.

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ă.