WWW.NEW.PDFM.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Собрание документов
 

«школьников по информатике Иннополис 26 марта – 1 апреля 2017 года Всероссийская олимпиада школьников по информатике Задача 1 Программирование квадрокоптеров Задача 1 Программирование ...»

Всероссийская олимпиада школьников по информатике

Всероссийская олимпиада

школьников по информатике

Иннополис

26 марта – 1 апреля 2017 года

Всероссийская олимпиада школьников по информатике

Задача 1 Программирование квадрокоптеров

Задача 1 Программирование

квадрокоптеров

Идея задачи жюри олимпиады

Подготовка тестов Максим Ахмедов,

Григорий Резников, Рамис Ямилов

Разбор задачи Рамис Ямилов

Всероссийская олимпиада школьников по информатике

Задача 1 Программирование квадрокоптеров Постановка задачи Постановка задачи Загадана правильная скобочная последовательность длины n Разрешается задавать вопросы про правильность некоторых фрагментов этой последовательности Требуется отгадать эту последовательность Всероссийская олимпиада школьников по информатике Задача 1 Программирование квадрокоптеров Решение Решение на 49 баллов Спросим про все подотрезки Если подотрезок является правильной скобочной последовательностью, то на ее концах находятся открывающая и закрывающая скобки Каждый символ принадлежит границе какого-либо правильного подотрезка За n(n 1)/2 запросов мы выясним информацию про все символы Всероссийская олимпиада школьников по информатике Задача 1 Программирование квадрокоптеров Решение Решение Поскольку последовательность является правильной, для каждой открывающей скобки имеется парная закрывающая, находящаяся правее Будем находить символы последовательности по порядку Пусть мы уже выяснили, какие символы находятся на позициях 1 .



.. i 1, а последняя открывающая скобка без пары находится на позиции x Всероссийская олимпиада школьников по информатике Задача 1 Программирование квадрокоптеров Решение Решение Для того, чтобы узнать, какой символ находится на позиции i, зададим вопрос про фрагмент [x... i] Если на позиции i находится закрывающая скобка, то она является парной к открывающей с позиции x, и поэтому фрагмент [x... i] будет правильной скобочной последовательностью Всероссийская олимпиада школьников по информатике Задача 1 Программирование квадрокоптеров Решение Решение Для того чтобы эффективно находить последнюю открывающую скобку без пары, будем хранить их позиции в стек

–  –  –

Решение на 30 баллов O(qnA) Заметим, что если все числа меньше 2k, то минимальное x также меньше 2k, поскольку более старшие биты не будут влиять на сравнения

Сделаем, что написано:

После каждого запроса перебёрем число x Для каждого 1 i n 1 проверим что ai x ai+1 x Всероссийская олимпиада школьников по информатике Задача 2 Иллюзия сортировки Решение

–  –  –

Полное решение O(q(log n + log A))

Оптимизируем дерево отрезков:

Заметим, что в предыдущем решении в каждой вершине хранилось 60 булевых значений Используем битовое сжатие Запрос изменения подъём по дереву O(log n) Ответ на запрос формируем в корне дерева отрезков за O(log A) Всероссийская олимпиада школьников по информатике Задача 2 Иллюзия сортировки Решение Полное решение O(q log A)

Избавимся от дерева отрезков:

Заметим, что мы использовали только корень дерева отрезков для ответа на запрос Заменим дерево отрезков на массив (количество ограничений для каждой пары {i, 0/1}) Обрабатываем запрос и отвечаем за O(log A) Всероссийская олимпиада школьников по информатике Задача 2 Иллюзия сортировки Решение Дальнейшие оптимизации





Работаем с битами:

Что нас тормозит?

Поиск старшего бита в числе x Используем функцию __builtin_clz (count leading zeroes за O(log w)) На некоторых компьютерах доступна ассемблерная инструкция BSR Предподсчитаем ответ для всех 16-битных слов Всероссийская олимпиада школьников по информатике Задача 2 Иллюзия сортировки Решение

–  –  –

Подзадача 5 (100 баллов) Бонус! Автоматически проходится при сочетании предыдущих идей Всероссийская олимпиада школьников по информатике Задача 5 Накопитель Постановка задачи

–  –  –

Решение за O(n), при ri = C, 15 баллов l[i] L L = L Всероссийская олимпиада школьников по информатике Задача 6 Серверы на Меркурии Решение

–  –  –

Решение за O(n), 100 баллов Если отрезок времени, когда канал открыт, не пересекается с допустимым отрезком, то для i + 1 и всех следующих ответа нет Всероссийская олимпиада школьников по информатике Задача 6 Серверы на Меркурии Решение Решение за O(n), 100 баллов Левая граница так же как в предыдущей подзадаче Всероссийская олимпиада школьников по информатике Задача 6 Серверы на Меркурии Решение

–  –  –

Дисклеймер В данной презентации длины обеих последовательностей обозначаются как n :) Всероссийская олимпиада школьников по информатике Задача 8 Траектория обучения

–  –  –

Divide & Conquer Всероссийская олимпиада школьников по информатике Задача 8 Траектория обучения Divide & Conquer Всероссийская олимпиада школьников по информатике Задача 8 Траектория обучения

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

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Улан-Удэнский колледж железнодорожного транспорта Улан-Удэнского института железнодорожного транспорта филиала федерального государственного бюджетного образовательного учреждения высшего образова...»

«НАЦИОНАЛЬНЫЙ ЦЕНТР ОБЩЕСТВЕННО-ПРОФЕССИОНАЛЬНОЙ АККРЕДИТАЦИИ ПРЕДСТАВЛЕНИЕ к общественно-профессиональной аккредитации образовательных программ "Прикладная математика и информатика", "Информационные технологии (Фундаментальные...»

«Polar “Physics of Auroral Phenomena”, Proc. XXXIX Annual Seminar, Apatity, pp. 119-122, 2016 Geophysical Polar Geophysical Institute, 2016 Institute ИССЛЕДОВАНИЕ ВЛИЯНИЯ МАГНИТНОГО ПОЛЯ НА ВЫСОКОШИРОТНЫЕ КВ ТРАСС...»

«Компания Postgres Professional Е. П. Моргунов ЯЗЫК SQL. БАЗОВЫЙ КУРС УЧЕБНО-ПРАКТИЧЕСКОЕ ПОСОБИЕ Москва 2017 УДК 004.655 ББК 32.973.26-018.2 М79 Моргунов, Е. П. М79 Язык SQL . Базовый курс: учеб.-практ. пособие / Е. П. Моргунов; под ред. Е. В. Рогова, П. В. Лузанова; Postgres Professional. — М., 2017. — 256...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования "РОССИЙСКИЙ ГОСУДАРСТВЕННыЙ ГУМАНИТАРНыЙ УНИВЕРСИТЕТ" DIES ACADEMICUS 2015/2016 итоги Москва 2016 ББК 74.58 И93 Dies academicus: Итоги 2016/2016 у...»

«КОНКУРСНОЕ ЗАДАНИЕ МОБИЛЬНАЯ РОБОТОТЕХНИКА ИНФОРМАЦИЯ ДЛЯ КОНКУРСАНТОВ Робот-контролер игровой площадки Главный эксперт Е.О. Какоулина WSR2017_TP23 СОДЕРЖАНИЕ Введение 1. Роботы конкурсантов 2. Журна...»

«УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ СИБИРСКОГО ОТДЕЛЕНИЯ РАН (ИВТ СО РАН) ИТОГОВЫЙ ОТЧЕТ о научной и научноорганизационной деятельности в 2010 году Нов...»

«ОБЩАЯ ХАРАКТЕРИСТИКА ОСНОВНОЙ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЫ 09.06.01 "Информатика и вычислительная техника" 09.06.01_09 "Математическое моделирование, численные методы и комплексы программ" Выпускающий институт: Компьютерных наук и технолог...»






 
2018 www.new.pdfm.ru - «Бесплатная электронная библиотека - собрание документов»

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