9.8. Все задачи

Контрольный вопрос 9.1: Как найти ответы на эти подзадачи?

Задача 9.2: Решите задачу, про которую я говорил выше. Есть неограниченное количество монет достоинства \(a_1\), неограниченное количество монет достоинства \(a_2\) и т.д., до \(a_N\). Требуется проверить, можно ли набрать сумму \(S\) этими монетами. Постарайтесь решить её за \(O(NS)\). Решать задачу, конечно, нужно динамикой. Тут вы поймёте, чем так некрасиво двойное присваивание во второй строке.

Задача 9.3: Решите эту задачу (либо в том варианте, который мы разбирали, либо в варианте из предыдущего задания), только с дополнительным вопросом: если набрать данную сумму можно, то каким минимальным количеством монет?

Задача 9.4: Попробуем, как и раньше, в качестве подзадач рассматривать задачу поиска оптимального пути от \((1,1)\) до \((i,j)\) для всех \(i\) и \(j\). Поймите, почему принцип оптимальности для подзадач тут не будет выполнен, и, соответственно, почему нельзя решить эту задачу напрямую аналогично обычной задаче про черепашку.

Задача 9.5: Придумайте, какие подзадачи тут можно рассмотреть, чтобы принцип оптимальности выполнялся, и решите-таки эту задачу методом ДП.

Задача 9.6: Решите эту задачу

Задача 9.7: Зачем нужны эти три условия?

Задача 9.8: Поймите, почему тут не работает принцип оптимальности, почему эта задача не решается тупой динамикой и как одно связано с другим.

Задача 9.9: Вспомните задачу про монеты. Там тоже каждой монетой можно было пользоваться не более одного раза, но при этом задача благополучно решалась динамикой. Чем таким наша задача отличается от задачи про монеты? Можете ли придумать какую-нибудь задачу, которая казалась бы близкой к нашей задаче про черепашку, но решалась бы динамикой аналогично задаче про монеты?

Контрольный вопрос 9.10: Понимаете ли вы, что остальные элементы в этих примерах считаются корректно?

Задача 9.11: Напишите аналогично задачу про монеты.

Задача 9.12: Какую задачу будет решать этот же код, но с циклом по \(j\) в обратном порядке, т.е. от \(a[i]\) до \(s\)?

Задача 9.13: Напишите процедуру \(out\) для случая, когда мы ввели нулевые элементы массива так, как это было сказано в соответствующем разделе.

Задача 9.14: Избавьтесь от рекурсии в какой-нибудь из приведённых выше процедур \(out\)

Задача 9.15: Научитесь выводить первое в лексикографическим порядке решение задачи про черепашку с набором максимальной суммы. Решение задаём строкой из букв ’R’ и ’U’ и лексикографический порядок на этих строках определяем как всегда.

Задача 9.16: Научитесь выводить \(k\)-ый в лексикографическом порядке путь черепашки в задаче с подсчётом количества путей.

Задача 9.17: Напишите эту программу.

Задача 9.18: Напишите программу определения номера по пути в задаче про черепашку с подсчётом числа путей.

Задача 9.19: Напишите такую программу.

Задача 9.20: Напишите программу перебора всех решений задачи про монеты.

Задача 9.21: Решите эту задачу.

Задача 9.22: Задача 7 «Числа» с региональной олимпиады — 2009

Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.

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

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

Задача 9.23: Докажите эти соотношения (они не очевидны!)

Задача 9.24: Напишите процедуру \(out\) для вывода решения в этой задаче.

Задача 9.25: Подумайте над тем, как тут выводить первое в лексикографическом порядке решение. По-моему, это не очень тривиально.

Задача 9.26: Придумайте контрпримеры к двум приведённым способам решения этой задачи

Задача 9.27: Решите задачу о наибольшей общей подпоследовательности трёх строк по аналогии с задачей для двух строк.

Задача 9.28: На самом деле строго мы это ещё не доказали. Докажите.

Задача 9.29: Напишите решение задачи про максимальный подпалиндром.

Задача 9.30: Важное задание! Напишите процедуру \(out\) вывода решения в этой задаче.

Задача 9.31: Научитесь выводить первое в лексикографическом порядке решение здесь.

Задача 9.32: Есть \(N\) вещей, у каждой из которых известен вес и стоимость. У нас есть рюкзак грузоподъемности \(W\), т.е. мы можем унести произвольный набор вещей при условии, что их суммарный вес не превосходит некоторого числа \(W\). Требуется среди всех таких наборов выбрать набор с максимальной суммарной стоимостью. Решите эту задачу за \(O(NW)\): найдите ответ и выведите само решение.

Задача 9.33: Напишите процедуру out вывода решения в этой задаче.

Задача 9.34: Дано дерево. Найдите в нем наибольшее паросочетание, т.е. набор рёбер такой, что 1) никакие два ребра не имеют общего конца, 2) число рёбер максимально возможно. Напишите как само ДП, так и процедуру \(out\) вывода решения.

Задача 9.35: Додумайте эту задачу.

Задача 9.36: В кучке лежат \(N\) камешков. Двое игроков ходят по очереди. Первый своим ходом может взять из кучи от 3 до 5 камешков, второй — добавить в кучу 1 или 2 камешка. Выигрывает тот, после чьего хода камешков в куче не останется или количество камешков в куче будет делиться на 30, либо после чьего хода противник не сможет сходить. Кто выигрывает при правильной игре? (Эту задачу я только что придумал. Может так оказаться, что тут есть простая закономерность, например, всегда выигрывает второй, я не знаю. Но в любом случае придумайте динамическое решение за \(O(N)\).)

Задача 9.37: Напишите процедуру out вывода решения в этой задаче.

Задача 9.38: Задача «Перестановки» с региона-2009.

Задано множество из \(n\) различных натуральных чисел. Перестановку элементов этого множества назовем \(k\)-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее \(k\). Например, если задано множество элементов \(S = {6, 3, 9, 8}\), то перестановка \({8, 6, 3, 9}\) является 2-перестановкой, а перестановка \({6, 8, 3, 9}\) – нет.

Перестановка \({p_1, p_2, \dots, p_n}\) будет лексикографически меньше перестановки \({q_1, q_2, \dots, q_n}\), если существует такое натуральное число \(i\) (\(1 ≤ i ≤ n\)), для которого \(p_j = q_j\) при \(j < i\) и \(p_i < q_i\).

В качестве примера упорядочим все \(k\)-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества \(S\): \({3, 9, 6, 8}\), \({8, 6, 3, 9}\), \({8, 6, 9, 3}\) и \({9, 3, 6, 8}\). Соответственно, первой 2-перестановкой в лексикографическом порядке является множество \({3, 9, 6, 8}\), а четвертой – множество \({9, 3, 6, 8}\).

Требуется написать программу, позволяющую найти \(m\)-ую \(k\)-перестановку в этом порядке.

(конец условия задачи)

…на самом деле это — отличная задача на теорию ДП. Вам потребуется, во-первых, динамика по подмножествам, во-вторых, умение по объекту находить номер. Обратите внимание, что ДП по подмножествам потребует тут ещё одного параметра, кроме самого подмножества, но зато обойдётся без этих мучений с поиском какого-нибудь элемента множества.

Задача 9.39: Научитесь выводить симпатичный узор по номеру. Т.е. придумайте, в каком порядке симпатичные узоры можно занумеровать так, чтобы вы смогли по номеру вывести узор, и научитесь это делать.

Задача 9.40: Сколько есть способов расставить королей на доске \(N\times M\) так, чтобы никто из них никого не бил? Не знаю, вдруг тут есть формула, но решите эту задачу динамикой по профилю. Тогда вы сможете решить и такую задачу: на доске \(N\times M\) несколько клеток вырезаны. Сколькими способами на оставшихся клетках можно расставить королей, чтобы никто никого не бил?

Задача 9.41: Найти число способов разложить данное число \(N\) в сумму слагаемых: а) считая разложения, различающиеся порядком слагаемых, различными; б) считая разложения, различающиеся порядком слагаемых, одинаковыми; в) считая разложения, различающиеся порядком слагаемых, одинаковыми и требуя, чтобы все слагаемые в каждом разложении были различны; г) и т.п.

Задача 9.42: Найти число правильных скобочных последовательностей, состоящих из \(N\) пар скобок. [Коротко говоря, правильная скобочная последовательность — это последовательность открывающих и закрывающих скобок, в которой скобки сбалансированы. (()) — это правильная скобочная последовательность из двух пар скобок, ()() — тоже, а )()( и ())( — нет. Я надеюсь, смысл определения понятен].

а) Используя только круглые скобки;

б) используя круглые, квадратные и фигурные скобки: ()[], [{}] — правильные, а ({)} и )()( — нет.

Научитесь выводить скобочную последовательность по номеру.

Задача 9.43: Сколькими способами можно замостить доску \(N\times M\) доминошками?

Задача 9.44: Дана строка \(s\), состоящая из букв, и маска \(m\). Маска может содержать буквы, символы * и ?. Звёздочка может обозначать любую строку (в т.ч. пустую), а знак вопроса — любой символ. Подходит ли данная строка под эту маску? (Например, строка abcdefg подходит под маску ab*f?, но не под ab?f?.)

Задача 9.45: При умножении матрицы размера \(a\times b\) на матрицу \(b\times c\) получается матрица \(a\times c\), при этом, чтобы выполнить такое умножение, требуется выполнить \(abc\) умножений отдельных чисел. (Т.е. сложность операции умножения матриц — \(O(abc)\).) Умножение матриц не коммутативно (т.е. матрицы нельзя менять местами: \(AB\neq BA\)), но ассоциативно (т.е. в любом выражении можно расставлять скобки как угодно, результат от этого не изменится: \(A(BC)=(AB)C\)). Правда, от расстановки скобок в выражении зависит количество необходимых умножений чисел. Соответственно, получается задача. Дано выражение \(A_1\cdot A_2\cdot\ldots\cdot A_n\), где \(A_1\), \(A_2\) и т.д. — матрицы; размер матрицы \(A_i\)\(r_i\times c_i\), при этом \(c_i=r_{i+1}\) для всех \(i\). Требуется в выражении расставить скобки (т.е. указать порядок выполнения действий) так, чтобы потребовалось как можно меньше умножений чисел.

Задача 9.46: Дана строка \(s_1\). Разрешается за одно действие либо удалить произвольный символ текущей строки, либо вставить произвольный символ в произвольное место текущей строки, либо изменить произвольный символ текущей строки (на любой символ по вашему выбору).

а) Требуется за наименьшее число действий получить данную строку \(s_2\).

б) То же самое, но за каждое действие есть штраф: \(d\) за удаление, \(i\) за вставку и \(c\) за замену, требуется минимизировать штраф.

в) То же самое, но штрафы зависят от того, что это за символы (т.е. штраф за удаление зависит от того, какой символ удаляем и т.д.; все эти зависимости заданы во входном файле).

г) и т.д.

Задача 9.47:

TeX’s line-breaking algorithm has proved to be general enough to handle a surprising variety of different applications; this, in fact, is probably the most interesting aspect of the whole TeX system.

Donald E. Knuth. The TeX book.

Алгоритм TeX’а для разбиения строк оказывается достаточно всеобщим для того, чтобы справиться с удивительным разнообразием различных приложений. Фактически, это, вероятно, наиболее интересный аспект в системе TeX.

Дональд Е. Кнут. Все про TeX.

Идея и код фигурного абзаца тоже взяты из TeXbook.

../_images/paragraph.png