ВКОШП-2011. Разбор задач

Сентябрь 14, 2022

Главная
Математика
ВКОШП-2011. Разбор задач

Содержание

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. Скачать презентацию

Слайд 2

Задача A
Наибольший общий делитель

Слайд 3

Автор задачи – Виталий Аксёнов
Условие – Виталий Аксёнов
Подготовка тестов – Виталий

Аксёнов
Разбор – Виталий Аксёнов

Слайд 4

Постановка задачи
Дано n чисел и число d
Надо найти какой-нибудь поднабор из

чисел, такой что их наибольший общий делитель равен d

Слайд 5

Как решать?
Взять все числа, которые делятся на d
Теперь взять у них

у всех наибольший общий делитель
Если он равен d, то выводим это множество, если нет, то вывести -1

Слайд 6

Обоснование
Пусть есть какой-то другой набор, который удовлетворяет нас
Все элементы из этого

набора обязаны делиться на d, а, значит, этот набор является подмножеством нашего
Следовательно НОД этого набора может быть только больше, чем НОД нашего, а, значит, если наш набор не удовлетворяет, то и другой тоже

Слайд 7

Задача B
Защита беженцев

Слайд 8

Автор задачи – Алексей Цыпленков
Условие – Антон Банных
Подготовка тестов – Антон

Банных
Разбор – Виталий Аксёнов

Слайд 9

Постановка задачи
Дан многоугольник P
Точка называется защищённой, если любой луч проведённый из

него пересекается с многоугольником P
Надо найти многоугольник, состоящий из защищённых точек

Слайд 10

Как решать?
Если из какой-то точки луч уходит на бесконечность, продлим его

в другую сторону до пересечения со стороной (будем считать такую точку на стороне освещённой)
Назовём такую операцию “освещением”

Слайд 11

Как решать?
Утверждение: если сделать такую операцию для каждой точки, для которой

существует луч выходящий на бесконечность, то на каждой стороне может быть максимум 1 освещённый отрезок

Слайд 12

Как решать? (продолжение)
Проведем лучи для всех пар вершин
Для всех таких лучей проведём

нашу операцию “освещение”
На каждой стороне получили набор освещённых точек

Слайд 13

Как решать? (продолжение)
Утверждается, что освещённый отрезок на стороне ограничен самой левой освещённой

точкой на стороне и самой правой освещённой точкой стороне

Слайд 14

Как решать? (продолжение)
Осталось восстановить ответ
Утверждение: вершины нашего нового многоугольника – концы невырожденных

“освещённых” частей

Слайд 15

Задача C
Телефонный номер

Слайд 16

Автор задачи – Михаил Дворкин
Условие – Евгений Курпилянский
Подготовка тестов – Евгений

Курпилянский
Разбор – Павел Кунявский

Слайд 17

Постановка задачи
Дан телефонный номер – последовательность чисел, разделенных дефисами
Необходимо найти все

телефонные номера, которые произносятся также как и данный

Слайд 18

Как решать?
Найдем последовательность слов, которые используются при произношении данного номера
Заметим, что

слова «тысяча» и «миллион» (в разных формах) всегда употребляются вместе с предыдущим словом, поэтому форма этих слов не важна
Следовательно, каждое слово можно хранить как его числовое значение

Слайд 19

Как решать? (продолжение)
Нужно перебрать всевозможные расстановки дефисов между словами и вывести все,

которые являются корректными телефонными номерами
Для определения корректности записи нужно понимать можно ли «склеить» несколько слов в одно число

Слайд 20

Обоснование
Количество слов в тестах меньше 100 (так как цифр не больше

50)
Количество телефонных номеров в ответе не больше 100000
Следовательно, перебор будет работать быстро с отсечением – не перебирать дальше, если следующую группу слов нельзя «склеить» в одно число

Слайд 21

Задача D
Гостиница

Слайд 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)

Слайд 25

Задача E
Парад

Слайд 26

Автор задачи – Сергей Поромов
Условие – Сергей Мельников
Подготовка тестов – Сергей

Мельников
Разбор – Сергей Мельников

Слайд 27

Постановка задачи
Есть последовательность из n чисел
Надо разбить их на убывающую и

возрастающую подпоследовательности

Слайд 28

Как решать?
Будем считать динамику less[i] и greater[i]
Разбиение чисел хорошее – разбиение

чисел на возрастающую и убывающую подпоследовательности

Слайд 29

Как решать? (продолжение)
В какой последовательности находится i-ый элемент:
В убывающей, less[i] равен минимальному

из последних элементов всех возрастающих последовательностей во всех хороших разбиениях чисел с индексами от 1 до i-1

Слайд 30

Как решать? (продолжение)
В возрастающей, greater[i] равен максимуму из последних элементов всех убывающих

последовательностей во всех хороших разбиениях чисел с индексами от 1 до i-1

Слайд 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], greater[i])

Слайд 32

Как решать? (продолжение)
Если мы не смогли посчитать less[n] или greater[n], то ответ

– Impossible
А иначе, нужно просто восстановить ответ по этой динамике

Слайд 33

Задача F
Магазин

Слайд 34

Автор задачи – Николай Ведерников
Условие – Николай Ведерников
Подготовка тестов – Николай

Ведерников
Разбор – Николай Ведерников

Слайд 35

Постановка задачи
Дано n стоимостей товаров и известно, что k-ый бесплатно
Найти минимальное

число денег, которое нужно потратить, чтобы купить все товары

Слайд 36

Как решать?
Отсортируем все цены в порядке убывания
Разобьём их на группы по

k, начиная с первого, и из каждой группы, может быть кроме последней, можно не платить за минимальный элемент (то есть не платить за элемент, номер которого делится на k)
Корректность такого алгоритма понять несложно

Слайд 37

Задача G
Занос

Слайд 38

Автор задачи – Николай Ведерников
Условие – Виталий Аксёнов
Подготовка тестов – Виталий

Аксёнов
Разбор – Николай Ведерников

Слайд 39

Постановка задачи
Дано 5 чисел
Максимальная скорость автомобиля - v
Длина первого отрезка трассы

- x
Длина второго отрезка трассы - y
Максимальное ускорение при разгоне - a
Максимальное ускорение при торможении - b
Найти минимальное время за которое можно преодолеть трассу при условии, что скорость между двумя отрезками равна 0

Слайд 40

Как решать?
Заметим, что ситуация с разгоном и ситуация с торможением совершенно

одинаковы, то есть при торможении мы считаем, что едем в другую сторону и ускоряемся
Задача свелась к:
Максимальная скорость машины – v
Максимальное ускорение машины – a
Длина отрезка - x

Слайд 41

Как решать? (продолжение)
Понятно, что нам надо сразу разгоняться с ускорением a до

скорости v, а далее ехать с постоянной скоростью
2 случая:
Успеваем разогнаться: , тогда ответ –
Не успеваем разогнаться: , тогда ответ –

Слайд 42

Задача H
Чай

Слайд 43

Автор задачи – Антон Ахи
Условие – Антон Ахи
Подготовка тестов – Антон

Ахи
Разбор – Антон Ахи

Слайд 44

Постановка задачи
Дан чайник объёма V и мощностью N, температура воды в

чайнике опускается не ниже 20 градусов и поднимается не выше 100, вода в чайнике остывает со скоростью k градусов в секунду
Дано m запросов, состоящих из двух чисел – время прихода члена жюри ti и объём его кружки ai , надо на каждый запрос вернуть время в секундах, когда член жюри начнёт пить чай

Слайд 45

Как решать?
Отсортируем членов жюри по временам прихода
И просто нужно запросы жюри

обрабатывать в таком порядке прямо как написано в условии

Слайд 46

Подводные камни
Нужно не забывать, что минимальная температура воды в чайнике –

20 градусов
Изначально чайник был пуст

Слайд 47

Задача I
Командная олимпиада

Слайд 48

Автор задачи – Юрий Петров
Условие – Никита Иоффе
Подготовка тестов – Никита

Иоффе
Разбор – Никита Иоффе

Слайд 49

Постановка задачи
Дана перестановка чисел 1, 1, 2, 2, …, n, n
Требуется

найти такую перестановку, что минимальное расстояние между двумя одинаковыми элементами было максимально и сумма расстояний между старыми и новыми позициями минимальна

Слайд 50

Как решать?
Заметим, что нам подходят только перестановки, что расстояние между двумя

одинаковыми ровно n, то есть теперь положение i в первой половине однозначно задаёт положение i во второй половине

Слайд 51

Как решать? (продолжение)
Построим полный двудольный граф и на ребре из i в

j напишем расстояние между положениями i в изначальной перестановке и когда они будут стоять на позициях j и j+n
Осталось просто на этом графе найти минимальное взвешенное полное парасочетание

Слайд 52

Задача J
Поезда

Слайд 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-ое число Каталана

Слайд 57

Как решать? (продолжение)
Теперь просто решаем стандартную задачу о восстановлении k-ого комбинаторного объекта,

то есть ставим поочерёдно на первое место числа от 1 до n и проверяем, а потом запускаемся рекурсивно от частей [1..i-1] и [1..n-i+1]

Слайд 58

Задача K
Королевская династия

Слайд 59

Автор задачи – Глеб Евстропов
Условие – Михаил Пядёркин
Подготовка тестов – Михаил

Пядёркин
Разбор – Олег Давыдов

Слайд 60

Постановка задачи
Дано подвешенное дерево из n вершин
Дано m запросов, состоящих из

2 чисел – v и k
Для каждого запроса надо вывести количество потомков вершины v на расстоянии k

Слайд 61

Как решать?
Обойдём dfs-ом вершины, и отметим для каждой времена входа in[v]

и выхода out[v], а также для каждой высоты будем хранить набор вершин, которые находятся на этой высоте

Слайд 62

Как решать? (продолжение)
Обрабатываем запрос:
Пусть h[v] – высота вершины v
Рассмотрим набор вершин, находящихся

на высоте h[v]+k
Среди них нужно найти количество таких, у которых времена входа от in[v] до out[v]
Бинарный поиск

ВКОШП-2011. Разбор задач

Содержание

Задача AНаибольший общий делитель

Автор задачи – Виталий АксёновУсловие – Виталий АксёновПодготовка тестов – Виталий

Постановка задачиДано n чисел и число dНадо найти какой-нибудь поднабор из

Как решать?Взять все числа, которые делятся на dТеперь взять у них

ОбоснованиеПусть есть какой-то другой набор, который удовлетворяет насВсе элементы из этого

Задача BЗащита беженцев

Автор задачи – Алексей ЦыпленковУсловие – Антон БанныхПодготовка тестов – Антон

Постановка задачиДан многоугольник PТочка называется защищённой, если любой луч проведённый из

Как решать?Если из какой-то точки луч уходит на бесконечность, продлим его

Как решать?Утверждение: если сделать такую операцию для каждой точки, для которой

Как решать? (продолжение)Проведем лучи для всех пар вершинДля всех таких лучей проведём

Как решать? (продолжение)Утверждается, что освещённый отрезок на стороне ограничен самой левой освещённой

Как решать? (продолжение)Осталось восстановить ответУтверждение: вершины нашего нового многоугольника – концы невырожденных

Задача CТелефонный номер

Автор задачи – Михаил ДворкинУсловие – Евгений КурпилянскийПодготовка тестов – Евгений

Постановка задачиДан телефонный номер – последовательность чисел, разделенных дефисамиНеобходимо найти все

Как решать?Найдем последовательность слов, которые используются при произношении данного номераЗаметим, что

Как решать? (продолжение)Нужно перебрать всевозможные расстановки дефисов между словами и вывести все,

ОбоснованиеКоличество слов в тестах меньше 100 (так как цифр не больше

Задача DГостиница

Автор задачи – Антон БанныхУсловие – Антон АхиПодготовка тестов – Антон

Постановка задачиДано число nНадо его разложить на сумму двоек и троек

Как решать?Понятно, что нам не имеет смысла иметь в сумме больше

Задача EПарад

Автор задачи – Сергей ПоромовУсловие – Сергей МельниковПодготовка тестов – Сергей

Постановка задачиЕсть последовательность из n чиселНадо разбить их на убывающую и

Как решать?Будем считать динамику less[i] и greater[i]Разбиение чисел хорошее – разбиение

Как решать? (продолжение)В какой последовательности находится i-ый элемент:В убывающей, less[i] равен минимальному

Как решать? (продолжение)В возрастающей, greater[i] равен максимуму из последних элементов всех убывающих

Пересчёт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

Как решать? (продолжение)Если мы не смогли посчитать less[n] или greater[n], то ответ

Задача FМагазин

Автор задачи – Николай ВедерниковУсловие – Николай ВедерниковПодготовка тестов – Николай

Постановка задачиДано n стоимостей товаров и известно, что k-ый бесплатноНайти минимальное

Как решать?Отсортируем все цены в порядке убыванияРазобьём их на группы по

Задача GЗанос

Автор задачи – Николай ВедерниковУсловие – Виталий АксёновПодготовка тестов – Виталий

Постановка задачиДано 5 чиселМаксимальная скорость автомобиля - vДлина первого отрезка трассы

Как решать?Заметим, что ситуация с разгоном и ситуация с торможением совершенно

Как решать? (продолжение)Понятно, что нам надо сразу разгоняться с ускорением a до

Задача HЧай

Автор задачи – Антон АхиУсловие – Антон АхиПодготовка тестов – Антон

Постановка задачиДан чайник объёма V и мощностью N, температура воды в

Как решать?Отсортируем членов жюри по временам приходаИ просто нужно запросы жюри

Подводные камниНужно не забывать, что минимальная температура воды в чайнике –

Задача IКомандная олимпиада

Автор задачи – Юрий ПетровУсловие – Никита ИоффеПодготовка тестов – Никита

Постановка задачиДана перестановка чисел 1, 1, 2, 2, …, n, nТребуется

Как решать?Заметим, что нам подходят только перестановки, что расстояние между двумя

Как решать? (продолжение)Построим полный двудольный граф и на ребре из i в

Задача JПоезда

Автор задачи – Виталий АксёновУсловие – Никита ИоффеПодготовка тестов – Никита

Постановка задачиНайти k-ую в лексикографическом порядке последовательность, которую можно отсортировать стеком

Как решать?Заметим, что количество таких перестановок из n элементов равно числу

Как решать? (продолжение)Если мы на первое место поставим число i, то последовательность

Как решать? (продолжение)Теперь просто решаем стандартную задачу о восстановлении k-ого комбинаторного объекта,

Задача KКоролевская династия

Автор задачи – Глеб ЕвстроповУсловие – Михаил ПядёркинПодготовка тестов – Михаил

Постановка задачиДано подвешенное дерево из n вершинДано m запросов, состоящих из

Как решать? Обойдём dfs-ом вершины, и отметим для каждой времена входа in[v]

Как решать? (продолжение)Обрабатываем запрос:Пусть h[v] – высота вершины vРассмотрим набор вершин, находящихся

Похожие презентации