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

Нажмите для полного просмотра!

Индивидуальная олимпиада по информатике и программированию. Очный тур, слайд №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 года Москва, Новосибирск, Санкт-Петербург, Саратов, Челябинск

Слайд 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 баллов)