Fişierul intrare/ieşire:magic3.in, magic3.outSursăAlgoritmiada 2014, Runda Finala
AutorAndrei HeidelbacherAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Magic3

Tassadar vrea să devină mentalist şi s-a hotărât să înveţe un truc pe care să i-l arate prietenului său, Zeratul. Se consideră numerele naturale de la 1 la N şi o constantă K (1 <= K < N). Zeratul trebuie să se gândească la un număr natural X (1 <= X <= N), iar Tassadar poate efectua întrebări de forma "Numărul X la care te-ai gândit se află în mulţimea { a1, a2, ..., aK }?" (mulţimea trebuie să conţină K numere naturale distincte din intervalul [1, N]).
După un anumit număr de întrebări, Tassadar va ghici prin magie numărul la care s-a gândit Zeratul.
Deoarece nu vrea să-şi plictisească prietenul cu prea multe întrebări, vă roaga să-i spuneţi care este numărul minim de întrebări pe care trebuie să le pună, în cel mai rău caz, pentru a ghici numărul la care s-a gândit Zeratul.

Date de intrare

Fişierul de intrare magic3.in conţine pe prima linie numărul de teste T. Pe următoarele T linii se vor afla câte două numere N şi K cu semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire magic3.out veţi afişa T numere reprezentând raspunsul pentru fiecare test, câte unul pe linie.

Restricţii

  • 1 ≤ T ≤ 104
  • 2 ≤ N ≤ 109
  • 1 ≤ K < N

Exemplu

magic3.inmagic3.out
1
7 2
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content