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:

...
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 ...

Date de ieşire

În fişierul de ieşire cbinput.out ...

Restricţii

• 1 ≤ T ≤ 10
• 1 ≤ K ≤ N ≤ 1000

Exemplu

Explicaţie

In primul caz putem construi un sir astfel incat linia 9 sa se execute de 6 ori.

Cum se trimit solutii?