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

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


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

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

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

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

Презентация на тему ВКОШП-2011. Разбор задач

Содержание

Задача AНаибольший общий делитель
ВКОШП-2011Разбор задачСанкт-Петербург, 2011 Задача AНаибольший общий делитель Автор задачи – Виталий АксёновУсловие – Виталий АксёновПодготовка тестов – Виталий АксёновРазбор – Виталий Аксёнов Постановка задачиДано n чисел и число dНадо найти какой-нибудь поднабор из чисел, Как решать?Взять все числа, которые делятся на dТеперь взять у них у ОбоснованиеПусть есть какой-то другой набор, который удовлетворяет насВсе элементы из этого набора Задача BЗащита беженцев Автор задачи – Алексей ЦыпленковУсловие – Антон БанныхПодготовка тестов – Антон БанныхРазбор – Виталий Аксёнов Постановка задачиДан многоугольник PТочка называется защищённой, если любой луч проведённый из него Как решать?Если из какой-то точки луч уходит на бесконечность, продлим его в Как решать?Утверждение: если сделать такую операцию для каждой точки, для которой существует Как решать? (продолжение)Проведем лучи для всех пар вершинДля всех таких лучей проведём Как решать? (продолжение)Утверждается, что освещённый отрезок на стороне ограничен самой левой освещённой Как решать? (продолжение)Осталось восстановить ответУтверждение: вершины нашего нового многоугольника – концы невырожденных “освещённых” частей Задача CТелефонный номер Автор задачи – Михаил ДворкинУсловие – Евгений КурпилянскийПодготовка тестов – Евгений КурпилянскийРазбор – Павел Кунявский Постановка задачиДан телефонный номер – последовательность чисел, разделенных дефисамиНеобходимо найти все телефонные Как решать?Найдем последовательность слов, которые используются при произношении данного номераЗаметим, что слова Как решать? (продолжение)Нужно перебрать всевозможные расстановки дефисов между словами и вывести все, ОбоснованиеКоличество слов в тестах меньше 100 (так как цифр не больше 50)Количество Задача DГостиница Автор задачи – Антон БанныхУсловие – Антон АхиПодготовка тестов – Антон АхиРазбор – Антон Ахи Постановка задачиДано число nНадо его разложить на сумму двоек и троек с минимальным числом слагаемых Как решать?Понятно, что нам не имеет смысла иметь в сумме больше двух Задача EПарад Автор задачи – Сергей ПоромовУсловие – Сергей МельниковПодготовка тестов – Сергей МельниковРазбор – Сергей Мельников Постановка задачиЕсть последовательность из n чиселНадо разбить их на убывающую и возрастающую подпоследовательности Как решать?Будем считать динамику less[i] и greater[i]Разбиение чисел хорошее – разбиение чисел Как решать? (продолжение)В какой последовательности находится i-ый элемент:В убывающей, less[i] равен минимальному Как решать? (продолжение)В возрастающей, greater[i] равен максимуму из последних элементов всех убывающих ПересчётLess[i]if a[i+1]a[i] then greater[i+1]= Как решать? (продолжение)Если мы не смогли посчитать less[n] или greater[n], то ответ Задача FМагазин Автор задачи – Николай ВедерниковУсловие – Николай ВедерниковПодготовка тестов – Николай ВедерниковРазбор – Николай Ведерников Постановка задачиДано n стоимостей товаров и известно, что k-ый бесплатноНайти минимальное число Как решать?Отсортируем все цены в порядке убыванияРазобьём их на группы по k, Задача GЗанос Автор задачи – Николай ВедерниковУсловие – Виталий АксёновПодготовка тестов – Виталий АксёновРазбор – Николай Ведерников Постановка задачиДано 5 чиселМаксимальная скорость автомобиля - vДлина первого отрезка трассы - Как решать?Заметим, что ситуация с разгоном и ситуация с торможением совершенно одинаковы, Как решать? (продолжение)Понятно, что нам надо сразу разгоняться с ускорением a до Задача HЧай Автор задачи – Антон АхиУсловие – Антон АхиПодготовка тестов – Антон АхиРазбор – Антон Ахи Постановка задачиДан чайник объёма V и мощностью N, температура воды в чайнике Как решать?Отсортируем членов жюри по временам приходаИ просто нужно запросы жюри обрабатывать Подводные камниНужно не забывать, что минимальная температура воды в чайнике – 20 градусовИзначально чайник был пуст Задача IКомандная олимпиада Автор задачи – Юрий ПетровУсловие – Никита ИоффеПодготовка тестов – Никита ИоффеРазбор – Никита Иоффе Постановка задачиДана перестановка чисел 1, 1, 2, 2, …, n, nТребуется найти Как решать?Заметим, что нам подходят только перестановки, что расстояние между двумя одинаковыми Как решать? (продолжение)Построим полный двудольный граф и на ребре из i в Задача JПоезда Автор задачи – Виталий АксёновУсловие – Никита ИоффеПодготовка тестов – Никита ИоффеРазбор – Павел Кунявский Постановка задачиНайти k-ую в лексикографическом порядке последовательность, которую можно отсортировать стеком Как решать?Заметим, что количество таких перестановок из n элементов равно числу Каталана, Как решать? (продолжение)Если мы на первое место поставим число i, то последовательность Как решать? (продолжение)Теперь просто решаем стандартную задачу о восстановлении k-ого комбинаторного объекта, Задача KКоролевская династия Автор задачи – Глеб ЕвстроповУсловие – Михаил ПядёркинПодготовка тестов – Михаил ПядёркинРазбор – Олег Давыдов Постановка задачиДано подвешенное дерево из n вершинДано m запросов, состоящих из 2 Как решать? Обойдём dfs-ом вершины, и отметим для каждой времена входа in[v] Как решать? (продолжение)Обрабатываем запрос:Пусть h[v] – высота вершины vРассмотрим набор вершин, находящихся Спасибо за внимание! Вопросы?http://neerc.ifmo.ru/school
Слайды презентации

Слайд 2 Задача A
Наибольший общий делитель

Задача AНаибольший общий делитель

Слайд 3 Автор задачи – Виталий Аксёнов
Условие – Виталий Аксёнов
Подготовка

Автор задачи – Виталий АксёновУсловие – Виталий АксёновПодготовка тестов – Виталий АксёновРазбор – Виталий Аксёнов

тестов – Виталий Аксёнов
Разбор – Виталий Аксёнов


Слайд 4 Постановка задачи
Дано n чисел и число d
Надо найти

Постановка задачиДано n чисел и число dНадо найти какой-нибудь поднабор из

какой-нибудь поднабор из чисел, такой что их наибольший общий

делитель равен d

Слайд 5 Как решать?
Взять все числа, которые делятся на d
Теперь

Как решать?Взять все числа, которые делятся на dТеперь взять у них

взять у них у всех наибольший общий делитель
Если он

равен d, то выводим это множество, если нет, то вывести -1

Слайд 6 Обоснование
Пусть есть какой-то другой набор, который удовлетворяет нас
Все

ОбоснованиеПусть есть какой-то другой набор, который удовлетворяет насВсе элементы из этого

элементы из этого набора обязаны делиться на d, а,

значит, этот набор является подмножеством нашего
Следовательно НОД этого набора может быть только больше, чем НОД нашего, а, значит, если наш набор не удовлетворяет, то и другой тоже

Слайд 7 Задача B
Защита беженцев

Задача BЗащита беженцев

Слайд 8 Автор задачи – Алексей Цыпленков
Условие – Антон Банных
Подготовка

Автор задачи – Алексей ЦыпленковУсловие – Антон БанныхПодготовка тестов – Антон БанныхРазбор – Виталий Аксёнов

тестов – Антон Банных
Разбор – Виталий Аксёнов


Слайд 9 Постановка задачи
Дан многоугольник P
Точка называется защищённой, если любой

Постановка задачиДан многоугольник PТочка называется защищённой, если любой луч проведённый из

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

многоугольник, состоящий из защищённых точек

Слайд 10 Как решать?
Если из какой-то точки луч уходит на

Как решать?Если из какой-то точки луч уходит на бесконечность, продлим его

бесконечность, продлим его в другую сторону до пересечения со

стороной (будем считать такую точку на стороне освещённой)
Назовём такую операцию “освещением”

Слайд 11 Как решать?
Утверждение: если сделать такую операцию для каждой

Как решать?Утверждение: если сделать такую операцию для каждой точки, для которой

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

на каждой стороне может быть максимум 1 освещённый отрезок


Слайд 12 Как решать? (продолжение)
Проведем лучи для всех пар вершин
Для всех

Как решать? (продолжение)Проведем лучи для всех пар вершинДля всех таких лучей

таких лучей проведём нашу операцию “освещение”
На каждой стороне получили

набор освещённых точек

Слайд 13 Как решать? (продолжение)
Утверждается, что освещённый отрезок на стороне ограничен

Как решать? (продолжение)Утверждается, что освещённый отрезок на стороне ограничен самой левой

самой левой освещённой точкой на стороне и самой правой

освещённой точкой стороне


Слайд 14 Как решать? (продолжение)
Осталось восстановить ответ
Утверждение: вершины нашего нового многоугольника

Как решать? (продолжение)Осталось восстановить ответУтверждение: вершины нашего нового многоугольника – концы невырожденных “освещённых” частей

– концы невырожденных “освещённых” частей


Слайд 15 Задача C
Телефонный номер

Задача CТелефонный номер

Слайд 16 Автор задачи – Михаил Дворкин
Условие – Евгений Курпилянский
Подготовка

Автор задачи – Михаил ДворкинУсловие – Евгений КурпилянскийПодготовка тестов – Евгений КурпилянскийРазбор – Павел Кунявский

тестов – Евгений Курпилянский
Разбор – Павел Кунявский


Слайд 17 Постановка задачи
Дан телефонный номер – последовательность чисел, разделенных

Постановка задачиДан телефонный номер – последовательность чисел, разделенных дефисамиНеобходимо найти все

дефисами
Необходимо найти все телефонные номера, которые произносятся также как

и данный

Слайд 18 Как решать?
Найдем последовательность слов, которые используются при произношении

Как решать?Найдем последовательность слов, которые используются при произношении данного номераЗаметим, что

данного номера
Заметим, что слова «тысяча» и «миллион» (в разных

формах) всегда употребляются вместе с предыдущим словом, поэтому форма этих слов не важна
Следовательно, каждое слово можно хранить как его числовое значение

Слайд 19 Как решать? (продолжение)
Нужно перебрать всевозможные расстановки дефисов между словами

Как решать? (продолжение)Нужно перебрать всевозможные расстановки дефисов между словами и вывести

и вывести все, которые являются корректными телефонными номерами
Для определения

корректности записи нужно понимать можно ли «склеить» несколько слов в одно число


Слайд 20 Обоснование
Количество слов в тестах меньше 100 (так как

ОбоснованиеКоличество слов в тестах меньше 100 (так как цифр не больше

цифр не больше 50)
Количество телефонных номеров в ответе не

больше 100000
Следовательно, перебор будет работать быстро с отсечением – не перебирать дальше, если следующую группу слов нельзя «склеить» в одно число

Слайд 21 Задача D
Гостиница

Задача DГостиница

Слайд 22 Автор задачи – Антон Банных
Условие – Антон Ахи
Подготовка

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

тестов – Антон Ахи
Разбор – Антон Ахи


Слайд 23 Постановка задачи
Дано число n
Надо его разложить на сумму

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

двоек и троек с минимальным числом слагаемых


Слайд 24 Как решать?
Понятно, что нам не имеет смысла иметь

Как решать?Понятно, что нам не имеет смысла иметь в сумме больше

в сумме больше двух двоек, так как 3 двойки

= 2 тройки
Если n ≡ 0 (mod 3), то ответ (n/3, 0)
Если n ≡ 1 (mod 3), то ответ ((n-4)/3, 2)
Если n ≡ 2 (mod 3), то ответ ((n-2)/3, 1)



Слайд 25 Задача E
Парад












Задача EПарад

Слайд 26 Автор задачи – Сергей Поромов
Условие – Сергей Мельников
Подготовка

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

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


Слайд 27 Постановка задачи
Есть последовательность из n чисел
Надо разбить их

Постановка задачиЕсть последовательность из n чиселНадо разбить их на убывающую и возрастающую подпоследовательности

на убывающую и возрастающую подпоследовательности


Слайд 28 Как решать?
Будем считать динамику less[i] и greater[i]
Разбиение чисел

Как решать?Будем считать динамику less[i] и greater[i]Разбиение чисел хорошее – разбиение

хорошее – разбиение чисел на возрастающую и убывающую подпоследовательности


Слайд 29 Как решать? (продолжение)
В какой последовательности находится i-ый элемент:
В убывающей,

Как решать? (продолжение)В какой последовательности находится i-ый элемент:В убывающей, less[i] равен

less[i] равен минимальному из последних элементов всех возрастающих последовательностей

во всех хороших разбиениях чисел с индексами от 1 до i-1

Слайд 30 Как решать? (продолжение)
В возрастающей, greater[i] равен максимуму из последних

Как решать? (продолжение)В возрастающей, greater[i] равен максимуму из последних элементов всех

элементов всех убывающих последовательностей во всех хороших разбиениях чисел

с индексами от 1 до i-1

Слайд 31 Пересчёт
Less[i]
if a[i+1]

ПересчётLess[i]if a[i+1]a[i] then greater[i+1]=          min(greater[i+1], greater[i])

a[i+1]>less[i] then greater[i+1]=a[i]
if a[i+1]>a[i] then greater[i+1]=

min(greater[i+1], greater[i])


Слайд 32 Как решать? (продолжение)
Если мы не смогли посчитать less[n] или

Как решать? (продолжение)Если мы не смогли посчитать less[n] или greater[n], то

greater[n], то ответ – Impossible
А иначе, нужно просто восстановить

ответ по этой динамике

Слайд 33 Задача F
Магазин


Задача FМагазин

Слайд 34 Автор задачи – Николай Ведерников
Условие – Николай Ведерников
Подготовка

Автор задачи – Николай ВедерниковУсловие – Николай ВедерниковПодготовка тестов – Николай ВедерниковРазбор – Николай Ведерников

тестов – Николай Ведерников
Разбор – Николай Ведерников


Слайд 35 Постановка задачи
Дано n стоимостей товаров и известно, что

Постановка задачиДано n стоимостей товаров и известно, что k-ый бесплатноНайти минимальное

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

купить все товары

Слайд 36 Как решать?
Отсортируем все цены в порядке убывания
Разобьём их

Как решать?Отсортируем все цены в порядке убыванияРазобьём их на группы по

на группы по k, начиная с первого, и из

каждой группы, может быть кроме последней, можно не платить за минимальный элемент (то есть не платить за элемент, номер которого делится на k)
Корректность такого алгоритма понять несложно

Слайд 37 Задача G
Занос

Задача GЗанос

Слайд 38 Автор задачи – Николай Ведерников
Условие – Виталий Аксёнов
Подготовка

Автор задачи – Николай ВедерниковУсловие – Виталий АксёновПодготовка тестов – Виталий АксёновРазбор – Николай Ведерников

тестов – Виталий Аксёнов
Разбор – Николай Ведерников


Слайд 39 Постановка задачи
Дано 5 чисел
Максимальная скорость автомобиля - v
Длина

Постановка задачиДано 5 чиселМаксимальная скорость автомобиля - vДлина первого отрезка трассы

первого отрезка трассы - x
Длина второго отрезка трассы -

y
Максимальное ускорение при разгоне - a
Максимальное ускорение при торможении - b
Найти минимальное время за которое можно преодолеть трассу при условии, что скорость между двумя отрезками равна 0

Слайд 40 Как решать?
Заметим, что ситуация с разгоном и ситуация

Как решать?Заметим, что ситуация с разгоном и ситуация с торможением совершенно

с торможением совершенно одинаковы, то есть при торможении мы

считаем, что едем в другую сторону и ускоряемся
Задача свелась к:
Максимальная скорость машины – v
Максимальное ускорение машины – a
Длина отрезка - x

Слайд 41 Как решать? (продолжение)
Понятно, что нам надо сразу разгоняться с

Как решать? (продолжение)Понятно, что нам надо сразу разгоняться с ускорением a

ускорением a до скорости v, а далее ехать с

постоянной скоростью
2 случая:
Успеваем разогнаться: , тогда ответ –

Не успеваем разогнаться: , тогда ответ –

Слайд 42 Задача H
Чай









Задача HЧай

Слайд 43 Автор задачи – Антон Ахи
Условие – Антон Ахи
Подготовка

Автор задачи – Антон АхиУсловие – Антон АхиПодготовка тестов – Антон АхиРазбор – Антон Ахи

тестов – Антон Ахи
Разбор – Антон Ахи


Слайд 44 Постановка задачи
Дан чайник объёма V и мощностью N,

Постановка задачиДан чайник объёма V и мощностью N, температура воды в

температура воды в чайнике опускается не ниже 20 градусов

и поднимается не выше 100, вода в чайнике остывает со скоростью k градусов в секунду
Дано m запросов, состоящих из двух чисел – время прихода члена жюри ti и объём его кружки ai , надо на каждый запрос вернуть время в секундах, когда член жюри начнёт пить чай

Слайд 45 Как решать?
Отсортируем членов жюри по временам прихода
И просто

Как решать?Отсортируем членов жюри по временам приходаИ просто нужно запросы жюри

нужно запросы жюри обрабатывать в таком порядке прямо как

написано в условии

Слайд 46 Подводные камни
Нужно не забывать, что минимальная температура воды

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

в чайнике – 20 градусов
Изначально чайник был пуст


Слайд 47 Задача I
Командная олимпиада

Задача IКомандная олимпиада

Слайд 48 Автор задачи – Юрий Петров
Условие – Никита Иоффе
Подготовка

Автор задачи – Юрий ПетровУсловие – Никита ИоффеПодготовка тестов – Никита ИоффеРазбор – Никита Иоффе

тестов – Никита Иоффе
Разбор – Никита Иоффе


Слайд 49 Постановка задачи
Дана перестановка чисел 1, 1, 2, 2,

Постановка задачиДана перестановка чисел 1, 1, 2, 2, …, n, nТребуется

…, n, n
Требуется найти такую перестановку, что минимальное расстояние

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

Слайд 50 Как решать?
Заметим, что нам подходят только перестановки, что

Как решать?Заметим, что нам подходят только перестановки, что расстояние между двумя

расстояние между двумя одинаковыми ровно n, то есть теперь

положение i в первой половине однозначно задаёт положение i во второй половине

Слайд 51 Как решать? (продолжение)
Построим полный двудольный граф и на ребре

Как решать? (продолжение)Построим полный двудольный граф и на ребре из i

из i в j напишем расстояние между положениями i

в изначальной перестановке и когда они будут стоять на позициях j и j+n
Осталось просто на этом графе найти минимальное взвешенное полное парасочетание

Слайд 52 Задача J
Поезда


Задача JПоезда

Слайд 53 Автор задачи – Виталий Аксёнов
Условие – Никита Иоффе
Подготовка

Автор задачи – Виталий АксёновУсловие – Никита ИоффеПодготовка тестов – Никита ИоффеРазбор – Павел Кунявский

тестов – Никита Иоффе
Разбор – Павел Кунявский


Слайд 54 Постановка задачи
Найти k-ую в лексикографическом порядке последовательность, которую

Постановка задачиНайти k-ую в лексикографическом порядке последовательность, которую можно отсортировать стеком

можно отсортировать стеком


Слайд 55 Как решать?
Заметим, что количество таких перестановок из n

Как решать?Заметим, что количество таких перестановок из n элементов равно числу

элементов равно числу Каталана, так как каждой такой перестановке

можно взаимнооднозначно сопоставить правильную скобочную последовательность длины 2n

Слайд 56 Как решать? (продолжение)
Если мы на первое место поставим число

Как решать? (продолжение)Если мы на первое место поставим число i, то

i, то последовательность выглядит следующим образом:
i(ХП[1..i-1])(ХП[i+1..n]), где ХП[a..b] –последовательность

из чисел от a до b, которая сортируется стеком
Таким образом количество ХП[1..n], где на первом месте стоит i равно Ci-1*Cn-i+1, где Ci – i-ое число Каталана

Слайд 57 Как решать? (продолжение)
Теперь просто решаем стандартную задачу о восстановлении

Как решать? (продолжение)Теперь просто решаем стандартную задачу о восстановлении k-ого комбинаторного

k-ого комбинаторного объекта, то есть ставим поочерёдно на первое

место числа от 1 до n и проверяем, а потом запускаемся рекурсивно от частей [1..i-1] и [1..n-i+1]



Слайд 58 Задача K
Королевская династия

Задача KКоролевская династия

Слайд 59 Автор задачи – Глеб Евстропов
Условие – Михаил Пядёркин
Подготовка

Автор задачи – Глеб ЕвстроповУсловие – Михаил ПядёркинПодготовка тестов – Михаил ПядёркинРазбор – Олег Давыдов

тестов – Михаил Пядёркин
Разбор – Олег Давыдов


Слайд 60 Постановка задачи
Дано подвешенное дерево из n вершин
Дано m

Постановка задачиДано подвешенное дерево из n вершинДано m запросов, состоящих из

запросов, состоящих из 2 чисел – v и k
Для

каждого запроса надо вывести количество потомков вершины v на расстоянии k

Слайд 61 Как решать?
Обойдём dfs-ом вершины, и отметим для каждой

Как решать? Обойдём dfs-ом вершины, и отметим для каждой времена входа

времена входа in[v] и выхода out[v], а также для

каждой высоты будем хранить набор вершин, которые находятся на этой высоте

Слайд 62 Как решать? (продолжение)
Обрабатываем запрос:
Пусть h[v] – высота вершины v
Рассмотрим

Как решать? (продолжение)Обрабатываем запрос:Пусть h[v] – высота вершины vРассмотрим набор вершин,

набор вершин, находящихся на высоте h[v]+k
Среди них нужно найти

количество таких, у которых времена входа от in[v] до out[v]
Бинарный поиск

  • Имя файла: vkoshp-2011-razbor-zadach.pptx
  • Количество просмотров: 203
  • Количество скачиваний: 0