Відгадай число#527

Відгадай число (Розбір)

Запит повертає першу цифру числа n \cdot x, а перша цифра — це, по суті, інформація про дробову частину десяткового логарифма. Справді, перша цифра числа дорівнює тоді й лише тоді, коли

\{\log_{10} y\} \in \bigl[\log_{10} d,\; \log_{10}(d+1)\bigr),

де позначає дробову частину.

Позначимо t = \{\log_{10} n\} — саме цю величину ми й шукатимемо. Оскільки \log_{10}(nx) = \log_{10} n + \log_{10} x, кожен запит повідомляє, у який із дев'яти проміжків потрапляє \{t + \log_{10} x\}.

Це дозволяє робити двійковий пошук по . Підтримуємо відрізок [lo, hi), у якому лежить , і беремо його середину . Тепер підберемо так, щоб межа між відповіддю «» і відповіддю «» припала рівно на , тобто щоб

\{\mathit{mid} + \log_{10} x\} = \log_{10} 2.

Для цього візьмемо — найближче ціле до 10^{\,\log_{10} 2 - \mathit{mid} + k}, де показник підібраний так, щоб було якнайбільшим у межах 10^9 (що зменшує похибку округлення).

Тоді відповідь d = 1 означає t < \mathit{mid}, а d \ge 2 — що t \ge \mathit{mid}; звужуємо відрізок і повторюємо. Кожен запит дає рівно один біт.

Скільки бітів треба? Сусідні цілі і n+1 при n < 10^8 відрізняються за логарифмом приблизно на \frac{1}{n \ln 10} \approx 4 \cdot 10^{-9}, тому щоб їх розрізнити, потрібно близько \log_2 (1/4\cdot 10^{-9}) \approx 28 бітів. Саме тому ліміт — запитів, і кожен із них має давати повноцінний біт; «марнувати» запити не можна.

Відновлення . Знаючи з достатньою точністю, ми знаємо мантису числа. Залишилось визначити порядок — і тут стає в пригоді умова, що не ділиться на : числа , , мають однакову дробову частину логарифма, тож без цієї умови задача була б нерозв'язною. Отже, серед кандидатів \mathrm{round}(10^{\,t + j}) для різних рівно один не кратний десяти — він і є відповіддю.

Не забувайте про flush після кожного запиту й рахуйте логарифми в типі long double, щоб не втратити потрібні дев'ять значущих цифр.