Содержание
- 2. Задача A. Ситха джедай против
- 3. Авторы Идея задачи – Антон Банных Условие задачи – Антон Ахи Подготовка тестов – Антон Банных
- 4. Постановка задачи Два адепта Силы n умений Познания по каждому умению растут по линейному закону Найти
- 5. Упрощение постановки задачи Рассмотрим каждое умение в отдельности Условие того, что в день x познания джедая
- 6. Решение для одного умения нет решения
- 7. Решение Поддерживаем интервал, на котором джедай не хуже ситха Добавляем умения по одному Каждый раз нужно
- 8. Тонкости И числитель и знаменатель дроби может быть как положительным, так и отрицательным Деление с округлением
- 9. Простое решение Все ограничения на x не превосходят 1000, поэтому если решение есть, то оно находится
- 10. Задача B. Министерство правды
- 11. Авторы Идея задачи – Андрей Комаров, Павел Кротков Условие задачи – Антон Банных Подготовка тестов –
- 12. Формальная постановка задачи Дан массив целых чисел Необходимо разбить его на три не пустые части, с
- 13. Идея Подсчитаем частичные суммы на префиксе. Теперь можно быстро находить сумму на отрезке с a до
- 14. Решение за Переберем длины первой и второй частей Вычислим S1, S2, S3 при помощи частичных сумм
- 15. Решение за NlogN Переберем длину первого отрезка Разобьём оставшийся отрезок на две примерно равные части. Рассмотрим
- 16. Решение за NlogN (2) Докажем что разбивать второй отрезок не пополам не выгодно Если S1 минимальное,
- 17. Решение за NlogN (3) Точку разбиения будем искать двоичным поиском Пусть длина первого отрезка A Найдем
- 18. Решение за NlogN Точку разбиения будем искать двоичным поиском l := 1; r := n -
- 19. Решение за N Заметим что при увеличении A, величина A+B в оптимальном ответе не может уменьшится
- 20. Задача C. Йою Ньерк
- 21. Авторы Идея задачи – Антон Ахи Условие задачи – Антон Ахи Подготовка тестов – Сергей Поромов
- 22. Постановка задачи Есть прямоугольное поле из улиц и авеню Каждая улица и авеню односторонняя Необходимо найти
- 23. Частичные случаи Все улицы направлены в одну сторону и все авеню тоже в одну сторону –
- 24. Идея решения Количество отрезков пути не превышает 5
- 25. Идея решения Для нахождения кратчайшего пути использовать обход в ширину Для выбора кратчайших путей с минимальным
- 26. Как максимизировать минимальный отрезок? Двоичный поиск по длине минимального отрезка В графе кратчайших путей с минимальным
- 27. Восстановление ответа Для каждого перекрестка и направления, с которого приехали, запоминать длину последнего отрезка пути Восстанавливать
- 28. Время работы Обходы в ширину - O(nm), двоичный поиск + обход в глубину суммарно O(nm·log(max(n, m)))
- 29. Задача D. Обратный кузнечик
- 30. Авторы Идея задачи – Владимир Ульянцев Условие задачи – Владимир Ульянцев Подготовка тестов – Антон Ахи
- 31. Постановка задачи Кузнечик прыгает на одну или две травинки вперед Кузнечик не может находится на сломанной
- 32. Решение «прямой» задачи Если все n травинок целы, то число путей ─ n-ое число Фибоначчи Когда
- 33. Идея «обратной» задачи Число путей всегда является произведением чисел Фибоначчи Требуется представить k в виде произведения
- 34. Решение «обратной» задачи Чисел Фибоначчи, которые делят k, очень мало Чисел, которые представимы произведениями этих чисел
- 35. Решение «обратной» задачи Для каждого k будем вычислять наименьшее число травинок необходимых, чтобы его получить Вычисления
- 36. Восстановление ответа Зная минимальное необходимо число травинок, можно его увеличивать, добавляя к последовательности либо 0 1,
- 37. Тонкости решения Если m > n или m и n имеют разную четность и m +
- 38. Альтернативные подходы Не перебирать делители k, а выстраивать произведения чисел Фибоначчи, аналогично задаче о рюкзаке Пытаться
- 40. Скачать презентацию