Cerința
Se dă un număr natural n (1≤n≤106 ), și un șir cu cel mult 1000000 de elemente, numere naturale de forma 10p (0≤p≤9). Se cere să se afișeze numărul care ar apărea pe poziția n în șirul ordonat crescător. Dacă șirul are mai puțin de n termeni, se afișează mesajul Nu exista.
Date de intrare
Fișierul de intrare puteri6.in conține pe prima linie numărul n, iar pe a doua linie elementele șirului dat, separate prin spații.
Date de ieșire
Fișierul de ieșire puteri6.out va conține pe prima linie numărul care ar apărea pe poziția n în șirul ordonat crescător sau mesajul Nu exista, dacă șirul are mai puțin de n termeni.
Restricții și precizări
Pentru determinarea numărului cerut se utilizează un algoritm eficient din punctul de vedere al timpului de executare. Se recomandă evitarea memorării valorilor elementelor din șir într-un tablou sau în altă structură de date similară.
Exemplu
puteri6.in
5
100 100000 1 100000 1000 100 10
puteri6.out
1000
Răspunsuri la întrebare
Răspuns:
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("puteri6.in");
ofstream g("puteri6.out");
int n, suma, fr[10], num, nrzero, i, z=1, exista, v[10];
int main()
{
for (i=0; i<10; ++i)
{
v[i]=z;
z*=10;
}
f >> n;
while (f >> num)
{
nrzero=0;
while (num>1)
{
++nrzero;
num=num/10;
}
++fr[nrzero];
}
for (int i=0; i<10; ++i)
{
suma=suma+fr[i];
if (suma>=n) { num= v[i]; exista=1; break; }
}
if (exista) g << num;
else g << "Nu exista";
}
Explicație:
O noua viziune a rezolvarii... la fel de 100 puncte... Succese la cercetare si comparare...
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("puteri6.in");
ofstream fout("puteri6.out");
int v[10], n,i,num,s;
int main()
{
fin >> n;
while (fin >> num)
{
i=-1; while (num) { ++i; num/=10; }
++v[i];
}
for (i=0; i<10; i++)
{
s+=v[i];
if (s>=n) break;
}
if (s<n) fout << "Nu exista";
else
{
fout << 1;
for (int p=1; p<=i; p++)
fout << 0;
}
return 0;
}