149A - Командировка

Во-первых, ясно, что если сумма всех чисел a_i меньше, чем k, то Петя в любом случае не сумеет вырастить цветок до нужной высоты, и следует вывести <<-1>>.

Во-вторых, несложно понять, что если мы хотим выбрать один месяц из двух, в который мы будем поливать цветок, то выгодно выбирать тот, где число a_i максимально. Таким образом, решение задачи очень просто: следует брать месяцы в порядке убывания чисел a_i и в эти месяцы поливать цветы. Как только сумма набранных a_i станет больше или равна k — следует прекратить процесс, ответ найден.

149B - Марсианские часы

В этой задаче требовалось только умение работать с разными системами счисления. Давайте попробуем перебрать основание, для каждого основания проверить, допустимо ли оно, а также перевести часы и минуты в десятичную систему и сравнить с 24 и 60 соответственно.

До какой величины следует перебирать основание? На самом деле, достаточно до 60, потому что 60 – верхнее ограничение на допустимые числа. Это следует из того, что если число в неизвестной системе счисления состоит из одного знака, то ее значение в десятичной не меняется никогда, а иначе его значение не меньше основания.

Также стоило разобрать случай с ответом <<-1>>, для этого, например, можно было проверить большое основание, например 100, и если для даже для него время корректно, то и для всех больших оно тоже корректно и ответ равен <<-1>>.

149C - Разделение на команды

Отсортируем всех мальчиков по умению играть. Тогда если мы отправим в первую команду всех мальчиков, стоящих в отсортированном массиве на нечетных местах, а во вторую – стоящих на четных местах, то все требования к разбиению выполнятся.

Первые два требования очевидно выполняются.

Для доказательства третьего рассмотрим геометрическое представление: пусть каждый мальчик обозначается точкой на оси X со значением, равным его умению играть. Соединим отрезками точки с номерами 1 и 2, 3 и 4, и так далее. Если n нечетно, то соединим эту точку с ближайшей предыдущей.

Очевидно, что все эти отрезки попарно пересекаются разве что в точках, а суммарная их длина равна разности сумм умений играть мальчиков, входящих в первую команду и во вторую команду. Также очевидно, что все эти отрезки полностью содержатся в отрезке [0, max(a_i)], а так как попарно имеют нулевую длину пересечения, то третье требование выполняется, что мы и доказали.

149D - Раскрашивание скобок

Введем обозначения цветов: 0 – черный, 1 – красный, 2 – синий. Заметим, что у отдельно взятой пары скобок всего 4 варианта раскраски: 0-1, 1-0, 0-2, 2-0.

Рассмотрим динамическое программирование, где состояние имеет вид – (l, r, c_l, c_r), где пара (l, r) задает одну из пар скобок, а с_l и c_r означают фиксированные для них цвета. Значением динамики является количество способов раскрасить все скобочки внутри отрезка (l, r) с соблюдением всех условий.

Выпишем все пары скобок, которые вложены непосредственно в пару (l, r), пусть их k штук. Причем, будем рассматривать только первый уровень вложенности, именно непосредственно вложенные. Для того, чтобы подсчитать значение динамики для состояния, внутри этого состояния будем подсчитывать еще одну динамику, где состояние – это пара (i, c) которое означает количество правильных раскрасок первых i непосредственно вложенных скобок и всех внутри них, если последняя закрывающая скобка имеет цвет c. Пересчитывать такую динамику вперед очень просто – попробуем раскрасить (i + 1)-ую скобочку в один из четырех вариантов, учитывая возможные конфликты. У такой динамики начальным состоянием является пара (0, c_l), а итоговый результат – сумма по состояниям вида (k, c), где c не должно конфликтовать с c_r.

Ответ на всю задачу считается аналогично внутренней динамике. Асимптотика решения – O(n²) с коэффициентом порядка 12.

149E - Марсианские строки

Будем решать задачу отдельно для каждой из m строк. Итак, пусть у нас есть строка p, ее длина l, и нам нужно проверить, может ли марсианин ее увидеть.

Введем дополнительные массивы: пусть pref[i] – минимальная позиция в s начала вхождения префикса строки p длиной ровно i, а также пусть suff[j] – максимальная позиция в s конца вхождения суффикса строки p длиной ровно j.

Нетрудно понять, что марсианин сможет увидеть p, если существует такое i, что suff[l - i] ≥ pref[i] + l–1.

Как подсчитать массивы? Для массива pref достаточно найти Z-функцию строки p#s, а для массива suff – Z-функцию строки r(p)#r(s), где r(t) означает перевернутую строку t. Используя массив Z-функций значения массивов suff и pref подсчитать тривиально.