632A - Grandma Laura and Apples
Задача предложена пользователем unprost.
Рассмотрим на процесс с конца. Последний покупатель всегда покупает половину яблока и половину получает бесплатно (поэтому последняя строка на самом деле всегда равна halfplus). Далее каждый покупатель удваивает текущее количество яблок и возможно прибавляет к нему единицу. Таким образом, нам просто задано бинарное представление числа записанное с конца. Для подсчёта ответа нужно просто с конца восстанавливать количество яблок попутно, вычисляя сумму денег.
С++ solution by me
Сложность: O(p).
632B - Alice, Bob, Two Teams
Задача предложена пользователем Lewin Gan Lewin.
Посчитаем частичные суммы на префиксах отдельно для всех чисел (в массиве s1) и отдельно для чисел напротив, которых стоит буква B (в массиве s2). Теперь мы можем за O(1) вычислять сумму на любом подотрезке, а также сумму на любом отрезке по числам напротив буквы B.
Переберем теперь префикс или суффикс и посчитаем сумму в случае его изменения по формуле: sum(s1, 0, n - 1) + sum(s2, 0, i) - s·sum(s1, 0, i) для префикса и sum(s1, 0, n - 1) + sum(s2, i, n - 1) + 2·sum(s1, i, n - 1) для суффикса.
C++ solution by me.
Python solution by Lewin.
Сложность: O(n).
