Вибір морозива

Ви стоїте перед морозильниками в супермаркеті, намагаючись вибрати тип морозива, яке хочете з'їсти після обіду. Завдання виявляється складним, адже все морозиво виглядає чудово! Тому ви вирішуєте довіритися випадковості, діставши з кишені свій чесний $k$-гранний кубик.

Однак, кількість варіантів морозива $n$ може не відповідати кількості граней $k$ на кубику. Це означає, що ви не можете просто кинути кубик один раз, щоб вибрати $i$-ий тип морозива. Вам потрібно знайти алгоритм, який включає нуль або більше кидків кубика, щоб вибір був рівноімовірним для кожного варіанту. Як досвідчений програміст, ви знаєте про метод прийняття-відхилення, який дозволяє зробити такий чесний вибір.

Проте сьогодні у вас важливе змагання, і ви не можете дозволити собі запізнитися. Тому метод прийняття-відхилення не підходить, адже він не гарантує обмежену кількість кидків. Ви вирішуєте знайти інший чесний алгоритм, який використовує найменшу кількість кидків у найгіршому випадку.

Для заданих $n$ і $k$ потрібно визначити найменше число $i$, для якого існує справедливий алгоритм, що вимагає не більше $i$ кидків кубика для вибору морозива.