title: Solving yes-no test
body: <p>There is a test with <code>N</code> YES or NO questions. You can write the test and the professor will tell you how many of your answers are correct. What is the fastest way to pass the test? I.e. give correct answers to all questions with the minimum number of trials.</p>
  
  <p><strong>UPD</strong> The solution with <code>N+1</code> trials is obvious. On each trial we will have correct answer to a single question. It is 1 bit of information. But professor gives us a number from 0 to N each time, it is log<sub>2</sub>(N + 1) bits of information. That's why the best solution has <code>O(N / log(N))</code> complexity. <strong>I'm looking for any solution with sub-linear worst time complexity.</strong></p>