Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
39 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
893.50 kB
Просмотров:
96
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Индивидуальная олимпиада по](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img0.jpg)
Содержание слайда: Индивидуальная олимпиада по информатике и программированию. Очный тур
Разбор задач
27 марта 2011 года
Москва, Новосибирск, Санкт-Петербург,
Саратов, Челябинск
№2 слайд![Задача A. Ситха джедай против](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img1.jpg)
Содержание слайда: Задача A.
Ситха джедай против
№3 слайд![Авторы Идея задачи Антон](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img2.jpg)
Содержание слайда: Авторы
Идея задачи – Антон Банных
Условие задачи – Антон Ахи
Подготовка тестов – Антон Банных
Подготовка разбора – Антон Банных
№4 слайд![Постановка задачи Два адепта](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img3.jpg)
Содержание слайда: Постановка задачи
Два адепта Силы
n умений
Познания по каждому умению растут по линейному закону
Найти день, в который познания по каждому умению у джедая будут не хуже, чем у ситха
№5 слайд![Упрощение постановки задачи](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img4.jpg)
Содержание слайда: Упрощение постановки задачи
Рассмотрим каждое умение в отдельности
Условие того, что в день x познания джедая в этом уменнии будут не хуже, чем у ситха:
Пусть и
Неравенство приобрело вид
№6 слайд![Решение для одного умения нет](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img5.jpg)
Содержание слайда: Решение для одного умения
нет решения
№7 слайд![Решение Поддерживаем](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img6.jpg)
Содержание слайда: Решение
Поддерживаем интервал, на котором джедай не хуже ситха
Добавляем умения по одному
Каждый раз нужно пересечь два интервала
O(n)
№8 слайд![Тонкости И числитель и](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img7.jpg)
Содержание слайда: Тонкости
И числитель и знаменатель дроби может быть как положительным, так и отрицательным
Деление с округлением требует разбора нескольких случаев при реализации в целых числах
Лучше делить в вещественных числах, а затем округлять в нужную сторону
№9 слайд![Простое решение Все](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img8.jpg)
Содержание слайда: Простое решение
Все ограничения на x не превосходят 1000, поэтому если решение есть, то оно находится на отрезке [0, 1000]
Переберем 1001 день и для каждого дня проверим, подходит ли он
O(nC), где C ─ ограничение сверху на начальные умения и ежедневные приросты
№10 слайд![Задача B. Министерство правды](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img9.jpg)
Содержание слайда: Задача B. Министерство правды
№11 слайд![Авторы Идея задачи Андрей](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img10.jpg)
Содержание слайда: Авторы
Идея задачи – Андрей Комаров, Павел Кротков
Условие задачи – Антон Банных
Подготовка тестов – Сергей Мельников
Подготовка разбора–Сергей Мельников
№12 слайд![Формальная постановка задачи](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img11.jpg)
Содержание слайда: Формальная постановка задачи
Дан массив целых чисел
Необходимо разбить его на три не пустые части, с суммами чисел S1, S2, S3
Минимизировать разность максимального и минимального из этих чисел
№13 слайд![Идея Подсчитаем частичные](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img12.jpg)
Содержание слайда: Идея
Подсчитаем частичные суммы на префиксе.
Теперь можно быстро находить сумму на отрезке с a до b
№14 слайд![Решение за Переберем длины](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img13.jpg)
Содержание слайда: Решение за
Переберем длины первой и второй частей
Вычислим S1, S2, S3 при помощи частичных сумм
Выберем лучший результат
№15 слайд![Решение за NlogN](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img14.jpg)
Содержание слайда: Решение за NlogN
№16 слайд![Решение за NlogN](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img15.jpg)
Содержание слайда: Решение за NlogN (2)
№17 слайд![Решение за NlogN](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img16.jpg)
Содержание слайда: Решение за NlogN (3)
№18 слайд![Решение за NlogN](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img17.jpg)
Содержание слайда: Решение за NlogN
№19 слайд![Решение за N](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img18.jpg)
Содержание слайда: Решение за N
№20 слайд![Задача C. Йою Ньерк](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img19.jpg)
Содержание слайда: Задача C. Йою Ньерк
№21 слайд![Авторы Идея задачи Антон Ахи](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img20.jpg)
Содержание слайда: Авторы
Идея задачи – Антон Ахи
Условие задачи – Антон Ахи
Подготовка тестов – Сергей Поромов
Подготовка разбора – Сергей Поромов
№22 слайд![Постановка задачи Есть](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img21.jpg)
Содержание слайда: Постановка задачи
Есть прямоугольное поле из улиц и авеню
Каждая улица и авеню односторонняя
Необходимо найти кратчайший путь от одного перекрестка до другого, из таких следует выбрать с минимальным числом поворотов, а уже из таких с максимумом минимального отрезка пути
№23 слайд![Частичные случаи Все улицы](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img22.jpg)
Содержание слайда: Частичные случаи
Все улицы направлены в одну сторону и все авеню тоже в одну сторону – 30 баллов. Ответ или не существует или из 1 или 2 отрезков.
Все авеню направлены в одну сторону – 50 баллов. Несложный разбор случаев – количество отрезков пути не более 3.
№24 слайд![Идея решения Количество](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img23.jpg)
Содержание слайда: Идея решения
Количество отрезков пути не превышает 5
№25 слайд![Идея решения Для нахождения](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img24.jpg)
Содержание слайда: Идея решения
Для нахождения кратчайшего пути использовать обход в ширину
Для выбора кратчайших путей с минимальным числом поворотов также использовать обход в ширину на 0-1 графе кратчайших путей
№26 слайд![Как максимизировать](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img25.jpg)
Содержание слайда: Как максимизировать минимальный отрезок?
Двоичный поиск по длине минимального отрезка
В графе кратчайших путей с минимальным числом поворотов искать путь от старта до финиша обходом в глубину
Обход в глубину делает шаг либо вперед в том же направлении на единичный отрезок, либо с поворотом на длину минимального отрезка
№27 слайд![Восстановление ответа Для](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img26.jpg)
Содержание слайда: Восстановление ответа
Для каждого перекрестка и направления, с которого приехали, запоминать длину последнего отрезка пути
Восстанавливать ответ с конца
№28 слайд![Время работы Обходы в ширину](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img27.jpg)
Содержание слайда: Время работы
Обходы в ширину - O(nm), двоичный поиск + обход в глубину суммарно O(nm·log(max(n, m)))
Решения за время порядка O(n3) получают около 80 баллов
№29 слайд![Задача D. Обратный кузнечик](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img28.jpg)
Содержание слайда: Задача D. Обратный кузнечик
№30 слайд![Авторы Идея задачи Владимир](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img29.jpg)
Содержание слайда: Авторы
Идея задачи – Владимир Ульянцев
Условие задачи – Владимир Ульянцев
Подготовка тестов – Антон Ахи
Подготовка разбора – Антон Ахи
№31 слайд![Постановка задачи Кузнечик](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img30.jpg)
Содержание слайда: Постановка задачи
Кузнечик прыгает на одну или две травинки вперед
Кузнечик не может находится на сломанной травинке
Найти такую конфигурацию целых и сломанных травинок, чтобы число различных путей кузнечика было ровно k
№32 слайд![Решение прямой задачи Если](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img31.jpg)
Содержание слайда: Решение «прямой» задачи
Если все n травинок целы, то число путей ─ n-ое число Фибоначчи
Когда отрезки из целых травинок разделены одной сломанной, число путей является произведением соответствующих чисел Фибоначчи
№33 слайд![Идея обратной задачи Число](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img32.jpg)
Содержание слайда: Идея «обратной» задачи
Число путей всегда является произведением чисел Фибоначчи
Требуется представить k в виде произведения чисел Фибоначчи
№34 слайд![Решение обратной задачи Чисел](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img33.jpg)
Содержание слайда: Решение «обратной» задачи
Чисел Фибоначчи, которые делят k, очень мало
Чисел, которые представимы произведениями этих чисел и являются делителями k, тоже мало
Будем перебирать на какое число Фибоначчи поделить k, после чего решать задачу для нового меньшего k
№35 слайд![Решение обратной задачи Для](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img34.jpg)
Содержание слайда: Решение «обратной» задачи
Для каждого k будем вычислять наименьшее число травинок необходимых, чтобы его получить
Вычисления для каждого k можно проводить один раз, запоминая результат
№36 слайд![Восстановление ответа Зная](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img35.jpg)
Содержание слайда: Восстановление ответа
Зная минимальное необходимо число травинок, можно его увеличивать, добавляя к последовательности либо 0 1, либо 0 1 1
Таким образом, если m ─ минимальное число травинок и n и m имеют разную четность, то необходимо добавить в конец 0 1 1
Далее добавлять в конец 0 1, пока это необходимо
№37 слайд![Тонкости решения Если m gt n](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img36.jpg)
Содержание слайда: Тонкости решения
Если m > n или m и n имеют разную четность и m + 3 > n, то ответ «Impossible»
Интересный случай: 2 1
k = 0 ─ особый случай: если n < 4, то ответ «Impossible», иначе ответом может быть, например, последовательность из нулей с единицами на концах
Важно понимать, что сломанных травинок используется на одну меньше, чем чисел Фибоначчи
№38 слайд![Альтернативные подходы Не](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img37.jpg)
Содержание слайда: Альтернативные подходы
Не перебирать делители k, а выстраивать произведения чисел Фибоначчи, аналогично задаче о рюкзаке
Пытаться жадно делить k на числа Фибоначчи (неверное решение ~70 баллов)
Перебирать все возможные конфигурации травинок и решать «прямую» задачу (40 баллов)
№39 слайд![Спасибо за внимание! Вопросы?](/documents_6/3b2547d02d35ea7d0cfe592d252a27e8/img38.jpg)
Содержание слайда: Спасибо за внимание!
Вопросы?