Содержание
- 2. Задача A Наибольший общий делитель
- 3. Автор задачи – Виталий Аксёнов Условие – Виталий Аксёнов Подготовка тестов – Виталий Аксёнов Разбор –
- 4. Постановка задачи Дано n чисел и число d Надо найти какой-нибудь поднабор из чисел, такой что
- 5. Как решать? Взять все числа, которые делятся на d Теперь взять у них у всех наибольший
- 6. Обоснование Пусть есть какой-то другой набор, который удовлетворяет нас Все элементы из этого набора обязаны делиться
- 7. Задача B Защита беженцев
- 8. Автор задачи – Алексей Цыпленков Условие – Антон Банных Подготовка тестов – Антон Банных Разбор –
- 9. Постановка задачи Дан многоугольник P Точка называется защищённой, если любой луч проведённый из него пересекается с
- 10. Как решать? Если из какой-то точки луч уходит на бесконечность, продлим его в другую сторону до
- 11. Как решать? Утверждение: если сделать такую операцию для каждой точки, для которой существует луч выходящий на
- 12. Как решать? (продолжение) Проведем лучи для всех пар вершин Для всех таких лучей проведём нашу операцию
- 13. Как решать? (продолжение) Утверждается, что освещённый отрезок на стороне ограничен самой левой освещённой точкой на стороне
- 14. Как решать? (продолжение) Осталось восстановить ответ Утверждение: вершины нашего нового многоугольника – концы невырожденных “освещённых” частей
- 15. Задача C Телефонный номер
- 16. Автор задачи – Михаил Дворкин Условие – Евгений Курпилянский Подготовка тестов – Евгений Курпилянский Разбор –
- 17. Постановка задачи Дан телефонный номер – последовательность чисел, разделенных дефисами Необходимо найти все телефонные номера, которые
- 18. Как решать? Найдем последовательность слов, которые используются при произношении данного номера Заметим, что слова «тысяча» и
- 19. Как решать? (продолжение) Нужно перебрать всевозможные расстановки дефисов между словами и вывести все, которые являются корректными
- 20. Обоснование Количество слов в тестах меньше 100 (так как цифр не больше 50) Количество телефонных номеров
- 21. Задача D Гостиница
- 22. Автор задачи – Антон Банных Условие – Антон Ахи Подготовка тестов – Антон Ахи Разбор –
- 23. Постановка задачи Дано число n Надо его разложить на сумму двоек и троек с минимальным числом
- 24. Как решать? Понятно, что нам не имеет смысла иметь в сумме больше двух двоек, так как
- 25. Задача E Парад
- 26. Автор задачи – Сергей Поромов Условие – Сергей Мельников Подготовка тестов – Сергей Мельников Разбор –
- 27. Постановка задачи Есть последовательность из n чисел Надо разбить их на убывающую и возрастающую подпоследовательности
- 28. Как решать? Будем считать динамику less[i] и greater[i] Разбиение чисел хорошее – разбиение чисел на возрастающую
- 29. Как решать? (продолжение) В какой последовательности находится i-ый элемент: В убывающей, less[i] равен минимальному из последних
- 30. Как решать? (продолжение) В возрастающей, greater[i] равен максимуму из последних элементов всех убывающих последовательностей во всех
- 31. Пересчёт Less[i] if a[i+1] if a[i+1] Greater[i] if a[i+1]>less[i] then greater[i+1]=a[i] if a[i+1]>a[i] then greater[i+1]= min(greater[i+1],
- 32. Как решать? (продолжение) Если мы не смогли посчитать less[n] или greater[n], то ответ – Impossible А
- 33. Задача F Магазин
- 34. Автор задачи – Николай Ведерников Условие – Николай Ведерников Подготовка тестов – Николай Ведерников Разбор –
- 35. Постановка задачи Дано n стоимостей товаров и известно, что k-ый бесплатно Найти минимальное число денег, которое
- 36. Как решать? Отсортируем все цены в порядке убывания Разобьём их на группы по k, начиная с
- 37. Задача G Занос
- 38. Автор задачи – Николай Ведерников Условие – Виталий Аксёнов Подготовка тестов – Виталий Аксёнов Разбор –
- 39. Постановка задачи Дано 5 чисел Максимальная скорость автомобиля - v Длина первого отрезка трассы - x
- 40. Как решать? Заметим, что ситуация с разгоном и ситуация с торможением совершенно одинаковы, то есть при
- 41. Как решать? (продолжение) Понятно, что нам надо сразу разгоняться с ускорением a до скорости v, а
- 42. Задача H Чай
- 43. Автор задачи – Антон Ахи Условие – Антон Ахи Подготовка тестов – Антон Ахи Разбор –
- 44. Постановка задачи Дан чайник объёма V и мощностью N, температура воды в чайнике опускается не ниже
- 45. Как решать? Отсортируем членов жюри по временам прихода И просто нужно запросы жюри обрабатывать в таком
- 46. Подводные камни Нужно не забывать, что минимальная температура воды в чайнике – 20 градусов Изначально чайник
- 47. Задача I Командная олимпиада
- 48. Автор задачи – Юрий Петров Условие – Никита Иоффе Подготовка тестов – Никита Иоффе Разбор –
- 49. Постановка задачи Дана перестановка чисел 1, 1, 2, 2, …, n, n Требуется найти такую перестановку,
- 50. Как решать? Заметим, что нам подходят только перестановки, что расстояние между двумя одинаковыми ровно n, то
- 51. Как решать? (продолжение) Построим полный двудольный граф и на ребре из i в j напишем расстояние
- 52. Задача J Поезда
- 53. Автор задачи – Виталий Аксёнов Условие – Никита Иоффе Подготовка тестов – Никита Иоффе Разбор –
- 54. Постановка задачи Найти k-ую в лексикографическом порядке последовательность, которую можно отсортировать стеком
- 55. Как решать? Заметим, что количество таких перестановок из n элементов равно числу Каталана, так как каждой
- 56. Как решать? (продолжение) Если мы на первое место поставим число i, то последовательность выглядит следующим образом:
- 57. Как решать? (продолжение) Теперь просто решаем стандартную задачу о восстановлении k-ого комбинаторного объекта, то есть ставим
- 58. Задача K Королевская династия
- 59. Автор задачи – Глеб Евстропов Условие – Михаил Пядёркин Подготовка тестов – Михаил Пядёркин Разбор –
- 60. Постановка задачи Дано подвешенное дерево из n вершин Дано m запросов, состоящих из 2 чисел –
- 61. Как решать? Обойдём dfs-ом вершины, и отметим для каждой времена входа in[v] и выхода out[v], а
- 62. Как решать? (продолжение) Обрабатываем запрос: Пусть h[v] – высота вершины v Рассмотрим набор вершин, находящихся на
- 64. Скачать презентацию