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

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

Фрагмент из книги:
Теория вероятностей рассматривает некоторый случайный процесс (или совокупность случайных процессов), называемый опытом. Возможные результаты этого опыта называются исходами. Множество исходов (обычно его обозначают буквой Q) — множество, на котором определена мера, такая, что мера всего множества равна 1. Если говорить простым языком, то мера — это функция, которая сопоставляет некоторый неотрицательный вес каждому элементу множества, а за меру подмножества принимается сумма мер его элементов. Мера каждого исхода называется его вероятностью и указывает, насколько ожидаем тот или иной исход.




Задача В. Случайное совпадение (Юниорская лига).
Вход:    stdin
Выход:    stdout
Ограничение по времени:    1 с
Ограничение по памяти:    256 Мб.

Васе скучно, и он от нечего делать взял N кубиков, пронумерованных числами от 1 до N, перемешал их и расставил в случайном порядке. После этого он несколько раз перемешал кубики и расставил их в том порядке, в котором они оказались. После каждого перемешивания он смотрел, не получилась ли та же самая перестановка, что и перестановка, получившаяся после первого перемешивания. Но кубиков было много, искомая перестановка всё никак не получалась, и Васе опять стало скучно. Но Вася подумал и решил получить искомую перестановку другим способом. Он расставил кубики по порядку от 1 до N и решил выбрать часть кубиков, перемешать их и вернуть на те же места, но, возможно, в другом порядке. Он решил повторять эти действия до тех пор, пока не получится перестановка, которую он запомнил в самом начале, но перед этим ему хочется узнать, через какое время, в среднем, он сможет этого добиться? Вася хочет получить эту перестановку как можно быстрее и выбирает кубики, которые он будет перемешивать, соответственно.

ОГЛАВЛЕНИЕ.
День первый. Контест Евгения Кануна.
Об авторе.
Теоретический материал. Теория вероятностей.
Задачи и разборы.
Задача А. Трудный путь (Юниорская лига).
Задача В. Случайное совпадение (Юниорская лига).
Задача С. Полный набор (Юниорская лига).
Задача D. Питание.
Задача Е. Секретный код.
Задача F. Dura Lex.
Задача G. Путь к знаниям.
Задача Н. Гранит науки.
Задача I. Вероятный диагноз.
Задача J. Зоологический эксперимент.
Задача К. Игра (Высшая лига).
Задача L. Опасная игра (Высшая лига).
Задача М. Хеш-таблица (Высшая лига).
День второй. Контест Сергея Нагина.
Об авторе.
Теоретический материал. Поиск состояний в задачах на динамическое программирование.
Задачи и разборы.
Задача А. Сережа и уменьшения (Юниорская лига).
Задача В. Сережа и шаблон (Юниорская лига).
Задача С. Сережа и массив (Юниорская лига).
Задача D. Сережа и вода.
Задача Е. Сережа и игра.
Задача F. Сережа и столбики.
Задача G. Сережа и деление.
Задача Н. Сережа и последовательность.
Задача I. Сережа и экзамен.
Задача J. Сережа и уменьшения (Высшая лига).
Задача К. Сережа и шаблон (Высшая лига).
Задача L. Сережа и массив (Высшая лига).
День третий. Контест Алексея Шмелева.
Об авторе.
Теоретический материал. Лемма Бёрнсайда и Теорема Пойа.
Задачи и разборы.
Задача A. Who Calls the Crystal Maiden? (Юниорская лига).
Задача В. World of Dota: Cross (Юниорская лига).
Задача С. Warlock (Юниорская лига).
Задача D. Wild Card: Subway.
Задача Е. Wild Card: Bus.
Задача F. Windrunner at Your Service.
Задача G. What is the Answer?.
Задача H. We Admit No Defeat.
Задача I. Wex-Wex-Wex.
Задача J. Warlock-2 (Высшая лига).
Задача К. World of Dota: Cross 2 (Высшая лига).
Задача L. Wild Card: Plane (Высшая лига).
День четвёртый. Контест Ярослава Твердохлеба и Романа Едемского.
Об авторах.
Теоретический материал. Оптимизация динамического программирования за счет использования свойств линейных функций и алгоритма Грэхема.
Задачи и разборы.
Задача А. Счастливые пары (Юниорская лига).
Задача В. Лазер (Юниорская лига).
Задача С. Новогодние подарки (Юниорская лига).
Задача D. Депутаты на дереве (Юниорская лига).
Задача Е. LinearMapReduce.
Задача F. Круги и деревья.
Задача G. Петя и игра.
Задача И. Петя и массивы.
Задача I. Петя и массив 2.
Задача J. Петя и прямоугольники.
Задача К. Игровелоперы.
Задача L. Путешествие (Высшая лига).
Задача М. Петя и среднее (Высшая лига).
Задача N. Депутаты на дереве (Высшая лига).
День пятый. Контест Романа Андреева.
Об авторе.
Теоретический материал. Лекция про пересечение полуплоскостей.
Задачи и разборы.
Задача А. Гарри Поттер и три заклинания.
Задача В. Антисортировка.
Задача С. Астрид и квадраты.
Задача D. Берт и землеройки.
Задача Е. Марсианская архитектура.
Задача F. Камилла и язык программирования WR.
Задача G. Ворчливые коровы.
Задача Н. Давид и осёл.
Задача I. Эмма и соты.
Задача J. Побег.
Задача К. Петя и Java.
Задача L. Цепная дробь.
Задача М. Шестерёнки.
Задача N. Задача на НОК.
Задача О. Сон Студента.
Задача Р. Постройка пирамиды.
Задача Q. Треугольная комната.
Задача R. SMS.
Задача S. Неквадраты.
Задача Т. Перестановка цифр.
Задача U. Пристрастный учитель.
Задача V. Поезда.
Задача W. Ловушки.
Задача X. Магия вуду.
Задача на самое короткое решение. Суперминимум.
День шестой. Контест Натальи Бондаренко.
Об авторе.
Теоретический материал. Об одной комбинаторной игре.
Задачи и разборы.
Задача А. Игра с числом.
Задача В. Отношение чисел Фибоначчи (простая версия).
Задача С. Отношение чисел Фибоначчи (сложная версия).
Задача D. Обобщенная последовательность Фибоначчи.
Задача Е. Сложение в фибоначчиевой системе счисления.
Задача F. Игра с монетами.
Задача G. Цзяньшицзы с тремя кучками.
Задача Н. Спички детям не игрушки.
Задача I. Ферзя в угол!.
Задача J. (р, q)-коня в угол!.
Задача К. Игра.
Задача L. Игра со строкой.
День седьмой. Контест Сергея Копелиовича.
Об авторе.
Теоретический материал. Перебор и NP-полные задачи.
Задачи и разборы.
Задача А. Трисочетание.
Задача В. Множество множеств.
Задача С. Длинная дорога.
Задача Е. Корни.
Задача F. Умножение многочленов.
Задача G. Деление многочленов.
Задача Н. Ребра добавляются, граф растет.
Задача I. Сумма всего подряд.
Задача J. Все клики.
Задача К. Макс клика.
Задача L. Учимся красить.
Задача М. Проще всего красить в три цвета.
Задача N. SAT USAT.
Задача O. Почти двудольный зверь.
День восьмой. Контест Akai.
Об авторе.
Теоретический материал. Поиск минимального элемента в стеке, в очереди и в скользящем окне в массиве.
Задачи и разборы.
Задача A. Anti-Lines (высшая лига).
Задача В. Big Fellow (высшая лига).
Задача С. Concave Polygon (высшая лига).
Задача D. Dead Points (высшая лига).
Задача Е. Equilateral Polygon.
Задача F. Flawless Numbers.
Задача G. Grep.
Задача H. Hash It!.
Задача I. Interactive Problem 2.
Задача J. Jolly Dolls.
Задача К. Block Shuffling (юниорская лига).
Задача L. Digit Permutation (юниорская лига).
Задача M. Mortal Points (юниорская лига).
Задача N. Non-convex Polygon (юниорская лига).
День девятый. Контест Виталия Неспирного.
Об авторе.
Теоретический материал. Построение пересечения полуплоскостей.
Задачи и разборы.
Задача А. Максимальная разность (высшая лига).
Задача В. Максимальная разность (юниорская лига).
Задача С. Построение многоугольника (высшая лига).
Задача D. Построение треугольника (юниорская лига).
Задача Е. Красивые узоры (высшая лига).
Задача F. Красивые узоры (юниорская лига).
Задача G. Строка без повторений (высшая лига).
Задача Н. Строка без повторений (юниорская лига).
Задача I. Сбор бобов (высшая лига).
Задача J. Сбор бобов (юниорская лига).
Задача К. Обратный сбор бобов (высшая лига).
Задача L. Обратный сбор бобов (юниорская лига).
Задача М. Уравнение (высшая лига).
Задача N. Уравнение (юниорская лига).
Задача О. Соревнование (высшая лига).
Задача Р Соревнование (юниорская лига).
Задача Q. Вписанная окружность (высшая лига).
Задача R. Вписанная окружность (юниорская лига).
Задача S. Разделяющая прямая (высшая лига).
Задача Т. Разделяющая прямая (юниорская лига).
Задача U. Стрингангуляция (высшая лига).
Задача V. Стрингангуляция (юниорская лига).
Задача W. Построение куба (высшая лига).
Задача X. Построение квадрата (юниорская лига).



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

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


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




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