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

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

Фрагмент из книги:
Для поиска увеличивающего пути можно попробовать запустить поиск в глубину из свободной вершины. Обход должен идти по чередующимся ребрам из паросочетания и не из него. Если найдется свободная вершина, то это будет означать наличие увеличивающего пути. Рассмотрим подробнее. Пусть есть некоторая вершина v при обходе и мы перебираем всех ее соседей не из паросочетания. Тогда в случае, если соседняя вершина и свободная, то найден увеличивающий путь, если насыщенная, но не посещенная, то надо ее посетить и запустить обход из ее пары в паросочетании.




Задача А. Ааа.
Имя входного файла: а. in
Имя выходного файла: a. out
Ограничение по времени: 2 с
Ограничение по памяти: 256 Мб

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

А началось все так:
Староста группы математиков на очередной абсолютно неважной паре занималась тем, что равномерно распределяла в области ближайшего окружения листочки с судоку. Саша не оказался обделенным вниманием, что послужило поводом заговорить.
— А, надеюсь, это самый сложный уровень?
— Как раз для тебя.
— Ну-ну, — видя глубокую иронию в ее глазах и то, что первые три строки судоку уже заполнены.
— Решишь — еще дам.
— Я тебе не просто решу, а скажу еще, сколько решений существует, — лихо заметил Саша, не подозревая, какие проблемы себе создал.
— Ну-ну.

Следующие два дня Саша занимался только тем, что искал количество решений судоку. Кстати, судоку — это головоломка, в которой предлагается заполнить таблицу 9 x 9 числами от 1 до 9 так, чтобы в каждой строке, столбце и каждом из 9 квадратов 3 х 3 все числа были различны. Изначально некоторые клетки уже заполнены и остается вписать числа в пустые клетки.
— А как девушку-то зовут?
— Ааа...

ОГЛАВЛЕНИЕ.
День первый. Контест Akai.
Об авторе.
Теоретический материал. Алгоритм Эдмондса о сжатии цветков.
Задачи и разборы.
Задача А. Ааа.
Задача В. Bachelor pursuing.
Задача С. Concatenation of credits.
Задача D. DeviantArt.
Задача E. Exam.
Задача F. Fate to hate.
Задача G. Genealogic tree.
Задача H. Happy Birthday.
Задача I. I love Ira.
Задача J. Justice.
Задача К. Knife to me.
Задача L. Lie to me.
Задача M. My Space.
Задача N. Now.
День второй. Контест Дворкина Михаила Эдуардовича.
Об авторе.
Теоретический материал. Приближенные алгоритмы для NP-полных задач.
Задачи и разборы.
Задача A. Points.
Задача В. Queens.
Задача С. Tangents.
День третий. Контест Неспирного Виталия и Лунева Антона.
Об авторах.
Теоретический материал. Конечные разности.
Задачи и разборы.
Задача А. СуперНим High (только для высшей лиги).
Задача В. СуперНим Junior (только для юниорской лиги).
Задача С. Хромой король High (только для высшей лиги).
Задача D. Хромой король Junior (только для юниорской лиги).
Задача Е. Изменение на отрезке High (только для высшей лиги).
Задача F. Изменение на отрезке Junior (только для юниорской лиги).
Задача G. К-цифровое число High (только для высшей лиги).
Задача Н. К-цифровое число Junior (только для юниорской лиги).
Задача I. Гиперкуб High (только для высшей лиги).
Задача J. Гиперкуб Junior (только для юниорской лиги).
Задача К. Кривая дракона High (только для высшей лиги).
Задача L. Кривая дракона Junior (только для юниорской лиги).
Задача М. Ферзи High (только для высшей лиги).
Задача N. Ферзи Junior (только для юниорской лиги).
Задача О. К-стороннее домино.
Задача Р. Различные попарные суммы.
День четвёртый. Контест Копелиовича Сергея Владимировича.
Об авторе.
Теоретический материал. Про алгоритм Йена и динамику.
Задачи и разборы.
Задача А. Сервера.
Задача В. Word period.
Задача С. Arithmetic.
Задача D. Таможенные правила.
Задача Е. Covering Points.
Задача F. Гамильтонов цикл в полном графе.
Задача G. PreQueL.
Задача Н. Sigma-функция на отрезке.
Задача I. Autotourism.
Задача J. Perfect Powers.
Задача К. Spell Checker.
Задача L. Valsum.
Задача М. Sprite.
Задача N. Suffarray.
Задача О. Foxes.
Задача Р. Cucarach.
Задачи на тему лекции.
Задача А. Длиннейший путь.
Задача В. Спички.
Задача С. Ideal Path.
Задача D. Strange People.
День пятый. Контест Жукова Дмитрия Ивановича.
Об авторе.
Задача А. Арифметическая прогрессия.
Задача В. Мирные кони.
Задача С. Четыре точки.
Задача D. Римские числа.
Задача Е. Камни.
Задача F. Две строки.
День шестой. Контест Гольдштейна Виталия Борисовича.
Об авторе.
Теоретический материал. Объединяемые структуры данных.
Задачи и разборы.
Задача А. Перекладываем камешки.
Задача В. Это левая куча?.
Задача С. Высота левого дерева.
Задача D. Правый путь левого дерева.
Задача Е. Объединение прямоугольников 2.
Задача F. Дерево.
Задача G. Дерево в отрезке.
Задача Н. Строки в дереве.
Задача I. Объединение прямоугольников.
Задача J. Объединяем множество.
Задача К. Непрефиксные коды.
Задача L. Дождик.
Задача на самый короткий код.
День шестой. Контест Неспирного Виталия и Лунева Антона.
Задачи и разборы.
Задача A. Minimal Prime Divisor.
Задача В. Isosceles Triangulation.
Задача С. XOR pairs.
Задача D. Win of the looser.
Задача E. Longest Geometric Progression.
День седьмой. Контест Куликова Егора Юрьевича.
Об авторе.
Теоретический материал. Дерево отрезков.
Задачи и разборы.
Задача А. Дима и знаменитый турист.
Задача В. Дима и строки.
Задача С. Дима и компьютерная игра.
Задача D. Дима и перестановка.
Задача Е. Дима и проценты.
Задача F. Дима & модуль.
Задача G. Дима и машина времени.
Задача Н. Дима и машина времени.
Задача I. Дима и массив.
Задача J. Дима и большой массив.
Задача К. Дима и массив-2.
Задача L. Дима и таблица.
Задача М. Дима и таблица-2.
День седьмой. Контест Мистряну Ивана Леонидовича и Щепина Алексея Юрьевича.
Об авторах.
Задачи и разборы.
Задача А. Полёт хомяка.
Задача В. Интервалы.
Задача С. Иерархия.
Задача D. Двоичные произведения.
Задача Е. Упаковочная машина.
День восьмой. Контест Копелиовича Сергея Владимировича.
Теоретический материал. Мощные структуры данных.
Задачи и разборы.
Задача А. Добавление и удаление точек.
Задача В. Сбалансированное дерево.
Задача С. Count Offline.
Задача D. Count Online.
Задача Е. Динамический Лес.
Задача F. Самая дальняя.
Задача G. Persistent Array.
Задача Н. Перестановки strike back.
Задача I. Persistent List.
Задача J. Проекция в Я3.
Задача К. Прямоугольные запросы.
Задача L. Точки в полуплоскости.
Задача М. Жесть.
Задача N. Подстроки со сдвигом.
Задача О. Антитест.
День восьмой. Контест Эльдара Богданова и Ираклия Мерабишвили.
Об авторах.
Задачи и разборы.
Задача А. Игра с числами.
Задача В. К-вложенные отрезки.
Задача С. Камикадзе.
Задача D. Бескорневые пары.
Задача Е. Стратегия.
День девятый. Контест Пака Станислава Олеговича.
Об авторе.
Теоретический материал. Комбинаторная геометрия.
Задачи и разборы.
Задача A. Asteroids collision.
Задача В. Most distant points pair.
Задача С. Minimum area bounding box.
Задача D. Burn after reading.
Задача E. Clear after burning.



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

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


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




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