Fişierul intrare/ieşire:cbinput.in, cbinput.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorGeorge MarcusAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?