Введем определение функции \(f(x)\): \(\) \begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{если } x \text{ четное} \\ x - 1 & \mbox{в противном случае } \end{matrix} \right. \end{matrix} \(\)
Можно заметить, что если мы выбираем некоторое число \(v\) и применяем к нему функцию \(f\), затем применяем функцию \(f\) к числу \(f(v)\), и так далее, то рано или поздно мы получим значение \(1\). Выпишем все промежуточные значения на пути от \(v\) до \(1\) и назовем все выписанные значения \(path(v)\). Например, \(path(1) = [1]\), \(path(15) = [15, 14, 7, 6, 3, 2, 1]\), \(path(32) = [32, 16, 8, 4, 2, 1]\).
Выпишем все \(path(x)\) для всех \(x\) от \(1\) до \(n\). Перед вами стоит задача: определить максимальное число \(m\) такое, что \(m\) встречается хотя бы в \(k\) различных \(path(x)\).
Иначе говоря, нужно найти такое максимальное \(y\), что \(\left| \{ x ~|~ 1 \le x \le n, y \in path(x) \} \right| \ge k\).
Примечание
В первом примере ответ равен \(5\), так как \(5\) встретится в \(path(5)\), в \(path(10)\) и в \(path(11)\).
Во втором примере ответ равен \(4\), так как \(4\) встретится в \(path(4)\), в \(path(5)\), в \(path(8)\), в \(path(9)\), в \(path(10)\) и в \(path(11)\).
В третьем примере \(n = k\), поэтому ответ равен \(1\), так как \(1\) это единственное число, содержащееся в путях всех чисел от \(1\) до \(20\).