517A — Виталий и строки

Для решения данной задачи можно было, например, найти строку next, лексикографически следующую за строкой s и проверить, что строка next лексикографически меньше строки t. Если строка next оказалась меньше строки t, выведем ее и закончим алгоритм. Если же строка next совпала со строкой t, следовало вывести No such string.

Чтобы найти строку next, лексикографически следующую за s, нужно сначала найти максимальный суффикс строки s, состоящий из букв 'z', заменить все буквы 'z' в этом суффиксе на буквы 'a', а затем букву, стоящую перед этим суффиксом, увеличить на единицу. То есть, если перед суффиксом стояла, например, буква 'd', ее следует заменить на букву 'e'.

Асимптотика решения — O(|s|), где |s| — длина строки s.

517B — Таня и поздравление

Для решения данной задачи, сначала насчитаем массив cnt[], где cnt[c] — сколько раз буква c встречалась в строке t. Будем считать два числа ans1 и ans2 — сколько раз Таня прокричит УРА! и сколько раз Таня произнесет ОПА.

Теперь проитерируемся по строке s, и если cnt[s[i]] > 0, то прибавим к ans1 единицу и уменьшим cnt[s[i]] на единицу.

Теперь вновь проитерируемся по строке s. Пусть c это буква равная s[i], но в обратном ей регистре. То есть если s[i] = 'w', то c = 'W'. Теперь, если cnt[c] > 0, то прибавим к ans2 единицу и уменьшим cnt[с] на единицу.

Осталось вывести два числа — ans1 и ans2.

Асимптотика решения — O(|s| + |t|), где |s| — длина строки s, а |t| — длина строки t.

517C — Аня и смартфон

Для решения данной задачи будем хранить два массива — a[] и pos[]. В массиве a[] будем хранить текущий порядок расположения иконок, то есть в a[i] хранится номер приложения, иконка которого стоит на i-м месте. В массиве pos[] будем хранить на каком месте в списке находятся иконки, то есть в pos[i] хранится в какой позиции массива a[] находится иконка приложения номер i. Будем считать ответ в переменной ans.

Проитерируемся по приложениям, которые нужно открыть. Пусть текущее приложение имеет номер num. Тогда нужно к ans прибавить pos[num] / k + 1 (первый член суммы — количество движений пальцем, чтобы долистать до нужного экрана, второй член суммы — одно движение пальцем для открытия приложения). Теперь, если иконка приложения номер num не стоит на первом месте в списке приложений, сделаем следующее — поменяем местами значения a[pos[num]] и a[pos[num] - 1] и обновим значения pos[] для иконок приложений, чьи номера равны a[pos[num]] и a[pos[num] - 1].

Асимптотика решения — O(n + m), где n — количество приложений, m — количество запросов на запуск приложений.

517D — Илья и эскалатор

Для решения данной задачи воспользуемся динамическим программированием. Будем хранить двумерный массив z типа double . В z[i][j] будет храниться вероятность того, что через i секунд j человек зашли на эскалатор.

В динамике будут следующие переходы. Если j = n, то есть все n людей уже находятся на эскалаторе, тогда сделаем переход z[i + 1][j] +  = z[i][j]. Иначе, либо j-й человек зайдет на эскалатор в i + 1 секунду, то есть z[i + 1][j + 1] +  = z[i][j] * p, либо j-й человек останется на месте, то есть z[i + 1][j] +  = z[i][j] * (1 – p).

Осталось посчитать ответ (математическое ожидание количества людей на эскалаторе) — это сумма по j от 0 до n включительно z[t][j] * j.

Асимптотика решения — O(t * n), где t — на какой момент нужно посчитать матожидание, n — сколько людей сначала стоит у эскалатора.

517E — Артур и вопросы

Сначала заметим следующий факт. Возьмем первые две суммы a₁ + a₂ + ... + a_k и a₂ + a₃ + ... + a_k + 1. Должно выполниться неравенство a₁ + a₂ + ... + a_k < a₂ + a₃ + ... + a_k + 1. Если перенести справа налево все элементы кроме a_k + 1, все они сократятся и останется a₁ < a_k + 1. Если выписать далее все подобные суммы получится, что последовательность распадается на k непересекающихся цепочек: a₁ < a_k + 1 < a_2k + 1 < a_3k + 1..., a₂ < a_k + 2 < a_2k + 2 < a_3k + 2..., ..., a_k < a_2k < a_3k....

Будем решать задачу для каждой цепочки отдельно. Рассмотрим первую цепочку a₁, a_k + 1, a_2k + 1.... Проитерируемся по ней, и найдем все пары индексов i, j (i < j), что a[i] и a[j] это числа, а не вопросы, в заданной последовательности, а для всех k от i + 1 до j - 1 в a[k] стоят знаки вопроса. Тогда понятно, что все эти вопросы нужно заменить на числа таким образом, чтобы не нарушить условие возрастания и при этом минимизировать сумму модулей поставленных чисел.

Понятно, что между индексами i и j стоит j - i - 1 знак вопроса, их можно заменить на a[j] - a[i] - 1 чисел. Если j - i - 1 > a[j] - a[i] - 1, тогда нужно вывести Incorrect sequence и закончить алгоритм. Иначе нужно жадным образом заменить все эти вопросы на числа.

Здесь возможно несколько случаев. Рассмотрим один из них, когда a[i] >  = 0 и a[j] >  = 0. Пусть текущая цепочка (3, ?, ?, ?, 9), i = 1, j = 5. Знаки вопроса нужно заменить следующим образом — (3, 4, 5, 6, 9). Осталось два случая, когда a[i] <  = 0, a[j] <  = 0, и случай, когда a[i] <  = 0, a[j] >  = 0. В таких случаях нужно поступать жадным образом, аналогично первому, не нарушая условие возрастания и минимизируя сумму модулей поставленных чисел.

Асимптотика решения — O(n), где n — количество элементов в заданной последовательности.

517F — Паша и труба

Будем решать данную задачу поэтапно. Сначала насчитаем два двумерных массива частичных сумм sumv[][] и sumg[][]. В sumv[i][j] хранится сколько решеток стоит в столбце j начиная со строки 1 до строки i. В sumg[i][j] хранится сколько решеток стоит в строке i начиная со столбца 1 до столбца j.

Посчитаем ans0 — сколько труб без изгибов можно проложить. Посчитаем количество вертикальных труб — проитерируемся по j от 2 до m — 1 и, если sumg[n][j] — sumg[n][0] = 0 (то есть в этом столбце нет ни одной решетки), прибавим к ans0 единицу. Аналогично посчитаем количество горизонтальных труб.

Посчитаем ans1 — сколько труб с 1 изгибом можно проложить. Переберем клетку, в которой будет изгиб (по условию эта клетка не должна лежать на краях поля). Возможны четыре случая: труба начинается слева, доходит до текущей перебираемой клетки и поворачивает вверх; труба начинается сверху, доходит до текущей перебираемой клетки и поворачивает вправо; труба начинается справа, доходит до текущей перебираемой клетки и поворачивает вниз; труба начинается снизу, доходит до текущей перебираемой клетки и поворачивает влево.

Рассмотрим первый случай — труба начинается слева, доходит до текущей перебираемой клетки и поворачивает вверх. Пусть клетка поворота находится в i-й строке и j-м столбце. Тогда к ans1 нужно прибавить единицу, если (sumg[i][j] — sumg[i][0]) + (sumv[i][j] — sumv[0][j]) = 0. Для оставшихся случаев нужно сделать аналогичным образом.

Осталось посчитать ans2 — сколько труб с 2 изгибами можно проложить. Поступим следующим образом. Посчитаем сколько труб начинаются сверху и заканчиваются сверху или снизу, и прибавим это число к ans2. Затем повернем матрицу три раза на 90 градусов и после каждого поворота прибавим к ans2 количество труб, начинающихся сверху и заканчивающихся сверху или снизу. Если считать таким образом, каждая труба посчитается по два раза, поэтому ans2 нужно поделить пополам.

Как посчитать для текущей матрицы сколько труб начинаются сверху и заканчиваются сверху или снизу. Насчитаем четыре двумерных массива lf[][], rg[][], sumUp[][], sumDown[][]. Пусть i — номер строки, j — номер столбца текущей клетки. Тогда в позиции (i, lf[i][j]) в матрице находится ближайшая слева решетка для клетки (i, j), а в позиции (i, rg[i][j]) в матрице находится ближайшая справа решетка для клетки (i, j). В sumUp[i][j] должно быть число — сколько столбцов без решеток содержится в подматрице от (1, 1) до (i, j) исходной матрицы. В sumDown[i][j] должно быть число — сколько столбцов без решеток содержится в подматрице от (i, 1) до (n, j) исходной матрицы. Осталось перебрать клетку, в которой произойдет первый поворот трубы (она шла сверху и повернула направо или налево), проверить что в столбце j над этой клеткой нет решеток, с помощью массивов lf и rg узнать насколько труба могла идти налево или направо и с помощью массивов sumUp и sumDown аккуратно пересчитать ответ.

Осталось вывести число ans1 + ans2 + ans3.

Асимптотика решения — O(n * m * const), где n — количество строк в заданной матрице, m — количество столбцов в заданной матрице, const принимает различные значения в зависимости от реализации, в решении из разбора const = 10.