| 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 rezolvat-o astfel (cod C++):
...
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;
}
...Vrem sa ii dam o lectie pe care nu o va uita niciodata!
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 va contine pe prima linite un numar intreg T reprezentand numarul de teste. Fiecare test va aparea pe o singura linie care va contine doua numere intregi N si K.
Date de ieşire
În fişierul de ieşire cbinput.out se vor afla raspunsurile pentru cele T teste. Raspunsul pentru fiecare test se va afla pe o singura linie care va contine N numere reprezentand sirul cautat.
Restricţii
- 1 ≤ T ≤ 100
- 1 ≤ K ≤ N ≤ 1000
Exemplu
| cbinput.in | cbinput.out |
|---|---|
| 2 6 4 1 1 | 1 1 2 2 3 4 1 |
Explicaţie
In primul test putem construi un sir astfel incat linia 9 sa se execute de 6 ori.
