Первая задача на реализацию. Надо было пройтись циклом по строке и все согласные буквы скопировать в новую строку. После этого пробежаться по полученной строке и перед каждой буквой вывести ‘.’.
Вторая задача также чисто на реализацию. Ее можно было выполнить следующим образом. Если задано n, то надо было вывести 2 * n + 1 строк для узора. При этом для строки I (0 <= I <= N) – количество пробелов в начале строки будет равно 2 * N – i. Для строки с номером I от N + 1 до 2 * N количество пробелов равно (I - N) * 2.
Таким образом, узор формируется следующим образом: сначала выводим соответствующее количество пробелов для нужной строки, потом соответствующую последовательность цифр. Каждая строка в решении должна заканчивать переводом строки и не содержать лишних пробелов в конце.
Итак, в задаче требуется получить наиболее красивый номер и затратить как можно меньше денег для этого. Разобьем задачу на подзадачи и решим ее для каждой цифры в отдельности. Чтобы затратить наименьшее количество денег и сделать максимальное количество замен следует для каждой цифры С заменять в номере все цифры отличные от нее сначала по модулю 1, затем по модулю 2, затем по модулю 3 и т д по возрастанию модуля, в этом и только в этом случае набранная сумма будет наименьшей. Естественно, если произведено нужное количество замен K, то работу алгоритма стоит прекратить. Однако, чтобы получить лексикографически наименьшую строку K с цифрами С, то надо производить замены следующим образом. Пусть на данном шаге алгоритма мы хотим поменять все цифры, отличные от цифры С по модулю I, то есть в строке все цифры С + I и цифры С – I заменить на цифру С. В таком случае сначала стоит заменять все цифры С + I на С, и замены производить с начала строки. А после поменять все цифры С – I на C, и замены производить с конца строки. В этом случае Петя потратит наименьшее количество денег, и получит лексикографически наименьший номер.
После останется выбрать наилучший ответ из 10 строк. Таким образом, асимптотическая сложность алгоритма равна 10 * 10 * n.
Задача решается ленивой динамикой. Пусть z[n1][n2][2] – это количество способов расставить войска в легионе Цезаря. Параметры обозначают следующее, n1 – это пехотинцы, n2 – это всадники, третий параметр обозначает какие войска ставит Цезарь в начало шеренги. Переходы следующие: если Цезарь хочет поставить n1 оставшихся пехотинцев в шеренгу, то из состоянии z[n1][n2][0] можно перейти в состояние z[n1 – i][n2][1], где I такое что (0 <= I <= min(n1, k1)). Если же Цезарь хочет поставить всадников, то из состояние динамики z[n1][n2][1] переходим в состояние z[n1][n2 – i][0], где 0 <= I <= min(k2, n2).
Формально задачу можно поставить так. Нам задан неориентированный связный граф, надо ориентировать его дуги таким образом, чтобы получился сильно связный ориентированный граф. Известна следующая теорема (на теоретической базе которой написана задача), что такой граф допускает ориентацию к сильно связному орграфу тогда и только тогда, когда каждое ребро входит в какой либо цикл.
Чтобы это проверить, достаточно запустить обход в глубину из произвольной вершины и ориентировать ребра графа в направлении этого обхода. Получилась некоторая ориентация графа. Чтобы убедиться, что в исходном графе нет мостов, достаточно взять полученную ориентацию графа, поменять в ней направление дуг, и проверить, что сохраняется сильная связность. Это можно сделать вторым поиском в глубину. Если сильная связность сохраняется, то ответом на задачу будет ориентация, полученная при первом обходе в глубину.
