Se dă un şir cu n numere naturale distincte două câte două. Să se determine poziţia pe care s-ar afla primul element al şirului în şirul sortat.
Date de intrare
Fişierul de intrare pozitie.in conţine pe prima linie numărul n. Urmează n numere naturale, dispuse pe mai multe linii, separate prin spaţii.
Date de ieşire
Fişierul de ieşire pozitie.out va conţine pe prima linie numărul p, reprezentând poziţia în şirul sortat a primului element din şirul dat.
Restricţii şi precizări
1 ≤ n ≤ 10000
elementele şirului vor avea cel mult 9 cifre
numerotarea elementelor se face de la 1
Exemplu
pozitie.in
6
267 13 45 628 7 79
pozitie.out
5
Explicație
Şirul sortat este 13 45 79 267 628. În acest şir, valoarea 267 (prima din şirul iniţial) se află pe poziţia a 5-a.
Î
Răspunsuri la întrebare
Răspuns:
Explicație:
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("pozitie.in");
ofstream g("pozitie.out");
int v[10001], n;
int cautareBinara(int nr)
{
int st = 1, dr = n, mid;
while(st <= dr)
{
mid = (st + dr ) / 2;
if(v[mid] == nr)
{
return mid;
}
if(v[mid] < nr)
st = mid + 1;
else dr = mid - 1;
}
}
int main()
{
f >> n ;
for(int i = 1; i <= n; i++)
f >> v[i];
long long value = v[1];
sort(v + 1, v + 1 + n); /// sortez crescator vectorul.
g << cautareBinara(value);
return 0;
}
Răspuns:
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pozitie.in");
ofstream g("pozitie.out");
int n, num, primul, i, poz;
int main()
{
f >> n >> primul;
poz=1;
for (i=2; i<=n; ++i)
{
f >> num;
if (primul>num) ++poz;
}
g << poz;
}
Explicație:
problema e de la tema Parcurgerea vectorilor, dar am realizat fără vector. Condiţiile permit şi nici pbinfo nu s-a supărat şi a evaluat codul cu 100