Всем привет! Давно не было разборов, поэтому сегодня я решил сделать разбор на сегодняшний div2 контест. Всем приятного просмотра, а если возникнут вопросы, смело смотрите код решения. Постараюсь объяснить максимально понятно, ну от вас жду лайка.

Задача А:

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

Дается число 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) в зависимости от имплементации.