Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2017-12-18 13:58:19.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cbinput.in, cbinput.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 18 |
| Autor | George Marcus | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
Cbinput
Georgel are de rezolvat urmatoarea problema: Se da un sir de N numere in ordine crescatoare cu valori intre 1 si K. Fiecare valoare de la 1 la K apare cel putin o data in sir. Sa se gaseasca ultima aparitie in sir a fiecarei valori de la 1 la K.
Georgel, incepator intr-ale informaticii, a gasit aceasta rezolvare:
...
int cautareBinara(int val) {
int st = 1;
int dr = N;
while(st <= dr) {
int mid = (st + dr) / 2;
if(v[mid] == val) {
while(mid <= N && v[mid] == val) {
mid++; // <==
}
return mid - 1;
} else if(v[mid] < val) {
st = mid + 1;
} else {
dr = mid - 1;
}
}
return -1;
}
...
for (int i = 1; i <= K; i++) {
cout << cautareBinara(i) << endl;
}
...Fiind date N si K, sa se gaseasca un sir valid de intrare astfel incat linia 9 (mid++) sa se execute de un numar maxim de ori.
Date de intrare
Fişierul de intrare cbinput.in ...
Date de ieşire
În fişierul de ieşire cbinput.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| cbinput.in | cbinput.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
Trebuie sa te autentifici pentru a trimite solutii. Click aici
