Se citește un număr natural n (1≤n≤31 ) și k≤1000000, și apoi k numere naturale de forma 2^{p} (0≤p≤30). Se cere să se afișeze pe ecran numărul care ar apărea pe poziția n în șirul ordonat strict crescător obținut din toate numerele distincte aflate pe a doua linie a fișierului. Dacă șirul are mai puțin de n termeni distincţi, se afișează pe ecran mesajul Nu exista. Pentru determinarea numărului cerut se utilizează un algoritm eficient din punctul de vedere al timpului de executare. Exemplu: dacă n=4, k=9 și numerele 2^{2} 2^{5} 2^{0} 2^{5} 2^{3} 2^{2} 2^{1} 2^{2}atunci pe ecran se afișează valoarea 8.
Răspunsuri la întrebare
Program C:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//Calculeaza log2(x), unde x este o putere a lui 2
int lg2p(unsigned x) {
if (x == 0) return -1;
int bk = 0;
while ((x & 1) == 0) {
++bk;
x >>= 1;
}
return bk;
}
int main() {
unsigned dim, n, tmp;
//Citire pozitie
scanf("%u", &n);
//Citire dimensiune vector
scanf("%u", &dim);
//Citire elemente, calculare valori bucket
int bkt[31] = {0};
for (unsigned i = 0; i < dim; i++) {
scanf("%u", &tmp);
++bkt[lg2p(tmp)];
}
//Afisare rezultat
int curent=0;
int idbkt = 0;
while (curent < n) {
curent += bkt[idbkt++];
}
printf("%u", 1 << idbkt);
}
Explicatie :
Stiind ca toate numerele sunt o putere a lui 2 putem calcula usor logaritm in baza 2 al fiecarui numar.
Folosim un vector de frecventa in care memoram cate numere de acelasi fel exista pentru orice putere a lui 2. Putem apoi determina rapid ce numar se afla pe orice index.
Vezi counting sort.
Nota :
Se considera ca
