Что такое 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
  • Количество просмотров: 131
  • Количество скачиваний: 0
- Предыдущая Оценка обслуживания по телефону турфирмы
Следующая - Петр III (1761 - 1762)

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

Нет пакетам Нет пакетам 140
Общие сведения о микропроцессорных средствах автоматизации Общие сведения о микропроцессорных средствах автоматизации 132
Инструкция по технике безопасности и правилам поведения на уроке информатики Инструкция по технике безопасности и правилам поведения на уроке информатики 161
Управление компьютером Управление компьютером 128
Виртуальный туризм Виртуальный туризм 266
ТЕКСТ КАК ФОРМА ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ ТЕКСТ КАК ФОРМА ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ 127
Средства передачи информации 5-7 класс Средства передачи информации 5-7 класс 128
Компьютерные вирусы. Антивирусные программы. Компьютерные вирусы. Антивирусные программы. 129
Презентация по информатике Информатика в современном мире Презентация по информатике Информатика в современном мире 174
Оператори мови С++ Оператори мови С++ 101
Wechat. So what do people do with WeChat Wechat. So what do people do with WeChat 125
СУЩЕСТВЕННЫЕ СВОЙСТВА И ПРИНЯТИЕ РЕШЕНИЯ СУЩЕСТВЕННЫЕ СВОЙСТВА И ПРИНЯТИЕ РЕШЕНИЯ 31
Презентация Изучение видов компьютерной графики Презентация Изучение видов компьютерной графики 128
Удаление невидимых линий и поверхностей Удаление невидимых линий и поверхностей 137
Урок Программирование ветвящихся алгоритмов на Python Урок Программирование ветвящихся алгоритмов на Python 354
Начни зарабатывать на программах лояльности и кэшбэка Начни зарабатывать на программах лояльности и кэшбэка 112
Операции Операции 155
Безопасная работа в социальных сетях Безопасная работа в социальных сетях 128
Презентация по информатике Работа в PowerPoint Презентация по информатике Работа в PowerPoint 171
ВидеоБиблия ВидеоБиблия 133
Что такое моделирование Что такое моделирование 136
Понятие модели Понятие модели 135
Информационные ресурсы, позволяющие анализировать тексты на плагиат Информационные ресурсы, позволяющие анализировать тексты на плагиат 111
Macromedia flash Macromedia flash 131
Файловая система ЭВМ Файловая система ЭВМ 110
Экспертные системы Экспертные системы 122
Город будущего проект ученика 7 класса Город будущего проект ученика 7 класса 189
Работа со строками Работа со строками 122
Правила ведения телефонных переговоров Правила ведения телефонных переговоров 134
Фотошоп. Смарт-объекты Фотошоп. Смарт-объекты 95