Школьный этап Всероссийской олимпиады школьников по информатике в г. Нефтеюганске 9-11 класс

По условию $$$T$$$ численно равно количеству литров молока, надоенного победителем. Обозначив за $$$S$$$ количество литров молока, надоенного проигравшим, получаем, что ответ равен $$$T - S$$$, с другой стороны, верно $$$S = L - T$$$, где $$$L$$$ – количество литров молока, надоенного обоими финалистами. При подстановке этого выражения в предыдущее получаем, что ответ равен $$$T - (L - T) = 2T - L$$$.

Чтобы не было сдачи, достаточно выбирать только те пачки чипсов, которые стоят не больше рублей и не больше копеек, чем есть у Вадима. Из всех таких нужно выбрать самую дорогую.

Заметим, что можно рассматривать каждое слово отдельно, найти минимальное количество ошибок, а затем просуммировать. Заведём три счётчика — два для существительных (которые начинаются с гласной и которые начинаются с согласной) и для глаголов. Тогда за один проход по строке, смотря на чётность позиции и гласность буквы, можно найти количество ошибок для каждого из вариантов слова. Из всех вариантов достаточно выбрать минимум.

В условии задачи описан процесс прибавления единицы к каждому разряду номера версии. Нетрудно реализовать функцию $$$f(x)$$$, добавляющую $$$1$$$ к каждому разряду. Для этого нужно посчитать количество цифр в числе $$$x$$$ и прибавить к нему $$$(10^d - 1) / 9$$$, где $$$d$$$ — это количество цифр. Но в задаче от вас просят обратить эту операцию.

Пусть у нас есть число $$$x$$$, состоящее из $$$d$$$ цифр. Нам нужно найти такое $$$y$$$, что $$$f(y) = x$$$. Заметим, что у $$$y$$$ может быть $$$d$$$ или $$$d - 1$$$ цифр. Предположив количество цифр в $$$y$$$, получим два кандидата: $$$$$$y_1 = x - {\frac {10^d - 1} 9}, y_2 = x - {\frac {10^{d - 1} - 1} 9}.$$$$$$

Тогда $$$y_1$$$ подходит, если $$$y_1$$$ положительное и имеет $$$d$$$ цифр; а $$$y_2$$$ подходит, если $$$y_2$$$ положительное и имеет $$$d - 1$$$ цифр.

Если подходит ровно одно из чисел $$$y_1$$$ и $$$y_2$$$, то мы нашли номер версии, предшествующий $$$x$$$-й. Наша цель — построить такую цепочку из чисел, начиная с $$$N$$$, и ответом на задачу будет длина цепочки. Цепочка оборвётся, если ни одно из чисел $$$y_1$$$, $$$y_2$$$ не подходит. Возможно, вам придётся обработать отдельный случай $$$x = 1$$$, которому не может предшествовать ни одно число, так как номер версии всегда натуральный.

Наконец, что делать, если из чисел $$$y_1$$$ и $$$y_2$$$ подходят оба? Оказывается, это невозможно. По их формулам нетрудно понять, что $$$y_2 > y_1$$$. Но мы требуем, чтобы в записи $$$y_2$$$ было на одну цифру меньше, чем в $$$y_1$$$. Таким образом, цепочка никогда не ветвится: по номеру версии мы либо однозначно определим предыдущую, либо сделаем вывод, что эта версия была первой.

Заметим, что при увеличении силы, количество видных достопримечательностей из города строго возрастает. Поэтому можно для каждого города запустить бинарный поиск по ответу. Для того, чтобы быстро пересчитать сумму на отрезке $$$[l;r]$$$, можно использовать префикс-суммы.

Пусть $$$p_i$$$ — сумма $$$s_j$$$ с $$$1$$$-го по $$$i$$$-й. Для удобства положим $$$p_0 = 0$$$. Тогда если у $$$i$$$-го города поставить силу телескопа $$$x$$$, из него будет видно $$$p_{min(i + x, n)} - p_{max(i - x - 1, 0)}$$$ достопримечательностей.