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