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