🗊Презентация Индивидуальная олимпиада по информатике и программированию. Очный тур

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №1Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №2Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №3Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №4Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №5Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №6Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №7Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №8Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №9Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №10Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №11Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №12Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №13Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №14Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №15Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №16Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №17Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №18Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №19Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №20Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №21Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №22Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №23Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №24Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №25Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №26Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №27Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №28Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №29Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №30Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №31Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №32Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №33Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №34Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №35Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №36Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №37Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №38Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №39
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Индивидуальная олимпиада по информатике и программированию. Очный тур. Доклад-сообщение содержит 39 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Индивидуальная олимпиада по информатике и программированию. Очный тур Разбор задач 27 марта 2011 года Москва, Новосибирск, Санкт-Петербург, Саратов, Челябинск
Описание слайда:
Индивидуальная олимпиада по информатике и программированию. Очный тур Разбор задач 27 марта 2011 года Москва, Новосибирск, Санкт-Петербург, Саратов, Челябинск

Слайд 2


Задача A. Ситха джедай против
Описание слайда:
Задача A. Ситха джедай против

Слайд 3


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

Слайд 4


Постановка задачи Два адепта Силы n умений Познания по каждому умению растут по линейному закону Найти день, в который познания по каждому умению у джедая будут не хуже, чем у ситха
Описание слайда:
Постановка задачи Два адепта Силы n умений Познания по каждому умению растут по линейному закону Найти день, в который познания по каждому умению у джедая будут не хуже, чем у ситха

Слайд 5


Упрощение постановки задачи Рассмотрим каждое умение в отдельности Условие того, что в день x познания джедая в этом уменнии будут не хуже, чем у ситха: Пусть и Неравенство приобрело вид
Описание слайда:
Упрощение постановки задачи Рассмотрим каждое умение в отдельности Условие того, что в день x познания джедая в этом уменнии будут не хуже, чем у ситха: Пусть и Неравенство приобрело вид

Слайд 6


Решение для одного умения нет решения
Описание слайда:
Решение для одного умения нет решения

Слайд 7


Решение Поддерживаем интервал, на котором джедай не хуже ситха Добавляем умения по одному Каждый раз нужно пересечь два интервала O(n)
Описание слайда:
Решение Поддерживаем интервал, на котором джедай не хуже ситха Добавляем умения по одному Каждый раз нужно пересечь два интервала O(n)

Слайд 8


Тонкости И числитель и знаменатель дроби может быть как положительным, так и отрицательным Деление с округлением требует разбора нескольких случаев при реализации в целых числах Лучше делить в вещественных числах, а затем округлять в нужную сторону
Описание слайда:
Тонкости И числитель и знаменатель дроби может быть как положительным, так и отрицательным Деление с округлением требует разбора нескольких случаев при реализации в целых числах Лучше делить в вещественных числах, а затем округлять в нужную сторону

Слайд 9


Простое решение Все ограничения на x не превосходят 1000, поэтому если решение есть, то оно находится на отрезке [0, 1000] Переберем 1001 день и для каждого дня проверим, подходит ли он O(nC), где C ─ ограничение сверху на начальные умения и ежедневные приросты
Описание слайда:
Простое решение Все ограничения на x не превосходят 1000, поэтому если решение есть, то оно находится на отрезке [0, 1000] Переберем 1001 день и для каждого дня проверим, подходит ли он O(nC), где C ─ ограничение сверху на начальные умения и ежедневные приросты

Слайд 10


Задача B. Министерство правды
Описание слайда:
Задача B. Министерство правды

Слайд 11


Авторы Идея задачи – Андрей Комаров, Павел Кротков Условие задачи – Антон Банных Подготовка тестов – Сергей Мельников Подготовка разбора–Сергей Мельников
Описание слайда:
Авторы Идея задачи – Андрей Комаров, Павел Кротков Условие задачи – Антон Банных Подготовка тестов – Сергей Мельников Подготовка разбора–Сергей Мельников

Слайд 12


Формальная постановка задачи Дан массив целых чисел Необходимо разбить его на три не пустые части, с суммами чисел S1, S2, S3 Минимизировать разность максимального и минимального из этих чисел
Описание слайда:
Формальная постановка задачи Дан массив целых чисел Необходимо разбить его на три не пустые части, с суммами чисел S1, S2, S3 Минимизировать разность максимального и минимального из этих чисел

Слайд 13


Идея Подсчитаем частичные суммы на префиксе. Теперь можно быстро находить сумму на отрезке с a до b
Описание слайда:
Идея Подсчитаем частичные суммы на префиксе. Теперь можно быстро находить сумму на отрезке с a до b

Слайд 14


Решение за Переберем длины первой и второй частей Вычислим S1, S2, S3 при помощи частичных сумм Выберем лучший результат
Описание слайда:
Решение за Переберем длины первой и второй частей Вычислим S1, S2, S3 при помощи частичных сумм Выберем лучший результат

Слайд 15


Решение за NlogN
Описание слайда:
Решение за NlogN

Слайд 16


Решение за NlogN (2)
Описание слайда:
Решение за NlogN (2)

Слайд 17


Решение за NlogN (3)
Описание слайда:
Решение за NlogN (3)

Слайд 18


Решение за NlogN
Описание слайда:
Решение за NlogN

Слайд 19


Решение за N
Описание слайда:
Решение за N

Слайд 20


Задача C. Йою Ньерк
Описание слайда:
Задача C. Йою Ньерк

Слайд 21


Авторы Идея задачи – Антон Ахи Условие задачи – Антон Ахи Подготовка тестов – Сергей Поромов Подготовка разбора – Сергей Поромов
Описание слайда:
Авторы Идея задачи – Антон Ахи Условие задачи – Антон Ахи Подготовка тестов – Сергей Поромов Подготовка разбора – Сергей Поромов

Слайд 22


Постановка задачи Есть прямоугольное поле из улиц и авеню Каждая улица и авеню односторонняя Необходимо найти кратчайший путь от одного перекрестка до другого, из таких следует выбрать с минимальным числом поворотов, а уже из таких с максимумом минимального отрезка пути
Описание слайда:
Постановка задачи Есть прямоугольное поле из улиц и авеню Каждая улица и авеню односторонняя Необходимо найти кратчайший путь от одного перекрестка до другого, из таких следует выбрать с минимальным числом поворотов, а уже из таких с максимумом минимального отрезка пути

Слайд 23


Частичные случаи Все улицы направлены в одну сторону и все авеню тоже в одну сторону – 30 баллов. Ответ или не существует или из 1 или 2 отрезков. Все авеню направлены в одну сторону – 50 баллов. Несложный разбор случаев – количество отрезков пути не более 3.
Описание слайда:
Частичные случаи Все улицы направлены в одну сторону и все авеню тоже в одну сторону – 30 баллов. Ответ или не существует или из 1 или 2 отрезков. Все авеню направлены в одну сторону – 50 баллов. Несложный разбор случаев – количество отрезков пути не более 3.

Слайд 24


Идея решения Количество отрезков пути не превышает 5
Описание слайда:
Идея решения Количество отрезков пути не превышает 5

Слайд 25


Идея решения Для нахождения кратчайшего пути использовать обход в ширину Для выбора кратчайших путей с минимальным числом поворотов также использовать обход в ширину на 0-1 графе кратчайших путей
Описание слайда:
Идея решения Для нахождения кратчайшего пути использовать обход в ширину Для выбора кратчайших путей с минимальным числом поворотов также использовать обход в ширину на 0-1 графе кратчайших путей

Слайд 26


Как максимизировать минимальный отрезок? Двоичный поиск по длине минимального отрезка В графе кратчайших путей с минимальным числом поворотов искать путь от старта до финиша обходом в глубину Обход в глубину делает шаг либо вперед в том же направлении на единичный отрезок, либо с поворотом на длину минимального отрезка
Описание слайда:
Как максимизировать минимальный отрезок? Двоичный поиск по длине минимального отрезка В графе кратчайших путей с минимальным числом поворотов искать путь от старта до финиша обходом в глубину Обход в глубину делает шаг либо вперед в том же направлении на единичный отрезок, либо с поворотом на длину минимального отрезка

Слайд 27


Восстановление ответа Для каждого перекрестка и направления, с которого приехали, запоминать длину последнего отрезка пути Восстанавливать ответ с конца
Описание слайда:
Восстановление ответа Для каждого перекрестка и направления, с которого приехали, запоминать длину последнего отрезка пути Восстанавливать ответ с конца

Слайд 28


Время работы Обходы в ширину - O(nm), двоичный поиск + обход в глубину суммарно O(nm·log(max(n, m))) Решения за время порядка O(n3) получают около 80 баллов
Описание слайда:
Время работы Обходы в ширину - O(nm), двоичный поиск + обход в глубину суммарно O(nm·log(max(n, m))) Решения за время порядка O(n3) получают около 80 баллов

Слайд 29


Задача D. Обратный кузнечик
Описание слайда:
Задача D. Обратный кузнечик

Слайд 30


Авторы Идея задачи – Владимир Ульянцев Условие задачи – Владимир Ульянцев Подготовка тестов – Антон Ахи Подготовка разбора – Антон Ахи
Описание слайда:
Авторы Идея задачи – Владимир Ульянцев Условие задачи – Владимир Ульянцев Подготовка тестов – Антон Ахи Подготовка разбора – Антон Ахи

Слайд 31


Постановка задачи Кузнечик прыгает на одну или две травинки вперед Кузнечик не может находится на сломанной травинке Найти такую конфигурацию целых и сломанных травинок, чтобы число различных путей кузнечика было ровно k
Описание слайда:
Постановка задачи Кузнечик прыгает на одну или две травинки вперед Кузнечик не может находится на сломанной травинке Найти такую конфигурацию целых и сломанных травинок, чтобы число различных путей кузнечика было ровно k

Слайд 32


Решение «прямой» задачи Если все n травинок целы, то число путей ─ n-ое число Фибоначчи Когда отрезки из целых травинок разделены одной сломанной, число путей является произведением соответствующих чисел Фибоначчи
Описание слайда:
Решение «прямой» задачи Если все n травинок целы, то число путей ─ n-ое число Фибоначчи Когда отрезки из целых травинок разделены одной сломанной, число путей является произведением соответствующих чисел Фибоначчи

Слайд 33


Идея «обратной» задачи Число путей всегда является произведением чисел Фибоначчи Требуется представить k в виде произведения чисел Фибоначчи
Описание слайда:
Идея «обратной» задачи Число путей всегда является произведением чисел Фибоначчи Требуется представить k в виде произведения чисел Фибоначчи

Слайд 34


Решение «обратной» задачи Чисел Фибоначчи, которые делят k, очень мало Чисел, которые представимы произведениями этих чисел и являются делителями k, тоже мало Будем перебирать на какое число Фибоначчи поделить k, после чего решать задачу для нового меньшего k
Описание слайда:
Решение «обратной» задачи Чисел Фибоначчи, которые делят k, очень мало Чисел, которые представимы произведениями этих чисел и являются делителями k, тоже мало Будем перебирать на какое число Фибоначчи поделить k, после чего решать задачу для нового меньшего k

Слайд 35


Решение «обратной» задачи Для каждого k будем вычислять наименьшее число травинок необходимых, чтобы его получить Вычисления для каждого k можно проводить один раз, запоминая результат
Описание слайда:
Решение «обратной» задачи Для каждого k будем вычислять наименьшее число травинок необходимых, чтобы его получить Вычисления для каждого k можно проводить один раз, запоминая результат

Слайд 36


Восстановление ответа Зная минимальное необходимо число травинок, можно его увеличивать, добавляя к последовательности либо 0 1, либо 0 1 1 Таким образом, если m ─ минимальное число травинок и n и m имеют разную четность, то необходимо добавить в конец 0 1 1 Далее добавлять в конец 0 1, пока это необходимо
Описание слайда:
Восстановление ответа Зная минимальное необходимо число травинок, можно его увеличивать, добавляя к последовательности либо 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», иначе ответом может быть, например, последовательность из нулей с единицами на концах Важно понимать, что сломанных травинок используется на одну меньше, чем чисел Фибоначчи
Описание слайда:
Тонкости решения Если m > n или m и n имеют разную четность и m + 3 > n, то ответ «Impossible» Интересный случай: 2 1 k = 0 ─ особый случай: если n < 4, то ответ «Impossible», иначе ответом может быть, например, последовательность из нулей с единицами на концах Важно понимать, что сломанных травинок используется на одну меньше, чем чисел Фибоначчи

Слайд 38


Альтернативные подходы Не перебирать делители k, а выстраивать произведения чисел Фибоначчи, аналогично задаче о рюкзаке Пытаться жадно делить k на числа Фибоначчи (неверное решение ~70 баллов) Перебирать все возможные конфигурации травинок и решать «прямую» задачу (40 баллов)
Описание слайда:
Альтернативные подходы Не перебирать делители k, а выстраивать произведения чисел Фибоначчи, аналогично задаче о рюкзаке Пытаться жадно делить k на числа Фибоначчи (неверное решение ~70 баллов) Перебирать все возможные конфигурации травинок и решать «прямую» задачу (40 баллов)

Слайд 39


Спасибо за внимание! Вопросы?
Описание слайда:
Спасибо за внимание! Вопросы?

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию