Презентация Десятая Всероссийская командная олимпиада школьников по программированию онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Десятая Всероссийская командная олимпиада школьников по программированию абсолютно бесплатно. Урок-презентация на эту тему содержит всего 85 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:85 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:5.32 MB
- Просмотров:74
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Десятая Всероссийская командная олимпиада школьников по программированию
Разбор задач
14 ноября 2009 года
Санкт-Петербург
№2 слайд
Содержание слайда: Задача A. Поедание сыра
№3 слайд
Содержание слайда: Авторы задачи
Автор задачи — Сергей Мельников
Условие — Андрей Станкевич
Подготовка тестов — Антон Ахи
Разбор — Сергей Мельников
№4 слайд
Содержание слайда: Общая идея
Используем двоичный поиск по ответу
Дано t, можно ли организовать поедание сыра, чтобы мыши не ели сыр более чем через t часов, после того как сыр начал портится
Обозначим Di = di + t
№5 слайд
Содержание слайда: Интересные интервалы
Пусть Ti – все моменты времени ri и Di
T1 < T2 < … < Tn
Время разбивается на интервалы [Ti, Ti+1]
Сыр или можно есть в течение всего интервала, или нельзя
№6 слайд
Содержание слайда: Скорости всех мышей равны 1
Рассмотрим сеть
В ней надо найти максимальный поток
№7 слайд
Содержание слайда: Скорости всех мышей равны 1
№8 слайд
Содержание слайда: Разные скорости мышей
Упорядочим мышей по неубыванию скоростей:
s1 ≥ s2 ≥ … ≥ sm
Представим (m-1)-ю мышь, как набор из мыши со скоростью sm, и мыши со скоростью sm-1-sm
Аналогично разобьем (m-2)-ю мышь на 3 три мыши: sm, sm-1-sm и sm-2-sm-1
И так далее
№9 слайд
Содержание слайда: Модификация сети
Раньше было
№10 слайд
Содержание слайда: Общее решение
Двоичный поиск
Поток в специальной сети
№11 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче A?
№12 слайд
Содержание слайда: Задача B. Соревнования по программированию
№13 слайд
Содержание слайда: Авторы задачи
Автор задачи — Владимир Ульянцев
Условие — Федор Царев
Подготовка тестов — Антон Ахи
Разбор — Антон Ахи
№14 слайд
Содержание слайда: О чем задача?
Дан список файлов и определения для каталогов с тестами, задач и описаний соревнований
Необходимо посчитать количество описаний соревнаваний
№15 слайд
Содержание слайда: Как решать?
Востановить полностью дерево каталогов и файлов
Использовать символ «\» как разделитель имен в путях
Для каждого каталога хранить список подкаталогов и файлов в нем, например с помощью хеш-таблицы
№16 слайд
Содержание слайда: Как посчитать количество описаний соревнований?
В получившемся дереве файлов/каталогов проверить про каждый каталог, является ли он каталогом с тестами, задачей или описанием соревнований
Не зыбыть, что в каталоге с тестами могут быть подкаталоги
№17 слайд
Содержание слайда: Сколько работает?
Во входном файле задано не более 100000 файлов/каталогов
Каждый каталог просматривается один раз
№18 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче B?
№19 слайд
Содержание слайда: Задача C. Распил
№20 слайд
Содержание слайда: Авторы задачи
Авторы задачи — Елена Андреева, Владимир Гуровиц
Условие — Андрей Станкевич
Подготовка тестов — Антон Банных
Разбор — Антон Банных
№21 слайд
Содержание слайда: О чем задача?
Придумать n-угольник, который можно распилить на k-угольник и m-угольник разрезом, проходящим через две его вершины.
№22 слайд
Содержание слайда: Какие n, m, k допустимы?
Если , решения нет.
Иначе при достаточно больших n, m, k искомый многоугольник существует.
№23 слайд
Содержание слайда: m + k = n
№24 слайд
Содержание слайда: m + k = n + 1
№25 слайд
Содержание слайда: m + k = n + 2
№26 слайд
Содержание слайда: m + k = n + 3
№27 слайд
Содержание слайда: m + k = n + 4
№28 слайд
Содержание слайда: m + k = n + 4, k < 5
Дополнительный случай
№29 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче C?
№30 слайд
Содержание слайда: Задача D. Электричество
№31 слайд
Содержание слайда: Авторы задачи
Автор задачи — Владимир Гуровиц
Условие — Федор Царев
Подготовка тестов — Сергей Поромов
Разбор — Антон Банных
№32 слайд
Содержание слайда: О чем задача?
В наличии:
k сетевых фильтров
n элетроприборов
1 розетка
Требуется подсоединить все элетроприборы так, чтобы потребляемая ими мощность не превышала допустимую для сетевого фильтра.
К сетевому фильтру можно подсоединить не более одного сетевого фильтра.
№33 слайд
Содержание слайда: Основные идеи
Не имеет смысла поключать фильтр к фильтру с меньшей максимальной нагрузкой.
Наиболее мощные приборы имеет смысл ставить ближе к розетке.
№34 слайд
Содержание слайда: Решение
Отсортировать электроприборы и фильтры в порядке невозрастания мощностей.
Строить ответ жадно, начиная с фильтра, подключенного к розетке.
№35 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче D?
№36 слайд
Содержание слайда: Задача E. Адронные коллайдеры
№37 слайд
Содержание слайда: Авторы задачи
Автор задачи — Михаил Кевер
Условие — Федор Царев
Подготовка тестов — Сергей Поромов
Разбор — Сергей Мельников
№38 слайд
Содержание слайда: Две окружности
Две окружности: найдем окружность с центром на прямой, соединяющей центры исходных окружностей
№39 слайд
Содержание слайда: Две окружности
Для любой точки С на перпендикуляре восстановленном в точке D – существует окружность являющаяся решением
№40 слайд
Содержание слайда: Три окружности
Три окружности:
Построим прямую на которой может быть центр окружности делящей пополам O1 и O2
Построим прямую на которой может быть центр окружности делящей пополам O2 и O3
Найдем их точку пересечения - X
№41 слайд
Содержание слайда: Три окружности
№42 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче E?
№43 слайд
Содержание слайда: Задача F. Космические захватчики
№44 слайд
Содержание слайда: Авторы задачи
Автор задачи — Георгий Корнеев
Условие — Павел Маврин
Подготовка тестов — Антон Банных
Разбор — Антон Ахи
№45 слайд
Содержание слайда: О чем задача?
В столбцах находятся ai захватчиков
Пушка за одно действие либо перемещается в соседний столбец, либо производит выстрел и убивает одного захватчика
Необходимо уничтожить всех захватчиков за минимальное количество действий
№46 слайд
Содержание слайда: Частный случай
Если пушка стоит в крайнем столбце, то нужно уничтожить всех захватчиков в этом столбце и перейти к следующему
Ответ — сумма общего количества захватчиков и количества перемещений, то есть ai+(n-1)
№47 слайд
Содержание слайда: Решение
Дойти до ближайшего из краев, далее действовать по предыдущему плану
Ответ — ai+(n-1)+min(p-1,n-p)
№48 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче F?
№49 слайд
Содержание слайда: Задача G. Пробежки по Манхэттену
№50 слайд
Содержание слайда: Авторы задачи
Автор задачи — Михаил Дворкин
Условие — Павел Маврин
Подготовка тестов — Олег Давыдов
Разбор — Михаил Дворкин
№51 слайд
Содержание слайда: О чем задача?
Объект передвигается по Манхэттену, пробегая за t минут не более чем t кварталов.
Каждые t минут навигатор сообщает точку, где находится объект, с точностью до d кварталов.
Где может находиться объект в данный момент времени?
№52 слайд
Содержание слайда: Утверждение
В каждый момент времени множество точек, в которых может находиться объект, составляют прямоугольник, стороны которого повернуты на 45° относительно осей координат.
№53 слайд
Содержание слайда: В начальный момент времени
Это точка (0, 0) —
вырожденный прямоугольник.
№54 слайд
Содержание слайда: За t минут…
Объект может пройти не более t кварталов.
Прямоугольник «расширяется во все стороны на t»
№55 слайд
Содержание слайда: Данные от навигатора…
Сообщают, в каком квадрате может находиться объект.
Пересечем прямоугольник и квадрат (с параллельными осями) — получим новый прямоугольник.
№56 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче G?
№57 слайд
Содержание слайда: Задача H. Следующее разбиение на слагаемые
№58 слайд
Содержание слайда: Авторы задачи
Автор задачи — Андрей Станкевич
Условие — Андрей Станкевич
Подготовка тестов — Сергей Мельников
Разбор — Сергей Мельников
№59 слайд
Содержание слайда: Генерация следующего комбинаторного объекта
Дано разбиение
5=1+1+3
Идём с конца, пока нельзя увеличить слагаемое
Увеличим слагаемое на минимальную величину
Допишем минимальный «хвост»
№60 слайд
Содержание слайда: Когда можно увеличить слагаемое?
Первое слагаемое с конца нельзя увеличить
Второе слагаемое с конца можно увеличить
Например можно прибавить к нему последнее слагаемое
5=1+1+3 → 5=1+4
№61 слайд
Содержание слайда: На сколько можно увеличить слагаемое?
Слагаемое можно увеличить на 1, если оно было меньше последнего хотя бы на 2
5=1+1+3 → 5=1+2+2
Иначе его надо увеличить на величину последнего слагаемого
5=1+2+2 → 5=1+4
№62 слайд
Содержание слайда: Минимальный «хвост»?
Надо вывести хвост с суммой S, при этом последнее слагаемое которое было выведено перед ним равно K
Выведем несколько(возможно ноль) слагаемых K, а затем остаток
Остаток должен быть не меньше чем K
№63 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче H?
№64 слайд
Содержание слайда: Задача I. Самодвойственный документ
№65 слайд
Содержание слайда: Авторы задачи
Автор задачи — Сергей Мельников
Условие — Андрей Станкевич
Подготовка тестов — Сергей Мельников
Разбор — Сергей Мельников
№66 слайд
Содержание слайда: Условие задачи
В задаче надо построить граф из n вершин
Первый отдел: пары чисел – это ребра графа
Второй отдел: пары чисел – это вершины между которыми ребра нет
Граф изоморфен своему дополнению
№67 слайд
Содержание слайда: Когда ответ существует?
В полном графе из n вершин n(n - 1)/2 ребер
Если n = 4k + 2 или n = 4k + 3, то ребер нечетное число – ответ «No»
Если n = 4k или n = 4k + 1, то ответ «Yes»
№68 слайд
Содержание слайда: 4k вершин
4 вершины
№69 слайд
Содержание слайда: 12 вершин
№70 слайд
Содержание слайда: 4k + 1 вершина
5 вершин
№71 слайд
Содержание слайда: 13 вершин
№72 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче I?
№73 слайд
Содержание слайда: Задача J. Цирковое шоу
№74 слайд
Содержание слайда:
№75 слайд
Содержание слайда:
№76 слайд
Содержание слайда:
№77 слайд
Содержание слайда:
№78 слайд
Содержание слайда:
№79 слайд
Содержание слайда:
№80 слайд
Содержание слайда: Спасибо за внимание!
Вопросы по задаче J?
№81 слайд
Содержание слайда: Задача K. Красивая таблица результатов
№82 слайд
Содержание слайда: Авторы задачи
Автор задачи — Владимир Ульнцев
Условие — Андрей Станкевич
Подготовка тестов — Владимир Ульянцев
Разбор — Антон Ахи
№83 слайд
Содержание слайда: О чем задача?
Таблица результатов считается красивой, если количество задач, решенных каждой из команд, либо 0, либо делитель числа задач на соревновании
Сколько еще можно сдать задач, чтобы таблица не переставала быть красивой
№84 слайд
Содержание слайда: Как решать?
Для каждой команды увеличивать количество сданных ею задач, пока это не изменяет красоту таблицы результатов
У количества задач на соревновании не может быть более 24 подряд идущих делителей, так как минимальное число, которое делится на все числа от 1 до 24 это ― 5354228880
№85 слайд
Содержание слайда: Спасибо за внимание!
Вопросы?
Скачать все slide презентации Десятая Всероссийская командная олимпиада школьников по программированию одним архивом:
