149A - Командировка
Во-первых, ясно, что если сумма всех чисел ai меньше, чем k, то Петя в любом случае не сумеет вырастить цветок до нужной высоты, и следует вывести <<-1>>.
Во-вторых, несложно понять, что если мы хотим выбрать один месяц из двух, в который мы будем поливать цветок, то выгодно выбирать тот, где число ai максимально. Таким образом, решение задачи очень просто: следует брать месяцы в порядке убывания чисел ai и в эти месяцы поливать цветы. Как только сумма набранных ai станет больше или равна k — следует прекратить процесс, ответ найден.
149B - Марсианские часы
В этой задаче требовалось только умение работать с разными системами счисления. Давайте попробуем перебрать основание, для каждого основания проверить, допустимо ли оно, а также перевести часы и минуты в десятичную систему и сравнить с 24 и 60 соответственно.
До какой величины следует перебирать основание? На самом деле, достаточно до 60, потому что 60 – верхнее ограничение на допустимые числа. Это следует из того, что если число в неизвестной системе счисления состоит из одного знака, то ее значение в десятичной не меняется никогда, а иначе его значение не меньше основания.
Также стоило разобрать случай с ответом <<-1>>, для этого, например, можно было проверить большое основание, например 100, и если для даже для него время корректно, то и для всех больших оно тоже корректно и ответ равен <<-1>>.
149C - Разделение на команды
Отсортируем всех мальчиков по умению играть. Тогда если мы отправим в первую команду всех мальчиков, стоящих в отсортированном массиве на нечетных местах, а во вторую – стоящих на четных местах, то все требования к разбиению выполнятся.
Первые два требования очевидно выполняются.
Для доказательства третьего рассмотрим геометрическое представление: пусть каждый мальчик обозначается точкой на оси X со значением, равным его умению играть. Соединим отрезками точки с номерами 1 и 2, 3 и 4, и так далее. Если n нечетно, то соединим эту точку с ближайшей предыдущей.
Очевидно, что все эти отрезки попарно пересекаются разве что в точках, а суммарная их длина равна разности сумм умений играть мальчиков, входящих в первую команду и во вторую команду. Также очевидно, что все эти отрезки полностью содержатся в отрезке [0, max(ai)], а так как попарно имеют нулевую длину пересечения, то третье требование выполняется, что мы и доказали.
149D - Раскрашивание скобок
Введем обозначения цветов: 0 – черный, 1 – красный, 2 – синий. Заметим, что у отдельно взятой пары скобок всего 4 варианта раскраски: 0-1, 1-0, 0-2, 2-0.
Рассмотрим динамическое программирование, где состояние имеет вид – (l, r, cl, cr), где пара (l, r) задает одну из пар скобок, а сl и cr означают фиксированные для них цвета. Значением динамики является количество способов раскрасить все скобочки внутри отрезка (l, r) с соблюдением всех условий.
Выпишем все пары скобок, которые вложены непосредственно в пару (l, r), пусть их k штук. Причем, будем рассматривать только первый уровень вложенности, именно непосредственно вложенные. Для того, чтобы подсчитать значение динамики для состояния, внутри этого состояния будем подсчитывать еще одну динамику, где состояние – это пара (i, c) которое означает количество правильных раскрасок первых i непосредственно вложенных скобок и всех внутри них, если последняя закрывающая скобка имеет цвет c. Пересчитывать такую динамику вперед очень просто – попробуем раскрасить (i + 1)-ую скобочку в один из четырех вариантов, учитывая возможные конфликты. У такой динамики начальным состоянием является пара (0, cl), а итоговый результат – сумма по состояниям вида (k, c), где c не должно конфликтовать с cr.
Ответ на всю задачу считается аналогично внутренней динамике. Асимптотика решения – O(n2) с коэффициентом порядка 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 подсчитать тривиально.
