Содержание
- 2. Задача A. Поедание сыра
- 3. Авторы задачи Автор задачи — Сергей Мельников Условие — Андрей Станкевич Подготовка тестов — Антон Ахи
- 4. Общая идея Используем двоичный поиск по ответу Дано t, можно ли организовать поедание сыра, чтобы мыши
- 5. Интересные интервалы Пусть Ti – все моменты времени ri и Di T1 Время разбивается на интервалы
- 6. Скорости всех мышей равны 1 Рассмотрим сеть В ней надо найти максимальный поток Ребро из cыра
- 7. Скорости всех мышей равны 1 Три сыра p1=1 r1=2 d1=2 p2=3 r2=1 d2=4 p3=2 r3=2 d3=4
- 8. Разные скорости мышей Упорядочим мышей по неубыванию скоростей: s1 ≥ s2 ≥ … ≥ sm Представим
- 9. Модификация сети Раньше было Заменим, на такой фрагмент Kj,k – одни и те же разных i
- 10. Общее решение Двоичный поиск Поток в специальной сети
- 11. Спасибо за внимание! Вопросы по задаче A?
- 12. Задача B. Соревнования по программированию
- 13. Авторы задачи Автор задачи — Владимир Ульянцев Условие — Федор Царев Подготовка тестов — Антон Ахи
- 14. О чем задача? Дан список файлов и определения для каталогов с тестами, задач и описаний соревнований
- 15. Как решать? Востановить полностью дерево каталогов и файлов Использовать символ «\» как разделитель имен в путях
- 16. Как посчитать количество описаний соревнований? В получившемся дереве файлов/каталогов проверить про каждый каталог, является ли он
- 17. Сколько работает? Во входном файле задано не более 100000 файлов/каталогов Каждый каталог просматривается один раз
- 18. Спасибо за внимание! Вопросы по задаче B?
- 19. Задача C. Распил
- 20. Авторы задачи Авторы задачи — Елена Андреева, Владимир Гуровиц Условие — Андрей Станкевич Подготовка тестов —
- 21. О чем задача? Придумать n-угольник, который можно распилить на k-угольник и m-угольник разрезом, проходящим через две
- 22. Какие n, m, k допустимы? Если , решения нет. Иначе при достаточно больших n, m, k
- 23. m + k = n
- 24. m + k = n + 1
- 25. m + k = n + 2
- 26. m + k = n + 3
- 27. m + k = n + 4
- 28. m + k = n + 4, k
- 29. Спасибо за внимание! Вопросы по задаче C?
- 30. Задача D. Электричество
- 31. Авторы задачи Автор задачи — Владимир Гуровиц Условие — Федор Царев Подготовка тестов — Сергей Поромов
- 32. О чем задача? В наличии: k сетевых фильтров n элетроприборов 1 розетка Требуется подсоединить все элетроприборы
- 33. Основные идеи Не имеет смысла поключать фильтр к фильтру с меньшей максимальной нагрузкой. Наиболее мощные приборы
- 34. Решение Отсортировать электроприборы и фильтры в порядке невозрастания мощностей. Строить ответ жадно, начиная с фильтра, подключенного
- 35. Спасибо за внимание! Вопросы по задаче D?
- 36. Задача E. Адронные коллайдеры
- 37. Авторы задачи Автор задачи — Михаил Кевер Условие — Федор Царев Подготовка тестов — Сергей Поромов
- 38. Две окружности Две окружности: найдем окружность с центром на прямой, соединяющей центры исходных окружностей
- 39. Две окружности Для любой точки С на перпендикуляре восстановленном в точке D – существует окружность являющаяся
- 40. Три окружности Три окружности: Построим прямую на которой может быть центр окружности делящей пополам O1 и
- 41. Три окружности
- 42. Спасибо за внимание! Вопросы по задаче E?
- 43. Задача F. Космические захватчики
- 44. Авторы задачи Автор задачи — Георгий Корнеев Условие — Павел Маврин Подготовка тестов — Антон Банных
- 45. О чем задача? В столбцах находятся ai захватчиков Пушка за одно действие либо перемещается в соседний
- 46. Частный случай Если пушка стоит в крайнем столбце, то нужно уничтожить всех захватчиков в этом столбце
- 47. Решение Дойти до ближайшего из краев, далее действовать по предыдущему плану Ответ — Σai+(n-1)+min(p-1,n-p)
- 48. Спасибо за внимание! Вопросы по задаче F?
- 49. Задача G. Пробежки по Манхэттену
- 50. Авторы задачи Автор задачи — Михаил Дворкин Условие — Павел Маврин Подготовка тестов — Олег Давыдов
- 51. О чем задача? Объект передвигается по Манхэттену, пробегая за t минут не более чем t кварталов.
- 52. Утверждение В каждый момент времени множество точек, в которых может находиться объект, составляют прямоугольник, стороны которого
- 53. В начальный момент времени Это точка (0, 0) — вырожденный прямоугольник.
- 54. За t минут… Объект может пройти не более t кварталов. Прямоугольник «расширяется во все стороны на
- 55. Данные от навигатора… Сообщают, в каком квадрате может находиться объект. Пересечем прямоугольник и квадрат (с параллельными
- 56. Спасибо за внимание! Вопросы по задаче G?
- 57. Задача H. Следующее разбиение на слагаемые
- 58. Авторы задачи Автор задачи — Андрей Станкевич Условие — Андрей Станкевич Подготовка тестов — Сергей Мельников
- 59. Генерация следующего комбинаторного объекта Дано разбиение 5=1+1+3 Идём с конца, пока нельзя увеличить слагаемое Увеличим слагаемое
- 60. Когда можно увеличить слагаемое? Первое слагаемое с конца нельзя увеличить Второе слагаемое с конца можно увеличить
- 61. На сколько можно увеличить слагаемое? Слагаемое можно увеличить на 1, если оно было меньше последнего хотя
- 62. Минимальный «хвост»? Надо вывести хвост с суммой S, при этом последнее слагаемое которое было выведено перед
- 63. Спасибо за внимание! Вопросы по задаче H?
- 64. Задача I. Самодвойственный документ
- 65. Авторы задачи Автор задачи — Сергей Мельников Условие — Андрей Станкевич Подготовка тестов — Сергей Мельников
- 66. Условие задачи В задаче надо построить граф из n вершин Первый отдел: пары чисел – это
- 67. Когда ответ существует? В полном графе из n вершин n(n - 1)/2 ребер Если n =
- 68. 4k вершин 4 вершины 4k вершин – заменить вершины 2 и 3 на полные графы, 1
- 69. 12 вершин
- 70. 4k + 1 вершина 4k+1 вершина – заменить вершины 2 и 3 на полные графы, 1
- 71. 13 вершин
- 72. Спасибо за внимание! Вопросы по задаче I?
- 73. Задача J. Цирковое шоу
- 74. Авторы задачи Автор задачи — Юрий Петров Условие — Павел Маврин Подготовка тестов — Юрий Петров
- 75. Формулировка Дан набор отрезков Выбрать два поднабора, объединения которых не пересекаются Максимизировать минимум размеров
- 76. Идея решения Динамическое программирование
- 77. Решение: вычисляемая функция Функция f(a, n, t): a — самый правый из отрезков, взятых в один
- 78. Решение: переходы Перебрать отрезок b, который будет завершать следующую группу Перебрать набор, в который взять эту
- 79. Оценка времени работы Всего есть n×n×2 состояний Из каждого O(n) переходов Переходы перебирать в порядке возрастания
- 80. Спасибо за внимание! Вопросы по задаче J?
- 81. Задача K. Красивая таблица результатов
- 82. Авторы задачи Автор задачи — Владимир Ульнцев Условие — Андрей Станкевич Подготовка тестов — Владимир Ульянцев
- 83. О чем задача? Таблица результатов считается красивой, если количество задач, решенных каждой из команд, либо 0,
- 84. Как решать? Для каждой команды увеличивать количество сданных ею задач, пока это не изменяет красоту таблицы
- 86. Скачать презентацию