Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ultimulcartus.in, ultimulcartus.out | Sursă | Junior Challenge 2016 |
| Autor | Andrei Constantinescu | Adăugată de |  JuniorChallenge2016 •JuniorChallenge2015 |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ultimul Cartus
Spoiler alert! Dupa moartea lui Miclovan viata a devenit monotona si absenta, comisarul Roman este pus in situatia de il prinde pe Semaca, pe care justitia l-a achitat din lipsa de probe.
Astfel, Roman ajunge in fata unei arhive vechi, plina cu N dosare (N putere a lui 2), aranjate intr-o ordine aleatorie. Un prim pas in analizarea acestora il reprezinta ordonarea lor alfabetica dupa titlu. Vom considera, pentru simplitate, ca titlurile celor N dosare sunt numere naturale distincte, cuprinse intre 1 si N (altfel spus, ordinea dosarelor reprezinta o permutare a numerelor de la 1 la N). Deoarece numarul dosarelor este destul de mare, Roman propune o abordare sistematica, pe care o va duce la bun sfarsit cu ajutorul subordonatilor sai. Aceasta poate fi descrisa prin urmatorul algoritm:
const int NMAX = 1000000000;
int N;
int p[NMAX + 1]; // = permutarea data
int ops;
void bubble(int gap) {
bool ok = true;
while (ok) {
ok = false;
for (int i = 1; i <= N - gap; ++ i)
if (p[i] > p[i + gap]) {
swap(p[i], p[i + gap]);
++ ops;
ok = true;
}
}
}
void bubblesort() {
int gap = N;
while (gap) {
bubble(gap);
gap /= 2;
}
}Date de intrare
Fişierul de intrare ultimulcartus.in ...
Date de ieşire
În fişierul de ieşire ultimulcartus.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| ultimulcartus.in | ultimulcartus.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
