Зимняя школа по программированию, 2013

Зимняя школа по программированию, 2013.

Фрагмент из книги:
Пусть есть прямоугольная карта размера NxM, разбитая на квадратные клетки 1x1. Некоторые из клеток являются занятыми, остальные свободные. На этой карте имеются два циклических ориентированных маршрута. Оба маршрута проходят через пустые клетки таким образом, что любые две соседние клетки в плане маршрута являются соседними в одном из четырех направлений: верх, низ, лево, право. То есть каждый из маршрутов можно описать координатами его начальной клетки и списком команд четырех типов: вверх (U), вниз (D), влево (L), вправо (R). Команды описывают движение по маршруту.




Задача A. Automaton.
Вход:    stdln
Выход:    stdout
Ограничение по времени:    1 с
Ограничение по памяти:    256 Мб

Дана строка S. Построить детерминированный конечный автомат, принимающий все суффиксы строки S (и возможно другие конечные строки). Автомат должен состоять из минимального числа состояний — N и не более чем 2N переходов. Каждое состояние автомата объявляется финальным. Начальное состояние имеет номер 1.
На изображении ниже показан автомат из тестового примера для строки “abacaba".

Формат входного файла.
В единственной строке слово S, состоящее из строчных латинских букв.

Формат выходного файла.
В первой строке два числа N и К — количество состояний и количество переходов. Далее К строк, в каждой из которых по два числа аi, bi, и буква сi, означающие наличие перехода из состояния ai в bi по букве сi. Переходы можно выводить в любом порядке. Если решений несколько, можете вывести любое из них.

ОГЛАВЛЕНИЕ.
День первый. Контест Akai.
Об авторе.
Теоретический материал. Топологическая задача о маршрутах.
Задачи и разборы.
Задача A. Automaton.
Задача В. Bims.
Задача С. Cutting.
Задача D. Disclosure.
Задача Е. Embedded circles.
Задача F. False figures.
Задача G. Grouping.
Задача H. Hidden triangles.
Задача I. Interactive.
Задача J. Journey.
Задача К. Knuth knows.
Задача L. Lake.
Задача M. Match them up.
Задача N. Need for sum thing.
Задача О. Open air.
Задача P. Pseudo automaton.
Задача Q. Quiz.
Задача R. Reduction.
День второй. Контест Бондаренко Натальи Павловны.
Об авторе.
Теоретический материал. Потоки в сетях.
Задачи и разборы.
Задача А. Самая простая задача.
Задача В. Оптимальный поток величины 1.
Задача С. Максимальный поток в неориентированном графе.
Задача D. Задача про минералку.
Задача Е. В поисках невест.
Задача F. Задача о назначениях.
Задача G. План эвакуации.
Задача Н. Два кратчайших пути.
Задача I. Остоз.
Задача J. Поток в меняющейся сети.
Задача К. Произвольная циркуляция.
Задача L. Сетевые войны.
Задача М. Снег в Берляндии.
День третий. Контест Алексея Шмелева.
Об авторе.
Теоретический материал. Использование STL для решения олимпиадных задач (алгоритмы, контейнеры, примеры, ошибки).
Задачи и разборы.
Задача A. DOMA 2: Last Hit.
Задача В. Last Effect 3: Danger.
Задача С. Fineage: Training.
Задача D. DOMA 2: Inventory.
Задача E. South Mark: 3.50.
Задача F. HOLM 2: The Great Battle.
Задача G. Failout Few Vegas: Slow Save.
Задача H. Carmarandom TDC2013: New Trace.
Задача I. X-Dom: Railway.
Задача J. MindCraft: Heliport.
Задача К. Double Life: Amplifiers.
День четвертый. Контест Неспирного Виталия Николаевича.
Об авторе.
Теоретический материал. Линейное программирование и матричные игры.
Задачи и разборы.
Задача А. Неприводимые многочлены High.
Задача В. Неприводимые многочлены Junior.
Задача С. До первого выпадения High.
Задача D. До первого выпадения Junior.
Задача Е. Раскраска забора High.
Задача F. Раскраска забора Junior.
Задача G. Города-побратимы High.
Задача Н. Города-побратимы Junior.
Задача I. Отдых у реки High.
Задача J. Отдых у реки Junior.
Задача К. Количество представимых High.
Задача L. Количество представимых Junior.
Задача М. Квадратичная перестановка High.
Задача N. Квадратичная перестановка Junior.
Задача О. Цикл де Брёйна High.
Задача Р. Цикл де Брёйна Junior.
Задача Q. Карточный поединок High.
Задача R. Карточный поединок Junior.
Задача S. Посадка в самолет High.
Задача Т. Посадка в самолет Junior.
День пятый. Контест Геральда Агапова и Фефера Ивана.
Об авторах.
Теоретический материал. Топологическая сортировка онлайн.
Задачи и разборы.
Задача А. Обнаружение циклов.
Задача В. Топологическая сортировка.
Задача С. Расписание на дереве.
Задача D. Братья по крови наносят ответный удар.
Задача Е. Гиперраздление.
День шестой. Контест Фефера Ивана и Геральда Агапова.
Теоретический материал. Суффиксное дерево.
Задачи и разборы.
Задача А. Черно-белый куб.
Задача В. Один-два.
Задача С. Оптимальное разрезание.
Задача D. Граф-турнир.
Задача Е. Замок в виде мини-игры.
Задача F. Количество запросов.
Задача G. Две перестановки.
Задача Н. Робот-конь.
Задача I. Прыг-скок.
Задача J. Суффиксное дерево.
Задача К. Суффиксное дерево двух строк.
Задача L. Уникальные суффиксы.
Задача М. Общая подстрока.
Задача N. Контролирующее множество строк.
День седьмой. Контест Куликова Егора Юрьевича.
Об авторе.
Теоретический материал. Суффиксный автомат.
Задачи и разборы.
Задача A. Chords.
Задача В. Cyclic suffixes.
Задача С. A Coloring Game.
Задача D. Hippopotamus.
Задача Е. False RSA.
Задача F. Perspective.
Задача G. Circular Railway.
Задача Н. SETI.
Задача I. 2-3 Trees.
День восьмой. Контест Гольдштейна Виталия Борисовича.
Об авторе.
Теоретический материал. Кратчайшие пути в графах.
Задачи и разборы.
Задача А. Красная Шапочка.
Задача В. Уборка снега.
Задача С. Юный поджигатель.
Задача D. Реклама.
Задача Е. Космический мусорщик.
Задача F. Shortest Path.
Задача G. Дом улыбок.
Задача Н. Сфера.
Задача I. Домой на электричках.
Задача J. Поле чудес.
Задача К. Квадрат.
Задача на самый короткий код.
День восьмой. Контест Рипатти Артема Валерьевича.
Об авторе.
Задачи и разборы.
Задача А. Игра со стрелками.
Задача В. Гарри Поттер и философский камень.
Задача С. Преобразование последовательности.
Задача D. Отрезки.
Задача Е. Четыре подмножества.
День девятый. Контест Копелиовича Сергея Владимировича.
Об авторе.
Теоретический материал. Динамика и жадность 20 лет спустя.
Задачи и разборы.
Задача А. Белоснежка и n гномов.
Задача В. Эльфы и олени.
Задача С. Приключение.
Задача D. Авторитеты.
Задача Е. Коробки.
Задача F. Простые пути в дереве.
Задача G. Редукция дерева.
Задача Н. Изоморфные деревья.
Задача I. К минимумов на отрезке.
Задача J. Инверсии отрезка.
Задача К. Продуктивный бинпоиск.
Задача L. Командный пункт.
Задача М. Общая подпоследовательность.
Задача N. Различные подпоследовательности.
Задача О. Наибольшая общая возрастающая.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Зимняя школа по программированию, 2013 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по программированию :: программирование