Слайд 2
Задача A
Наибольший общий делитель
Слайд 3
Автор задачи – Виталий Аксёнов
Условие – Виталий Аксёнов
Подготовка
тестов – Виталий Аксёнов
Разбор – Виталий Аксёнов
Слайд 4
Постановка задачи
Дано n чисел и число d
Надо найти
какой-нибудь поднабор из чисел, такой что их наибольший общий
делитель равен d
Слайд 5
Как решать?
Взять все числа, которые делятся на d
Теперь
взять у них у всех наибольший общий делитель
Если он
равен d, то выводим это множество, если нет, то вывести -1
Слайд 6
Обоснование
Пусть есть какой-то другой набор, который удовлетворяет нас
Все
элементы из этого набора обязаны делиться на d, а,
значит, этот набор является подмножеством нашего
Следовательно НОД этого набора может быть только больше, чем НОД нашего, а, значит, если наш набор не удовлетворяет, то и другой тоже
Слайд 8
Автор задачи – Алексей Цыпленков
Условие – Антон Банных
Подготовка
тестов – Антон Банных
Разбор – Виталий Аксёнов
Слайд 9
Постановка задачи
Дан многоугольник P
Точка называется защищённой, если любой
луч проведённый из него пересекается с многоугольником P
Надо найти
многоугольник, состоящий из защищённых точек
Слайд 10
Как решать?
Если из какой-то точки луч уходит на
бесконечность, продлим его в другую сторону до пересечения со
стороной (будем считать такую точку на стороне освещённой)
Назовём такую операцию “освещением”
Слайд 11
Как решать?
Утверждение: если сделать такую операцию для каждой
точки, для которой существует луч выходящий на бесконечность, то
на каждой стороне может быть максимум 1 освещённый отрезок
Слайд 12
Как решать?
(продолжение)
Проведем лучи для всех пар вершин
Для всех
таких лучей проведём нашу операцию “освещение”
На каждой стороне получили
набор освещённых точек
Слайд 13
Как решать?
(продолжение)
Утверждается, что освещённый отрезок на стороне ограничен
самой левой освещённой точкой на стороне и самой правой
освещённой точкой стороне
Слайд 14
Как решать?
(продолжение)
Осталось восстановить ответ
Утверждение: вершины нашего нового многоугольника
– концы невырожденных “освещённых” частей
Слайд 16
Автор задачи – Михаил Дворкин
Условие – Евгений Курпилянский
Подготовка
тестов – Евгений Курпилянский
Разбор – Павел Кунявский
Слайд 17
Постановка задачи
Дан телефонный номер – последовательность чисел, разделенных
дефисами
Необходимо найти все телефонные номера, которые произносятся также как
и данный
Слайд 18
Как решать?
Найдем последовательность слов, которые используются при произношении
данного номера
Заметим, что слова «тысяча» и «миллион» (в разных
формах) всегда употребляются вместе с предыдущим словом, поэтому форма этих слов не важна
Следовательно, каждое слово можно хранить как его числовое значение
Слайд 19
Как решать?
(продолжение)
Нужно перебрать всевозможные расстановки дефисов между словами
и вывести все, которые являются корректными телефонными номерами
Для определения
корректности записи нужно понимать можно ли «склеить» несколько слов в одно число
Слайд 20
Обоснование
Количество слов в тестах меньше 100 (так как
цифр не больше 50)
Количество телефонных номеров в ответе не
больше 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)
Слайд 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]
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
А иначе, нужно просто восстановить
ответ по этой динамике
Слайд 34
Автор задачи – Николай Ведерников
Условие – Николай Ведерников
Подготовка
тестов – Николай Ведерников
Разбор – Николай Ведерников
Слайд 35
Постановка задачи
Дано n стоимостей товаров и известно, что
k-ый бесплатно
Найти минимальное число денег, которое нужно потратить, чтобы
купить все товары
Слайд 36
Как решать?
Отсортируем все цены в порядке убывания
Разобьём их
на группы по k, начиная с первого, и из
каждой группы, может быть кроме последней, можно не платить за минимальный элемент (то есть не платить за элемент, номер которого делится на k)
Корректность такого алгоритма понять несложно
Слайд 38
Автор задачи – Николай Ведерников
Условие – Виталий Аксёнов
Подготовка
тестов – Виталий Аксёнов
Разбор – Николай Ведерников
Слайд 39
Постановка задачи
Дано 5 чисел
Максимальная скорость автомобиля - v
Длина
первого отрезка трассы - x
Длина второго отрезка трассы -
y
Максимальное ускорение при разгоне - a
Максимальное ускорение при торможении - b
Найти минимальное время за которое можно преодолеть трассу при условии, что скорость между двумя отрезками равна 0
Слайд 40
Как решать?
Заметим, что ситуация с разгоном и ситуация
с торможением совершенно одинаковы, то есть при торможении мы
считаем, что едем в другую сторону и ускоряемся
Задача свелась к:
Максимальная скорость машины – v
Максимальное ускорение машины – a
Длина отрезка - x
Слайд 41
Как решать?
(продолжение)
Понятно, что нам надо сразу разгоняться с
ускорением a до скорости v, а далее ехать с
постоянной скоростью
2 случая:
Успеваем разогнаться: , тогда ответ –
Не успеваем разогнаться: , тогда ответ –
Слайд 43
Автор задачи – Антон Ахи
Условие – Антон Ахи
Подготовка
тестов – Антон Ахи
Разбор – Антон Ахи
Слайд 44
Постановка задачи
Дан чайник объёма V и мощностью N,
температура воды в чайнике опускается не ниже 20 градусов
и поднимается не выше 100, вода в чайнике остывает со скоростью k градусов в секунду
Дано 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-ое число Каталана
Слайд 57
Как решать?
(продолжение)
Теперь просто решаем стандартную задачу о восстановлении
k-ого комбинаторного объекта, то есть ставим поочерёдно на первое
место числа от 1 до n и проверяем, а потом запускаемся рекурсивно от частей
[1..i-1] и [1..n-i+1]
Слайд 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]
Бинарный поиск