Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Десятая Всероссийская командная олимпиада школьников по программированию

Содержание

Задача A. Поедание сыра
Десятая Всероссийская командная олимпиада школьников по программированиюРазбор задач14 ноября 2009 годаСанкт-Петербург Задача A. Поедание сыра Авторы задачиАвтор задачи — Сергей МельниковУсловие — Андрей СтанкевичПодготовка тестов — Антон АхиРазбор — Сергей Мельников Общая идеяИспользуем двоичный поиск по ответуДано t, можно ли организовать поедание сыра, Интересные интервалыПусть Ti – все моменты времени ri и DiT1 < T2 Скорости всех мышей равны 1Рассмотрим сетьВ ней надо найти максимальный потокРебро из Скорости всех мышей равны 1Три сыраp1=1 r1=2 d1=2p2=3 r2=1 d2=4p3=2 r3=2 d3=4Две мыши Разные скорости мышейУпорядочим мышей по неубыванию скоростей:s1 ≥ s2 ≥ … ≥ Модификация сетиРаньше былоЗаменим, на такой фрагментKj,k – одни и те же разных i и одного Ik Общее решениеДвоичный поискПоток в специальной сети Спасибо за внимание! Вопросы по задаче A? Задача B. Соревнования по программированию Авторы задачиАвтор задачи — Владимир УльянцевУсловие — Федор ЦаревПодготовка тестов — Антон АхиРазбор — Антон Ахи О чем задача?Дан список файлов и определения для каталогов с тестами, задач Как решать?Востановить полностью дерево каталогов и файловИспользовать символ «\» как разделитель имен Как посчитать количество описаний соревнований?В получившемся дереве файлов/каталогов проверить про каждый каталог, Сколько работает?Во входном файле задано не более 100000 файлов/каталоговКаждый каталог просматривается один раз Спасибо за внимание! Вопросы по задаче B? Задача C. Распил Авторы задачиАвторы задачи — Елена Андреева, Владимир ГуровицУсловие — Андрей СтанкевичПодготовка тестов — Антон БанныхРазбор — Антон Банных О чем задача?Придумать n-угольник, который можно распилить на k-угольник и m-угольник разрезом, Какие n, m, k допустимы?Если m + k = n m + k = n + 1 m + k = n + 2 m + k = n + 3 m + k = n + 4 m + k = n + 4, k < 5 Дополнительный случай Спасибо за внимание! Вопросы по задаче C? Задача D. Электричество Авторы задачиАвтор задачи — Владимир ГуровицУсловие — Федор ЦаревПодготовка тестов — Сергей ПоромовРазбор — Антон Банных О чем задача?В наличии:k сетевых фильтровn элетроприборов1 розеткаТребуется подсоединить все элетроприборы так, Основные идеиНе имеет смысла поключать фильтр к фильтру с меньшей максимальной нагрузкой.Наиболее РешениеОтсортировать электроприборы и фильтры в порядке невозрастания мощностей.Строить ответ жадно, начиная с фильтра, подключенного к розетке. Спасибо за внимание! Вопросы по задаче D? Задача E. Адронные коллайдеры Авторы задачиАвтор задачи — Михаил КеверУсловие — Федор ЦаревПодготовка тестов — Сергей ПоромовРазбор — Сергей Мельников Две окружностиДве окружности: найдем окружность с центром на прямой, соединяющей центры исходных окружностей Две окружностиДля любой точки С на перпендикуляре восстановленном в точке D – существует окружность являющаяся решением Три окружностиТри окружности:Построим прямую на которой может быть центр окружности делящей пополам Три окружности Спасибо за внимание! Вопросы по задаче E? Задача F. Космические захватчики Авторы задачиАвтор задачи — Георгий КорнеевУсловие — Павел МавринПодготовка тестов — Антон БанныхРазбор — Антон Ахи О чем задача?В столбцах находятся ai захватчиковПушка за одно действие либо перемещается Частный случай Если пушка стоит в крайнем столбце, то нужно уничтожить всех РешениеДойти до ближайшего из краев, далее действовать по предыдущему плануОтвет — Σai+(n-1)+min(p-1,n-p) Спасибо за внимание! Вопросы по задаче F? Задача G. Пробежки по Манхэттену Авторы задачиАвтор задачи — Михаил ДворкинУсловие — Павел МавринПодготовка тестов — Олег ДавыдовРазбор — Михаил Дворкин О чем задача?Объект передвигается по Манхэттену, пробегая за t минут не более УтверждениеВ каждый момент времени множество точек, в которых может находиться объект, составляют В начальный момент времениЭто точка (0, 0) — вырожденный прямоугольник. За t минут…Объект может пройти не более t кварталов. Прямоугольник «расширяется во все стороны на t» Данные от навигатора…Сообщают, в каком квадрате может находиться объект.Пересечем прямоугольник и квадрат Спасибо за внимание! Вопросы по задаче G? Задача H. Следующее разбиение на слагаемые Авторы задачиАвтор задачи — Андрей СтанкевичУсловие — Андрей СтанкевичПодготовка тестов — Сергей МельниковРазбор — Сергей Мельников Генерация следующего комбинаторного объектаДано разбиение5=1+1+3Идём с конца, пока нельзя увеличить слагаемоеУвеличим слагаемое Когда можно увеличить слагаемое?Первое слагаемое с конца нельзя увеличитьВторое слагаемое с конца На сколько можно увеличить слагаемое?Слагаемое можно увеличить на 1, если оно было Минимальный «хвост»?Надо вывести хвост с суммой S, при этом последнее слагаемое которое Спасибо за внимание! Вопросы по задаче H? Задача I. Самодвойственный документ Авторы задачиАвтор задачи — Сергей МельниковУсловие — Андрей СтанкевичПодготовка тестов — Сергей МельниковРазбор — Сергей Мельников Условие задачиВ задаче надо построить граф из n вершинПервый отдел: пары чисел Когда ответ существует?В полном графе из n вершин n(n - 1)/2 реберЕсли 4k вершин4 вершины4k вершин – заменить вершины 2 и 3 на полные 12 вершин 4k + 1 вершина4k+1 вершина – заменить вершины 2 и 3 на 13 вершин Спасибо за внимание! Вопросы по задаче I? Задача J. Цирковое шоу Авторы задачиАвтор задачи — Юрий ПетровУсловие — Павел МавринПодготовка тестов — Юрий ПетровРазбор — Юрий Петров ФормулировкаДан набор отрезковВыбрать два поднабора, объединения которых не пересекаютсяМаксимизировать минимум размеров Идея решенияДинамическое программирование Решение: вычисляемая функцияФункция f(a, n, t):a — самый правый из отрезков, взятых в Решение: переходыПеребрать отрезок b, который будет завершать следующую группуПеребрать набор, в который Оценка времени работыВсего есть n×n×2 состоянийИз каждого O(n) переходовПереходы перебирать в порядке Спасибо за внимание! Вопросы по задаче J? Задача K. Красивая таблица результатов Авторы задачиАвтор задачи — Владимир УльнцевУсловие — Андрей СтанкевичПодготовка тестов — Владимир УльянцевРазбор — Антон Ахи О чем задача?Таблица результатов считается красивой, если количество задач, решенных каждой из Как решать?Для каждой команды увеличивать количество сданных ею задач, пока это не Спасибо за внимание! Вопросы?http://neerc.ifmo.ru/school
Слайды презентации

Слайд 2 Задача A. Поедание сыра

Задача A. Поедание сыра

Слайд 3 Авторы задачи
Автор задачи — Сергей Мельников
Условие — Андрей Станкевич
Подготовка тестов —

Авторы задачиАвтор задачи — Сергей МельниковУсловие — Андрей СтанкевичПодготовка тестов — Антон АхиРазбор — Сергей Мельников

Антон Ахи
Разбор — Сергей Мельников

Слайд 4 Общая идея
Используем двоичный поиск по ответу
Дано t, можно

Общая идеяИспользуем двоичный поиск по ответуДано t, можно ли организовать поедание

ли организовать поедание сыра, чтобы мыши не ели сыр

более чем через t часов, после того как сыр начал портится
Обозначим Di = di + t

Слайд 5 Интересные интервалы
Пусть Ti – все моменты времени ri

Интересные интервалыПусть Ti – все моменты времени ri и DiT1 <

и Di
T1 < T2 < … < Tn
Время

разбивается на интервалы [Ti, Ti+1]
Сыр или можно есть в течение всего интервала, или нельзя

Слайд 6 Скорости всех мышей равны 1
Рассмотрим сеть
В ней надо

Скорости всех мышей равны 1Рассмотрим сетьВ ней надо найти максимальный потокРебро

найти максимальный поток
Ребро из cыра i в интервал k,

если этот сыр можно есть в этот интервал

Можно, если все рёбра из s насыщены

Слайд 7 Скорости всех мышей равны 1
Три сыра
p1=1 r1=2 d1=2
p2=3

Скорости всех мышей равны 1Три сыраp1=1 r1=2 d1=2p2=3 r2=1 d2=4p3=2 r3=2 d3=4Две мыши

r2=1 d2=4
p3=2 r3=2 d3=4


Две мыши




Слайд 8 Разные скорости мышей
Упорядочим мышей по неубыванию скоростей:
s1 ≥

Разные скорости мышейУпорядочим мышей по неубыванию скоростей:s1 ≥ s2 ≥ …

s2 ≥ … ≥ sm
Представим (m-1)-ю мышь, как

набор из мыши со скоростью sm, и мыши со скоростью sm-1-sm
Аналогично разобьем (m-2)-ю мышь на 3 три мыши: sm, sm-1-sm и sm-2-sm-1
И так далее



Слайд 9 Модификация сети
Раньше было
Заменим, на такой фрагмент
Kj,k – одни

Модификация сетиРаньше былоЗаменим, на такой фрагментKj,k – одни и те же разных i и одного Ik

и те же разных i и одного Ik

Слайд 10 Общее решение
Двоичный поиск
Поток в специальной сети

Общее решениеДвоичный поискПоток в специальной сети

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

Спасибо за внимание! Вопросы по задаче A?

Слайд 12 Задача B. Соревнования по программированию

Задача B. Соревнования по программированию

Слайд 13 Авторы задачи
Автор задачи — Владимир Ульянцев
Условие — Федор Царев
Подготовка тестов —

Авторы задачиАвтор задачи — Владимир УльянцевУсловие — Федор ЦаревПодготовка тестов — Антон АхиРазбор — Антон Ахи

Антон Ахи
Разбор — Антон Ахи

Слайд 14 О чем задача?
Дан список файлов и определения для

О чем задача?Дан список файлов и определения для каталогов с тестами,

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

описаний соревнаваний

Слайд 15 Как решать?
Востановить полностью дерево каталогов и файлов
Использовать символ

Как решать?Востановить полностью дерево каталогов и файловИспользовать символ «\» как разделитель

«\» как разделитель имен в путях
Для каждого каталога хранить

список подкаталогов и файлов в нем, например с помощью хеш-таблицы

Слайд 16 Как посчитать количество описаний соревнований?
В получившемся дереве файлов/каталогов

Как посчитать количество описаний соревнований?В получившемся дереве файлов/каталогов проверить про каждый

проверить про каждый каталог, является ли он каталогом с

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

Слайд 17 Сколько работает?
Во входном файле задано не более 100000

Сколько работает?Во входном файле задано не более 100000 файлов/каталоговКаждый каталог просматривается один раз

файлов/каталогов
Каждый каталог просматривается один раз

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

Спасибо за внимание! Вопросы по задаче B?

Слайд 19 Задача C. Распил

Задача C. Распил

Слайд 20 Авторы задачи
Авторы задачи — Елена Андреева, Владимир Гуровиц
Условие — Андрей

Авторы задачиАвторы задачи — Елена Андреева, Владимир ГуровицУсловие — Андрей СтанкевичПодготовка тестов — Антон БанныхРазбор — Антон Банных

Станкевич
Подготовка тестов — Антон Банных
Разбор — Антон Банных

Слайд 21 О чем задача?
Придумать n-угольник, который можно распилить на

О чем задача?Придумать n-угольник, который можно распилить на k-угольник и m-угольник

k-угольник и m-угольник разрезом, проходящим через две его вершины.

Слайд 22 Какие n, m, k допустимы?
Если

Какие n, m, k допустимы?Если ,

,

решения нет.
Иначе при достаточно больших n, m, k искомый многоугольник существует.


Слайд 23 m + k = n

m + k = n

Слайд 24 m + k = n + 1

m + k = n + 1

Слайд 25 m + k = n + 2

m + k = n + 2

Слайд 26 m + k = n + 3

m + k = n + 3

Слайд 27 m + k = n + 4

m + k = n + 4

Слайд 28 m + k = n + 4, k

m + k = n + 4, k < 5 Дополнительный случай

< 5 Дополнительный случай

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

Спасибо за внимание! Вопросы по задаче C?

Слайд 30 Задача D. Электричество

Задача D. Электричество

Слайд 31 Авторы задачи
Автор задачи — Владимир Гуровиц
Условие — Федор Царев
Подготовка тестов —

Авторы задачиАвтор задачи — Владимир ГуровицУсловие — Федор ЦаревПодготовка тестов — Сергей ПоромовРазбор — Антон Банных

Сергей Поромов
Разбор — Антон Банных

Слайд 32 О чем задача?
В наличии:
k сетевых фильтров
n элетроприборов
1 розетка
Требуется

О чем задача?В наличии:k сетевых фильтровn элетроприборов1 розеткаТребуется подсоединить все элетроприборы

подсоединить все элетроприборы так, чтобы потребляемая ими мощность не

превышала допустимую для сетевого фильтра.
К сетевому фильтру можно подсоединить не более одного сетевого фильтра.

Слайд 33 Основные идеи
Не имеет смысла поключать фильтр к фильтру

Основные идеиНе имеет смысла поключать фильтр к фильтру с меньшей максимальной

с меньшей максимальной нагрузкой.
Наиболее мощные приборы имеет смысл ставить

ближе к розетке.

Слайд 34 Решение
Отсортировать электроприборы и фильтры в порядке невозрастания мощностей.
Строить

РешениеОтсортировать электроприборы и фильтры в порядке невозрастания мощностей.Строить ответ жадно, начиная с фильтра, подключенного к розетке.

ответ жадно, начиная с фильтра, подключенного к розетке.

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

Спасибо за внимание! Вопросы по задаче D?

Слайд 36 Задача E. Адронные коллайдеры

Задача E. Адронные коллайдеры

Слайд 37 Авторы задачи
Автор задачи — Михаил Кевер
Условие — Федор Царев
Подготовка тестов —

Авторы задачиАвтор задачи — Михаил КеверУсловие — Федор ЦаревПодготовка тестов — Сергей ПоромовРазбор — Сергей Мельников

Сергей Поромов
Разбор — Сергей Мельников

Слайд 38 Две окружности
Две окружности: найдем окружность с центром на

Две окружностиДве окружности: найдем окружность с центром на прямой, соединяющей центры исходных окружностей

прямой, соединяющей центры исходных окружностей

Слайд 39 Две окружности
Для любой точки С на перпендикуляре восстановленном

Две окружностиДля любой точки С на перпендикуляре восстановленном в точке D – существует окружность являющаяся решением

в точке D – существует окружность являющаяся решением

Слайд 40 Три окружности
Три окружности:
Построим прямую на которой может быть

Три окружностиТри окружности:Построим прямую на которой может быть центр окружности делящей

центр окружности делящей пополам O1 и O2
Построим прямую

на которой может быть центр окружности делящей пополам O2 и O3
Найдем их точку пересечения - X

Слайд 41 Три окружности

Три окружности

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

Спасибо за внимание! Вопросы по задаче E?

Слайд 43 Задача F. Космические захватчики

Задача F. Космические захватчики

Слайд 44 Авторы задачи
Автор задачи — Георгий Корнеев
Условие — Павел Маврин
Подготовка тестов —

Авторы задачиАвтор задачи — Георгий КорнеевУсловие — Павел МавринПодготовка тестов — Антон БанныхРазбор — Антон Ахи

Антон Банных
Разбор — Антон Ахи

Слайд 45 О чем задача?
В столбцах находятся ai захватчиков
Пушка за

О чем задача?В столбцах находятся ai захватчиковПушка за одно действие либо

одно действие либо перемещается в соседний столбец, либо производит

выстрел и убивает одного захватчика
Необходимо уничтожить всех захватчиков за минимальное количество действий

Слайд 46 Частный случай
Если пушка стоит в крайнем столбце,

Частный случай Если пушка стоит в крайнем столбце, то нужно уничтожить

то нужно уничтожить всех захватчиков в этом столбце и

перейти к следующему
Ответ — сумма общего количества захватчиков и количества перемещений, то есть Σai+(n-1)

Слайд 47 Решение
Дойти до ближайшего из краев, далее действовать по

РешениеДойти до ближайшего из краев, далее действовать по предыдущему плануОтвет — Σai+(n-1)+min(p-1,n-p)

предыдущему плану
Ответ — Σai+(n-1)+min(p-1,n-p)

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

Спасибо за внимание! Вопросы по задаче F?

Слайд 49 Задача G. Пробежки по Манхэттену

Задача G. Пробежки по Манхэттену

Слайд 50 Авторы задачи
Автор задачи — Михаил Дворкин
Условие — Павел Маврин
Подготовка тестов —

Авторы задачиАвтор задачи — Михаил ДворкинУсловие — Павел МавринПодготовка тестов — Олег ДавыдовРазбор — Михаил Дворкин

Олег Давыдов
Разбор — Михаил Дворкин

Слайд 51 О чем задача?
Объект передвигается по Манхэттену, пробегая за

О чем задача?Объект передвигается по Манхэттену, пробегая за t минут не

t минут не более чем t кварталов.
Каждые t минут навигатор сообщает

точку, где находится объект, с точностью до d кварталов.
Где может находиться объект в данный момент времени?

Слайд 52 Утверждение
В каждый момент времени множество точек, в которых

УтверждениеВ каждый момент времени множество точек, в которых может находиться объект,

может находиться объект, составляют прямоугольник, стороны которого повернуты на

45° относительно осей координат.

Слайд 53 В начальный момент времени
Это точка (0, 0) — вырожденный

В начальный момент времениЭто точка (0, 0) — вырожденный прямоугольник.

прямоугольник.

Слайд 54 За t минут…
Объект может пройти не более t кварталов.

За t минут…Объект может пройти не более t кварталов. Прямоугольник «расширяется во все стороны на t»


Прямоугольник «расширяется во все стороны на t»

Слайд 55 Данные от навигатора…
Сообщают, в каком квадрате может находиться

Данные от навигатора…Сообщают, в каком квадрате может находиться объект.Пересечем прямоугольник и

объект.
Пересечем прямоугольник и квадрат (с параллельными осями) — получим новый

прямоугольник.

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

Спасибо за внимание! Вопросы по задаче G?

Слайд 57 Задача H. Следующее разбиение на слагаемые

Задача H. Следующее разбиение на слагаемые

Слайд 58 Авторы задачи
Автор задачи — Андрей Станкевич
Условие — Андрей Станкевич
Подготовка тестов —

Авторы задачиАвтор задачи — Андрей СтанкевичУсловие — Андрей СтанкевичПодготовка тестов — Сергей МельниковРазбор — Сергей Мельников

Сергей Мельников
Разбор — Сергей Мельников

Слайд 59 Генерация следующего комбинаторного объекта
Дано разбиение
5=1+1+3
Идём с конца, пока

Генерация следующего комбинаторного объектаДано разбиение5=1+1+3Идём с конца, пока нельзя увеличить слагаемоеУвеличим

нельзя увеличить слагаемое
Увеличим слагаемое на минимальную величину
Допишем минимальный «хвост»

Слайд 60 Когда можно увеличить слагаемое?
Первое слагаемое с конца нельзя

Когда можно увеличить слагаемое?Первое слагаемое с конца нельзя увеличитьВторое слагаемое с

увеличить
Второе слагаемое с конца можно увеличить
Например можно прибавить к

нему последнее слагаемое
5=1+1+3 → 5=1+4

Слайд 61 На сколько можно увеличить слагаемое?
Слагаемое можно увеличить на

На сколько можно увеличить слагаемое?Слагаемое можно увеличить на 1, если оно

1, если оно было меньше последнего хотя бы на

2
5=1+1+3 → 5=1+2+2
Иначе его надо увеличить на величину последнего слагаемого
5=1+2+2 → 5=1+4

Слайд 62 Минимальный «хвост»?
Надо вывести хвост с суммой S, при

Минимальный «хвост»?Надо вывести хвост с суммой S, при этом последнее слагаемое

этом последнее слагаемое которое было выведено перед ним равно

K
Выведем несколько(возможно ноль) слагаемых K, а затем остаток
Остаток должен быть не меньше чем K

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

Спасибо за внимание! Вопросы по задаче H?

Слайд 64 Задача I. Самодвойственный документ

Задача I. Самодвойственный документ

Слайд 65 Авторы задачи
Автор задачи — Сергей Мельников
Условие — Андрей Станкевич
Подготовка тестов —

Авторы задачиАвтор задачи — Сергей МельниковУсловие — Андрей СтанкевичПодготовка тестов — Сергей МельниковРазбор — Сергей Мельников

Сергей Мельников
Разбор — Сергей Мельников

Слайд 66 Условие задачи
В задаче надо построить граф из n

Условие задачиВ задаче надо построить граф из n вершинПервый отдел: пары

вершин
Первый отдел: пары чисел – это ребра графа
Второй отдел:

пары чисел – это вершины между которыми ребра нет
Граф изоморфен своему дополнению

Слайд 67 Когда ответ существует?
В полном графе из n вершин

Когда ответ существует?В полном графе из n вершин n(n - 1)/2

n(n - 1)/2 ребер

Если n = 4k + 2

или n = 4k + 3, то ребер нечетное число – ответ «No»

Если n = 4k или n = 4k + 1, то ответ «Yes»

Слайд 68 4k вершин
4 вершины
4k вершин – заменить вершины 2

4k вершин4 вершины4k вершин – заменить вершины 2 и 3 на

и 3 на полные графы, 1 и 4 –

на пустые

Слайд 69 12 вершин

12 вершин

Слайд 70 4k + 1 вершина
4k+1 вершина – заменить вершины

4k + 1 вершина4k+1 вершина – заменить вершины 2 и 3

2 и 3 на полные графы, 1 и 4

– на пустые

5 вершин

Слайд 71 13 вершин

13 вершин

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

Спасибо за внимание! Вопросы по задаче I?

Слайд 73 Задача J. Цирковое шоу

Задача J. Цирковое шоу

Слайд 74 Авторы задачи
Автор задачи — Юрий Петров
Условие — Павел Маврин
Подготовка тестов —

Авторы задачиАвтор задачи — Юрий ПетровУсловие — Павел МавринПодготовка тестов — Юрий ПетровРазбор — Юрий Петров

Юрий Петров
Разбор — Юрий Петров

Слайд 75 Формулировка
Дан набор отрезков
Выбрать два поднабора, объединения которых не

ФормулировкаДан набор отрезковВыбрать два поднабора, объединения которых не пересекаютсяМаксимизировать минимум размеров

пересекаются
Максимизировать минимум размеров

Слайд 76 Идея решения
Динамическое программирование

Идея решенияДинамическое программирование

Слайд 77 Решение: вычисляемая функция
Функция f(a, n, t):
a — самый правый

Решение: вычисляемая функцияФункция f(a, n, t):a — самый правый из отрезков, взятых

из отрезков, взятых в один из наборов
n — текущее количество

отрезков в первом наборе
t — какому набору принадлежит отрезок a
Значение — максимальное количество отрезков во втором наборе

Слайд 78 Решение: переходы
Перебрать отрезок b, который будет завершать следующую

Решение: переходыПеребрать отрезок b, который будет завершать следующую группуПеребрать набор, в

группу
Перебрать набор, в который взять эту группу
Все отрезки, лежащие

правее конца a и левее конца b, выгодно взять в тот же набор

Слайд 79 Оценка времени работы
Всего есть n×n×2 состояний
Из каждого O(n)

Оценка времени работыВсего есть n×n×2 состоянийИз каждого O(n) переходовПереходы перебирать в

переходов
Переходы перебирать в порядке возрастания конца отрезка
Суммарное время обработки

переходов из одного состояния O(n)
Итоговое время O(n3)

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

Спасибо за внимание! Вопросы по задаче J?

Слайд 81 Задача K. Красивая таблица результатов

Задача K. Красивая таблица результатов

Слайд 82 Авторы задачи
Автор задачи — Владимир Ульнцев
Условие — Андрей Станкевич
Подготовка тестов —

Авторы задачиАвтор задачи — Владимир УльнцевУсловие — Андрей СтанкевичПодготовка тестов — Владимир УльянцевРазбор — Антон Ахи

Владимир Ульянцев
Разбор — Антон Ахи

Слайд 83 О чем задача?
Таблица результатов считается красивой, если количество

О чем задача?Таблица результатов считается красивой, если количество задач, решенных каждой

задач, решенных каждой из команд, либо 0, либо делитель

числа задач на соревновании
Сколько еще можно сдать задач, чтобы таблица не переставала быть красивой

Слайд 84 Как решать?
Для каждой команды увеличивать количество сданных ею

Как решать?Для каждой команды увеличивать количество сданных ею задач, пока это

задач, пока это не изменяет красоту таблицы результатов
У количества

задач на соревновании не может быть более 24 подряд идущих делителей, так как минимальное число, которое делится на все числа от 1 до 24 это ― 5354228880
  • Имя файла: desyataya-vserossiyskaya-komandnaya-olimpiada-shkolnikov-po-programmirovaniyu.pptx
  • Количество просмотров: 114
  • Количество скачиваний: 0
- Предыдущая Оценка обслуживания по телефону турфирмы
Следующая - Петр III (1761 - 1762)

Похожие презентации

Виртуальный батл- мероприятие для уч-ся 10-11 классов Виртуальный батл- мероприятие для уч-ся 10-11 классов 145
Возможности Paint Возможности Paint 113
Логические условия выбора данных Логические условия выбора данных 102
Что изучает информатика? Что изучает информатика? 119
Презентация Оптимизация подготовки к ОГЭ по информатике и ИКТ Презентация Оптимизация подготовки к ОГЭ по информатике и ИКТ 112
Алгоритм (5 класс) Алгоритм (5 класс) 131
Java. Графический интерфейс пользователя Java. Графический интерфейс пользователя 131
2. Java Spring Core 3. Spring IoC Container 2. Java Spring Core 3. Spring IoC Container 105
Разработка информационной системы делопроизводства Разработка информационной системы делопроизводства 123
Презентация-тест по информатике на тему Корпорация Apple Презентация-тест по информатике на тему Корпорация Apple 139
Впровадження ІКТ при вивченні іноземних мов Впровадження ІКТ при вивченні іноземних мов 138
Презентация к уроку информатики в 5 классе Что такое пиксель? Презентация к уроку информатики в 5 классе Что такое пиксель? 115
Презентация по информатике на тему: Диаграммы (5 класс) Презентация по информатике на тему: Диаграммы (5 класс) 196
Урок 14. Связь между составом сложного объекта и адресами его компонентов Урок 14. Связь между составом сложного объекта и адресами его компонентов 113
Безопасный интернет-способы защиты Безопасный интернет-способы защиты 96
Строки и функции (язык C) Строки и функции (язык C) 118
Двумерные массивы Двумерные массивы 100
Элективный курс по подготовке обучающихся к ОГЭ _ 2020, вариант 2 Элективный курс по подготовке обучающихся к ОГЭ _ 2020, вариант 2 121
Информационные модели Информационные модели 103
Данные и программы. Файлы и файловая система Данные и программы. Файлы и файловая система 110
Бэкап Бэкап 217
Автоматизированные информационные технологии обработки данных в налоговой службе Автоматизированные информационные технологии обработки данных в налоговой службе 125
Мир медиа. Опечатки и ошибки в российской прессе Мир медиа. Опечатки и ошибки в российской прессе 95
Презентация к уроку информатики в 9 классе по теме Одномерные массивы целых чисел Презентация к уроку информатики в 9 классе по теме Одномерные массивы целых чисел 151
Зрительные иллюзии Зрительные иллюзии 100
Вики-технология Вики-технология 187
Управление компьютером с помощью меню Управление компьютером с помощью меню 91
Супер - ЭВМ Супер - ЭВМ 134
История развития вычислительной техники История развития вычислительной техники 120
Презентация по информатике на тему Алгебра логики (8 класс) Презентация по информатике на тему Алгебра логики (8 класс) 96