ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Антон и Виктор, сидят за столом и пьют чай.
Антон пальцем собирает пыль с печатной машинки. Затем, делает глоток чая.
ВИКТОР Может еще чаю?
АНТОН Нет, мне хватит.
ВИКТОР Говоришь, что хочешь стать писателем?
АНТОН Да, очень. Но я не знаю, что для этого нужно.
ВИКТОР В первую очередь одержимость... Твоя мать знает, что ты здесь?
АНТОН Нет. Мама бы никогда в жизни меня не отпустила.
ВИКТОР Да, она одержима тобою, и твоей безопасностью. Её понять можно.
АНТОН Зачем тебе все эти книги?
ВИКТОР Чтобы стать писателем нужна хорошая идея и огромные знания. Идея у меня есть. Но знаний, чтобы её реализовать, у меня не достаточно.
АНТОН Мать говорит, ты болен. Она не хочет меня к тебе отпускать, потому что боится, что ты меня заразишь.
ВИКТОР Глупая женщина. Удивляюсь, почему она тебя еще не держит в изоляции.
АНТОН Я ей не позволяю.
ВИКТОР У тебя есть друзья?
АНТОН Один друг... И тот, наверное, скоро тоже предаст.
ВИКТОР Ты что ступил не на тот путь, о котором вечно твердит твоя мать?
АНТОН Нет, просто они меня не понимают. Мне с ними не интересно. Были бы в разных классах, может и не общались бы.
ВИКТОР Понятно.
АНТОН Расскажи о своей идее.
ВИКТОР Интересная просьба. (указывая на стопки книг) Ты найдешь её в этих книгах. Изучай их и поймешь. В них заложено много идей, только нужно научиться их оттуда...
Виктор мерзко кашляет. Достает платок, прикрывает им рот. На платке остаются пятна крови.
ВИКТОР Нужно поторапливаться. У меня мало времени, сынок. Езжай домой. Мне нужно поработать... Для начала, советую тебе изучить труды Аристотеля, Платона и Сократа.
Он поднимается с места. Из разных стопок книг находит произведения этих трех авторов. Вручает их Антону и торопливо провожает к выходу. Антон прячет книги в рюкзак. Обувается, набрасывает верхнюю одежду.
АНТОН Я могу приходить к тебе?
ВИКТОР Можешь.
АНТОН Когда захочу?
ВИКТОР Когда захочешь.
АНТОН Спасибо, пап.
Обнимает отца.
ВИКТОР Пожалуйста... беги.
Антон уходит. Виктор закрывает за ним дверь. Некоторое время еще стоит у двери. Затем, ступает к печатной машинке.
АНТОН Ты помнишь... когда я пришел к тебе в первый раз после нашей встречи?
ВИКТОР Помню.
Антон толкает дверь и входит в квартиру. На плече тот же рюкзак. За столом сидит Виктор и набирает текст на печатной машинке.
АНТОН Привет, пап! Почему дверь не заперта?
ВИКТОР Ты что уже изучил те книги?
АНТОН Да, я их принес.
Вытягивает из рюкзака древнегреческих философов.
ВИКТОР Оставь их там, и бери другие.
АНТОН Хорошо.
Оставляет книги на полу.
АНТОН Какие на этот раз?
ВИКТОР Бери те, что ближе. Изучай все подряд.
Антон берет первую стопку книг и засовывает в рюкзак.
Затем, некоторое время молча наблюдает за тем, что делает Виктор.
АНТОН Можно посмотреть, что ты делаешь?
ВИКТОР Нет. Ты только помешаешь... Взял книги?
АНТОН Да.
ВИКТОР Тогда, иди, изучай их. Чтобы стать писателем, нужно много работать.
АНТОН Ладно... пока!
Не спешит уходить. Ждет реакции отца. Нет реакции.
АНТОН Пока, пап!
Виктор наконец-то ставит точку и оборачивается к Антону.
ВИКТОР Пока, сынок. Изучай внимательней эти книги.
Антон кивает и уходит.
Виктор некоторое время смотрит ему вслед. Достает сигарету, закуривает, и продолжает печатать.
АНТОН Ты помнишь, когда я приехал к тебе в третий раз?
Виктор виновато молчит.
Чистый лист торчит из печатной машинки. Рядом с машинкой, текстом вниз лежат друг на друге две напечатанные страницы.
Виктор, сидя на стопке книг, бегло просматривает какую-то литературу. Скорее, ищет в ней некую информацию.
Пролистав полностью, не довольно отбрасывает в сторону и берет другую книгу.
В это время, в квартиру входит Антон.
АНТОН Привет, пап.
ВИКТОР Зачем пришел?
АНТОН (не понимая слов отца) За новыми книгами.
ВИКТОР (сердито) У меня такое чувство, что ты с ними плохо работаешь.
АНТОН Нет, я их внимательно читаю.
ВИКТОР (сердито, скорее из-за того, что он не может найти то, чего хочет) А ты хотя бы что-нибудь понял из того, что уже прочитал?
АНТОН Не все, конечно, но многое.
ВИКТОР И ты можешь, сложив эти знания, создать нечто новое?
АНТОН Еще нет.
ВИКТОР Ладно, бери нужные книги и уходи, не отвлекай.
Антон меняет свои книги на другие.
АНТОН Пап, может тебе помочь?
ВИКТОР У тебя недостаточно знаний. Будешь только мешать.
АНТОН (обиженно) Ладно, пока.
Идет к выходу.
ВИКТОР (отбрасывая книгу) Черт, где же оно?
Антон, постояв у двери несколько секунд, уходит.
АНТОН А на восьмой раз, ты меня даже не заметил.
Виктор виновато молчит. На глаза наворачиваются слезы.
Рядом с печатной машинкой друг на друге лежат десять листов печатного текста.
Виктор лихорадочно пробивает по кнопкам печатной машинки, заканчивая очередной лист.
В зубах покоится сигарета, пепел которой вот-вот упадет.
Тем временем, дверь в квартиру отворяется и входит Антон.
АНТОН Привет, пап!
Секунду ожидает реакции отца. Нет реакции.
Тогда он вынимает из рюкзака шесть книг и оставляет их на полу. Забирает следующую стопку.
Виктор ставит точку и вытягивает листик из печатной машинки. Пробегает внимательным взглядом по тексту. Берет карандаш, делает какие-то пометки. Снова проверяет текст. Сбивает накопившийся на сигарете пепел. Поправляет очки на лице. Оставляет лист текстом вниз поверх остальных десяти страниц.
Тут же, не сбиваясь с мысли, вставляет в машинку следующий лист и, задумчиво взглянув на сына, продолжает стучать по клавишам.
Антон, презрительным взглядом, наблюдает за отцом.
Уходит.
АНТОН Интересно, ты помнишь, когда снова стал запирать двери?
Виктор виновато молчит, стараясь не поддаться слабости.
АНТОН А ты помнишь, когда я перестал к тебе приходить за новыми книгами?
ВИКТОР (старается вспомнить, слезы текут по щекам) Нет, я не помню.
Виктор, склонив голову, тихо всхлипывает. Антон хладнокровно наблюдает за отцом.
АНТОН Я принес тебе гостинец.
Оставляет бутылку вина на столе.
АНТОН Год назад я познакомился с прекрасной девушкой... У неё мамины волосы... Собираемся скоро пожениться.
АНТОН А это... от матери.
Антон достает из черного пакета... свою книгу и кладет на стол перед отцом.
АНТОН Если бы не она, ты бы купил её только в каком-нибудь книжном магазине.
Отец незаметно вытирает слезы. Поднимает трепетный взгляд на книгу. Осторожно поднимает обложку, добирается до краткого содержания в начале.
Пробегает по нему взглядом. То, что он читает, шокирует его.
Закрывает книгу. Отодвигает от себя.
Забирает все свои напечатанные страницы. Бросает в мусорное ведро. Достает спички.
АНТОН Что ты делаешь?
ВИКТОР Моя книга... не может существовать, если в ней нет самой важной главы... Вопрос раскрыт. Нет смысла отвечать на него дважды.
Дрожащими руками зажигает спичку. Бросает спичку в ведро. Огонь постепенно съедает рукопись.
Виктор вынимает из пачки последнюю сигарету. Закуривает. Отходит к окну. Наблюдает, как солнце садится за горизонт.
Антон поднимается с места, подходит к печатной машинке, из которой торчит еще один листик, и пробегает взглядом по содержанию этого листика.
СОДЕРЖАНИЕ ЛИСТИКА: «Глава 64. Извечная борьба двух поколений. Родители и дети. «Вечное непонимание между жителями этих двух лагерей ведет к одному из наиболее острых конфликтов, на решение которого, чаще всего, уходит вся жизнь. Ибо, чтобы одни поняли других нужно прийти к компромиссу двух мировоззрений. Молодежь вечно играет роль бунтарей, тогда как родители – устоявшаяся власть, принципы и железные законы. И, именно, неприятие традиций предков рождает «элиту» нового времени».
Антон заглядывает в ведро на догорающую рукопись. Огонь переворачивает страницы, и прежде, чем уничтожить их, показывает некоторые главы: «Глава 52. Религия как догма; Глава 49. Что такое Вера; Глава 59. Вопросы, которые Воля ставит перед нами»
В пепельнице дотлевает последний бычок. Тонкая струйка дыма поднимается к потолку.
За окном восходит солнце.
На кровати умиротворенно лежит бездыханное тело Виктора с приоткрытым бледным ртом.
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Метод динамического программирования состоит в разбиении задачи на подзадачи, решении их и объединении результатов. В отличии от метода «разделяй и властвуй», динамическое программирование используется, когда подзадачи не являются независимыми. Чтобы не решать некоторые подзадачи несколько раз (как это делалось бы при использовании стратегии «разделяй и властвуй»), при динамическом программировании подзадачи решаются один раз и результат решения заносится в некоторую таблицу. Решение задачи методом динамического программирования как правило требует наличия рекуррентного соотношения между подзадачами. Скорость решения задач этим методом как правило полиномиальна, в отличии от методов полного перебора или бектрекинга.
1. Монеты. Имеются монеты достоинством v 1, v 2, …, vn копеек. Необходимо найти наименьшее количество монет, которыми можно выдать сумму S.
2. Задача о загрузке. Меется судно грузоподъемностью w и n предметов. Известно, что i - ый предмет имеет вес wi и ценность ci. Необходимо загрузить судно предметами так, чтобы получить максимальную прибыль. Вход. Первая строка содержит количество предметов n и грузоподъемность судна w. Следующие n строк содержат характеристики грузов: в i - ой строке находится вес wi и ценность ci i - го груза. Выход. Максимальная суммарная ценность грузов, которыми можно загрузить судно.
3. Доллары [Вальядолид, 147, 357, 674]. Валюта Новой Зеландии состоит из купюр 100$, 50$, 20$, 10$, 5$ и монет 2$, 1$, 50c, 20c, 10c, 5c. Необходимо определить количество способов, которыми можно составить заданную сумму. Например, 20 центов можно представить четырьмя способами: 20, 10 + 10, 10 + 5 + 5, 5 + 5 + 5 + 5. Вход. Состоит из нескольких действительных чисел, представляющих собой денежную сумму в долларах. Каждая входная сумма не более 300.00$ и кратна 5 центам. Последний тест содержит сумму 0.00 и не обрабатывается. Выход. Для каждого теста вывести денежную сумму, выровненную справа в поле длины 6, и число способов ее представления, выровненную справа в поле длины 17.
4. Оптимальное умножение матриц [Вальядолид, 348]. Для умножения матрицы А размера x ´ y на матрицу В размера y ´ z следует выполнить x * y * z операций. Необходимо вычислить произведение матриц A1 * A2 * … * A n, сделав при этом минимальное количество операций умножения. Рассмотрим пример. Пусть имеются три матрицы со следующими размерами: X – 5 ´ 10, Y – 10 ´ 20, Z – 20 ´ 35. Перемножим матрицы в последовательности ((X Y) Z): · XY: 5 * 10 * 20 = 1000 операций, получим при этом матрицу размера 5 ´ 20; · ((X Y) Z): 5 * 20 * 35 = 3500 операций; · Общее число умножений равно 4500. Перемножим матрицы в последовательности (X (YZ)): · YZ: 10 * 20 * 35 = 7000 операций, получим при этом матрицу размера 10 ´ 35; · (X (YZ)): 5 * 10 * 35 = 1750 операций; · Общее число умножений равно 8750. Таким образом, для минимизации числа умножений следует перемножить матрицы в последовательности ((X Y) Z). Вход. Первая строка каждого теста содержит количество перемножаемых матриц n (n £ 10). Далее следуют n строк, каждая из которых содержит два числа – размер матрицы A i (1 £ i £ n). Выход. Следует перемножить матрицы A1 * A2 * …* A n., произведя наименьшее количество умножений. Оптимальный порядок перемножения матриц вывести согласно формату, приведенному ниже.
Вход. Состоит из пар строк. Первая строка содержит первую последовательность, а вторая строка – вторую последовательность. Каждая входная последовательность содержит не более 1000 символов. Выход. Для каждого теста вывести в отдельной строке длину наибольшей общей подпоследовательности.
6. Путешествие Теобальдо [Вальядолид, 10681]. Теобальдо необходимо совершить переход из города s в город e, затратив на него не более чем d дней. Так как Теобальдо ленивый, он хочет потратить на путешествие максимально возможное число дней. Каждый следующий день Теобальдо должен переходить из одного города в другой. В задаче требуется узнать, сможет ли Теобальдо выполнить переход. Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество городов c (0 < c £ 100) и количество дорог l (0 £ l £ 500) между городами. Каждая из следующих l строк содержит номера двух городов A и B (1 £ a, b £ c, a ¹ b), соединенных дорогой. Далее следует строка, содержащая номер начального города s, номер конечного города e и максимальное число дней d (0 £ d £ 200), отведенное на путешествие. Последний тест содержит c = l = 0 и не обрабатывается. Выход. Для каждого теста вывести сообщение о том, сможет ли Теобальдо совершить переход, в соответствии с ниже приведенным форматом.
7. Путешествующий торговец [Вальядолид, 10702]. Джин – путешествующий торговец. Он ходит по городам, продавая и покупая товары. Страна, по которой он ходит, состоит из С городов. Начиная свой путь из города S, Джин должен сделать T переходов между городами. Торговцу разрешается посещать города, в которых он уже был. Свой путь Джин должен завершить в одном из E городов. Известна прибыль, которую Джин получает, совершив переход из i - го города в j - ый. Необходимо вычислить максимальную прибыль, которую он может получить, пройдя весь путь. Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит четыре целых числа: количество городов C (2 £ С £ 100), номер начального города S (1 £ S £ 100), число финальных городов E (1 £ E £ 100) и количество переходов T (1 £ T £ 1000). Следующие С строк содержат по С чисел. j - ое число i – ой строки содержит прибыль, которую получит Джин совершив переход из i - го города в j – ый. Поскольку Джин не может идти из i - ого города в i - ый, то i - ое число i – ой строки содержит 0. Далее в одной строке следуют E номеров городов, в которых торговец может завершить свой путь. Последний тест содержит C = S = E = T = 0 и не обрабатывается. Выход. Для каждого теста вывести максимальную прибыль, которую Джин может получить завершив свой путь.
8. Трамваи в Барселоне [Вальядолид, 10767]. Трамвай должен проехать по маршруту P0, P1, …, P n. Расстояние между остановками P i -1 и P i равно S i. Каждую часть пути S i водитель должен проезжать с постоянной скоростью v i, которую он выбирает на остановке P i -1. Обозначим через M i максимально возможную скорость, которую водитель может выбрать на остановке P i -1 (0 < v i £ M i). Вероятность поломки трамвая на промежутке S i равна v i / M i. Если поломка имеет место на отрезке S i, то она случается как раз на середине пути, после чего в течении 10 секунд включается аварийная система и со скоростью 5 метров в секунду трамвай без поломок едет до остановки P i. Пусть M0 – максимально допустимая скорость трамвая, с которой он может выехать с начальной станции P0. Тогда максимальная скорость, с которой трамвай может выехать со станции P i -1, равна M i = M0 – C i, где C i – суммарное количество поломок на промежутках S1, …, S i -1. Вычисление среднего времени покажем на примере. Пусть длина пути равна 300 метров, максимально возможная начальная скорость равна 25 метров в секунду. Если водитель выберет скорость 25 м/с, то трамвай обязательно поломается. И тогда он проедет половину пути за 150 / 25 = 6 секунд, простоит 10 секунд и доедет с аварийной скоростью 5 м/с до следующей остановки за 150 / 5 = 30 секунд. Всего при этом потратив 6 + 10 + 30 = 46 секунд. Допустим, что водитель выбирает скорость 15 метров в секунду. С вероятностью 15 / 25 = 0.6 произойдет поломка. В случае поломки трамвай проедет 150 метров со скоростью 15 м/с (потратив на это 10 секунд), потом 10 секунд простоит и со скоростью 5 м/с доедет до конца (150 / 5 = 30 секунд). С вероятностью 0.4 трамвай не поломается и доедет до следующей остановки за 300 / 15 = 20 секунд. Средний час равен 0.6 * 50 + 0.4 * 20 = 38 секунд. В задаче необходимо вычислить наименьшее среднее время, за которое трамвай может проехать весь путь от остановки P0 до P n. Вход. Каждая строка соответствует одному тесту и содержит начальную максимально возможную скорость трамвая M0 (5 £ M0 £ 25), значение n (1 £ n £ M0 - 1) а также длины всех секций S1, …, S n. Выход. Для каждого теста вывести оптимальное среднее время, за которое трамвай проедет весь путь. Результат выводить с 4 десятичными знаками после запятой.
9. Распределение оценок [Вальядолид, 10910]. На экзамене один студент сдавал n предметов и получил в сумме t балов. Он сдал все n предметов, для зачета каждого следовало набрать минимум p балов. Определить, сколькими способами студент мог сдать экзамен. Например, при n = 3, t = 34, p = 10 оценки по предметам могут распределиться следующим образом:
Студент может сдать экзамен 15 способами. Вход. Первая строка содержит количество тестов. Каждый тест содержит в одной строке три числа n, t, p, значения каждого из которых не больше 70. Выход. Для каждого теста вывести количество способов, которыми студент может сдать экзамен. Ответ является знаковым 32-битовым числом.
10. Как Вы прибавляете? [Вальядолид, 10943]. По заданному целому n установить количество его разбиений на k неотрицательных слагаемых. Например, для n = 20 и k = 2 существует 21 разбиение: 0 + 20, 1 + 19, 2 + 18,..., 19 + 1, 20 + 0. Вход. Каждая строка содержит два целых числа n и k (1 £ n, k £ 100). Последний тест содержит n = k = 0 и не обрабатывается. Выход. Для каждого теста вывести количество разбиений числа n на k неотрицательных слагаемых. Ответ выводить по модулю 1000000.
11. Задача группирования [Вальядолид, 11026]. Имеется n чисел. Выберем из них группу из k элементов. Две группы считаются разными, если существует хотя бы один элемент, который принадлежит одной группе и не принадлежит другой. Группирующей системой будем называть множество всех возможных групп. Например, из четырех элементов a, b, c, d можно составить шесть групп по два элемента. Группирующей системой для множества { a, b, c, d } и k = 2 будет множество { ab, ac, ad, bc, bd, cd }. Похожестью группирующей системы называется число, равное сумме произведений всех элементов групп, взятой по модулю m. Похожесть для представленного выше примера для k = 1 равна F1 = (a + b + c + d) mod m. Для k = 2 похожесть равна F2 = (ab + ac + ad + bc + bd + cd) mod m. Для заданного множества чисел и среди всех всевозможных k = 1, …, n найти похожесть Fk с максимальным значением. Вход. Первая строка каждого теста содержит числа n (2 £ n £ 1000) и m (1 £ m £ 231). Следующая строка содержит n положительных целых чисел. Все числа не более 1000. Последний тест содержит n = m = 0 и не обрабатывается. Выход. Для каждого теста вывести значение максимальной похожести среди всех возможных групп.
12. Подсчет общих подпоследовательностей [Топкодер, раунд 298, дивизион 1, уровень 3]. Подпоследовательность образуется из строки удалением нуля или нескольких символов из нее. По заданным трем строкам следует подсчитать количество их разных непустых общих подпоследовательностей. Класс: CountingCommonSubsequences Метод: long long countCommonSubsequences(String a, String b, String c) Ограничения: a, b и c содержат от 1 до 50 символов ‘a’ – ‘z’. Вход. Три строки a, b и c. Выход. Количество общих подпоследовательностей трех строк a, b и c.
|
