Полное решение:

Дается число n, нужно узнать мин кол-во кусочков, которое наш гг съест. Заметим, что мы всегда можем делать что-то по типу: 1 1 n-2, пока (n-2>=3). Из этого можно вывести формулу: floor((n-1)/2)

Сложность: O(1)

P/S: Вы конечно можете попробовать симуляцией, но боюсь по времени это не зайдет.

Полное решение:

Давайте рассмотрим решение-симуляцию. Какой для нас худший случай? Это когда все буквы в строке равны ‘A’. В таком случае у нас будет что то вроде O(1e9*n*q), что ясно не зайдет.

Вместо этого для этого случая мы можем вывести формулу: floor(N/len(s))+(N%len(s)).

Иначе можем просто просимулировать, потому если в строке есть хотя бы одна ‘B’, то симуляция займет log2(x) в худшем случае.

Сложность: O(n*log2(x)), на запрос.

Полное решение:

Оптимально сперва рассмотреть операцию “Разделить”, т.к она бесконечна. В каком случае x, подойдет для нашего y, в качестве данной операции?

Мы можем сделать что-то вроде n, x’ x’+(n%x) x’*2, однако данная стратегия не зайдет для чисел <x*4. Поэтому предположим, что любое число, что больше или равно нашему x*4, мы сможем разделить.

Теперь осталось лишь найти кол-во чисел <x*4, не считая чисел которые уже нам подходят, проверить сможем ли мы покрыть их к операциями. Так делаем для каждого x, от 1 до n.

Выведем максимальный ответ, как максимум из всех возможных вариантов.

Сложность: O(n) или O(nlogn) в зависимости от имплементации.