WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«21 февраля 2016 года 1 / 32 Задача A. Зонд на Нибиру Задача A. Зонд на Нибиру Задача A. Зонд на Нибиру Автор задачи Нияз Нигматуллин ...»

Открытая Олимпиада Университета

Иннополис по программированию

21 февраля 2016 года

1 / 32

Задача A. Зонд на Нибиру

Задача A. Зонд на Нибиру

Задача A. Зонд на Нибиру

Автор задачи Нияз Нигматуллин

Подготовка задачи Нияз Нигматуллин

2 / 32

Задача A. Зонд на Нибиру Постановка задачи

Постановка задачи

Задан многоугольник

Нужно провести вертикальную полосу ширины L

Максимизировать площадь пересечения полосы и

многоугольника

3 / 32

Задача A. Зонд на Нибиру Решение задачи

Решение задачи Выпуклый многоугольник Функция: f (x) площадь пересечения, если левый конец полосы в точке x f (x) выпукла Троичный поиск или другой метод поиска локального максимума s(a) площадь пересечения полуплоскости x a и многоугольника f (x) = s(x + L) s(x) Пересечь вертикальную прямую с многоугольником и посчитать площадь нового многоугольника 4 / 32 Задача A. Зонд на Нибиру Решение задачи Решение задачи Стороны параллельны осям координат Ответ в целой точке Перебрать точку, посчитать ответ 5 / 32 Задача A. Зонд на Нибиру Решение задачи Решение задачи Сканирующая прямая по x Поддерживаем f (x) Событие начала отрезка и конца Каждый отрезок вносит вклад в площадь, как площадь под этим отрезком Трапеция Каждый со своим знаком Отрезок слева направо отрицательный Справа налево положительный 6 / 32 Задача A. Зонд на Нибиру Решение задачи Решение задачи Поддерживаем сумму высот трапеций Также поддерживаем сумму изменений высот Площадь трапеции между двумя событиями x1 и



x2 :

(x2 x1 )·h + h (x2 x1 ) Делаем для каждого события добавления отрезка в x удаление отрезка в x + L Максимизируем функцию площади между двумя событиями (xx1 )·h + h (x x1 ) Квадратичная функция от x h Максимум в h Время работы: O(n log n) 7 / 32 Задача A. Зонд на Нибиру Решение задачи Альтернативное решение Есть большие проблемы с точностью Поэтому координаты и требуемая точность ответа малы Между целым x и x + 1 функция квадратична Можно воспользоваться численным методом для поиска Время работы: O(max |xi | · SEARCH), где SEARCH это время поиска максимума 8 / 32 Задача A. Зонд на Нибиру Вопросы?

Вопросы?

–  –  –

Постановка задачи Назовем число забавным, если оно само составное, а количество его делителей простое.

Цель посчитать количество таких числе на отрезке [L... R].

–  –  –

Решение первой части за O(n2) Заданный граф дерево, между каждой парой вершин есть ровно один простой путь.

Этот простой путь и будет кратчайшим.

Запустим обход в глубину или в ширину от каждой вершины.

–  –  –

Вторая часть за O(m!) Переберем все последовательности посещения событий.

Проверим, что возможно перейти от каждого события до следующего.

Обновим ответ длиной последовательности.

–  –  –

Решение первой части за O(n · log (n)) Выбираем любую вершину дерева и называем её корнем.

Храним длину пути от корня до каждой вершины.

Разбиваем путь от вершины a до вершины b их lca.

–  –  –

Вторая часть за O(m · log (m) · log (n)) Хотим обновить dp[ev] через prevEv.

Пусть v вершина события ev, u события prevEv, x вершина, разделяющая v и u.

Можем обновить ev через prevEv, если time(prevEv ) + dist(u, v ) time(ev )

–  –  –

Вторая часть за O(m · log (m) · log (n)) time(prevEv ) + dist(u, v ) time(ev ) time(prevEv ) + dist(u, x) + dist(x, v ) time(ev ) time(prevEv ) + dist(u, x) time(ev ) dist(x, v )

–  –  –

Вторая часть за O(m · log (m) · log (n)) time(prevEv ) + dist(u, x) time(ev ) dist(x, v ) Для каждой вершины x сохраним в массиве undex[x] все события e, которые были в дереве в момент, когда x была разделяющей, в порядке увеличения величины time(e) + dist(x, y), где y вершина, в которой проходит событие e.

Переберем событие ev, переберем разделяющую вершину x, надо обновить ответ на некотором префиксе массива under[x]

–  –  –

Вторая часть за O(m · log (m) · log (n)) Длину префикса массива under[x] находим двоичным поиском На массивах under[x] храним структуру данных, поддерживающую операции RMQ Обновим значения элементов массивов under[x] числом dp[ev]

–  –  –

Постановка задачи 2 отсортированных массива моментов времени, в которые звонят 2 друга.

Узнать какое минимальное и максимальное количество гостей из n друзей может придти на каждую из вечеринок.

–  –  –

Решение задачи Все друзья равнозначны.

В любой момент времени для каждого друга:

никто не звонил, звонил Амир, Булат или оба.

Если Амир пригласил максимальное количество, то Булат минимальное. Аналогично наоборот.

–  –  –

Решение задачи Находим максимум для Амира и минимум для Булата.

Рассматриваем моменты времени в порядке возрастания.

Амир всегда звонит тому, кого еще никто не пригласил.

Булат должен звонить тому, кого уже пригласил Амир, иначе неприглашенному.

–  –  –

Решение задачи Находим максимум для Амира и минимум для Булата.

Рассматриваем моменты времени в порядке возрастания.

Амир всегда звонит тому, кого еще никто не пригласил.

Булат должен звонить тому, кого уже пригласил Амир, иначе неприглашенному.

–  –  –

Вопросы?

32 / 32 Аттракцион Камень, ножницы, бумага – 2 Камень, ножницы, бумага – 2 Постановка задачи Два игрока играют в камень, ножницы, бумагу. Необходимо определить минимальное количество раз, когда выигрывает первый, если известно, что первый поставил камень 1 раз, ножницы – 1 раз, бумагу – 1 раз.

Второй – 2, 2 и 2 раз соответственно.

Камень, ножницы, бумага – 2 Идея решения Представим результаты игры в виде такой таблицы.

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

Камень, ножницы, бумага – 2 Идея решения Итак, надо минимизировать сумму 3 + 4 + 8 Для удобства переобозначим столбцы.

Камень, ножницы, бумага – 2 Идея решения Заметим, что можно взять любую пару столбцов и строк и сделать следующее преобразование:

Камень, ножницы, бумага – 2 Идея решения Так можно делать, если все значения остаются неотрицательными. Обнулим все значения на диагонали, кроме одного.

Камень, ножницы, бумага – 2 Идея решения Пусть мы решили оставить ненулевым 3 Попробуем сократить и его.

Камень, ножницы, бумага – 2 Идея решения 3 = 1 2 2. Это минимальное количество раз, когда бумага первого побеждает камень второго.

Камень, ножницы, бумага – 2 Решение Заметим, что среди всех диагональных элементов в ходе таких преобразований мы могли выбрать, какой из элементов оставить ненулевым.

Тогда ответом к задаче будет Камень, ножницы, бумага – 2 Альтернативное решение Чтобы совсем не думать над задачей, можно написать алгоритм нахождения максимального потока минимальной стоимости на следующем



Похожие работы:

«70 ABF Misting Руководство по эксплуатации : (8182)63-90-72 (4012)72-03-81 (831)429-08-12 (4812)29-41-54 +7(7172)727-132 (4842)92-23-67 (3843)20-46-81 (862)225-72-31 (4722)40-23-64 (3842)65-04-62 (383)227-86-73 (8652)20-65-13 (4832)59-03-52 (8332)68-02-04 (...»

«Мнения, приведенные в настоящей презентации, отражают мнение автора и не обязательно отражают мнение или политику Азиатского банка развития (АБР), или его Совета директоров, или правительств, которые они представляют. АБР не гарантирует точност...»

«СЦЕНАРИЙ городской игры-конкурса «Дело мастера боится» посвященной выбору профессии «Все работы хороши!»ЦЕЛИ И ЗАДАЧИ: дать общее представление об основных видах профессий, показать значение трудовой деятельности в жизни человека, воспитывать уважение к люд...»

«ВОЛОГОДСКІЯ Е І І А Р Х І и р н ы я ВДОМОСТИ. (Годъ сорововый). Находятъ, I * 15 чиселъ каждаго мсяца. Цна этого номера1'20 ко­ п е к ъ. Ц Н А годовому изданію для соборовъ, монастырей и приход­ скихъ церквей епархіи ПЯТЬ рублей; дл...»

«Этапы проведения научного исследования студента При подготовке и проведении исследования выделяют несколько этапов, которые отличаются друг от друга характером и содержанием, формами и процедурами исследовательской деятельности. Эти этапы взаимосвязаны и объединены логикой единого...»

«ВЕРХОВНА РАДА УКРАЇНИ ІНФОРМАЦІЙНЕ УПРАВЛІННЯ ВЕРХОВНА РАДА УКРАЇНИ У Д ЗЕРКАЛІ ЗМІ: За повідомленнями друкованих та інтернет-ЗМІ, телебачення і радіомовлення 13 листопада 2013 р., середа ДРУКОВАНІ ВИДАННЯ Для розвитку відносин із Республікою Білорусь є значний потенціал «Голос України» Учора в парламенті відбулося...»

«ДОГОВОР № _/НКО на осуществление деятельности банковским платежным агентом г. Йошкар-Ола 2015г. Небанковская кредитная организация «МОНЕТА.РУ» (общество с ограниченной ответственностью), именуемое в дальнейшем «НКО», в лице Председателя Правления Маймина Владислава Рувимовича, действующего на основании Устава, с одной сторо...»

«УСТАНОВЛЕНИЕ ПРИОРИТЕТА ЗАЯВКИ НА ПОЛЕЗНУЮ МОДЕЛЬ (ИЗОБРЕТЕНИЕ) ПО ДАТЕ ПОДАЧИ ТЕМ ЖЕ ЗАЯВИТЕЛЕМ БОЛЕЕ РАННЕЙ ЗАЯВКИ НА ПРОМЫШЛЕННЫЙ ОБРАЗЕЦ, И НАОБОРОТ А. М. ПАНТЮХИНА, директор патентного агентства ИнформПатентПитер, российский и евразийский патентный поверенный, Санкт-Петербург Редко, но бывает, что в заявке на выдачу патента на промышле...»

«1 Содержание. I. Целевой раздел. Пояснительная записка индивидуальной адаптированной 3 программы для ребнка с ОВЗ (аутизм). Цели и задачи реализации Программы 4 Принципы и подходы к реализации Программы. 4 Характеристики, значимые для разраб...»








 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.