🗊Презентация XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №1XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №2XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №3XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №4XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №5XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №6XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №7XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №8XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №9XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №10XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №11XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №12XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №13XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №14XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №15XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №16XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №17XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №18XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №19XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №20XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №21XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №22XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №23XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №24XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №25XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №26XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №27XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №28XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №29XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №30XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №31XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №32XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №33XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №34XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №35XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №36XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №37XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №38XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №39XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №40XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №41XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №42XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №43XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №44XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №45XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №46XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №47XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №48
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач. Доклад-сообщение содержит 48 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №1
Описание слайда:

Слайд 2


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №2
Описание слайда:

Слайд 3


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №3
Описание слайда:

Слайд 4


Постановка задачи Даны числа вида aa, bb и cc Вывести все различные перестановки этих чисел, соответствующие реальным датам
Описание слайда:
Постановка задачи Даны числа вида aa, bb и cc Вывести все различные перестановки этих чисел, соответствующие реальным датам

Слайд 5


Как решать? Всего существует 6 перестановок из aa, bb и cc Каждую перестановку проверяем на соответствие реальной дате Сохраняем все и выкидываем одинаковые
Описание слайда:
Как решать? Всего существует 6 перестановок из aa, bb и cc Каждую перестановку проверяем на соответствие реальной дате Сохраняем все и выкидываем одинаковые

Слайд 6


Подводные камни на самом деле перестановки не всегда бывают различными – 01/01/01 Если получилась дата вида dd/mm/00, значит, что дата соответствует 2100 -невисокосному году
Описание слайда:
Подводные камни на самом деле перестановки не всегда бывают различными – 01/01/01 Если получилась дата вида dd/mm/00, значит, что дата соответствует 2100 -невисокосному году

Слайд 7


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №7
Описание слайда:

Слайд 8


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №8
Описание слайда:

Слайд 9


Постановка задачи Есть n ростков бамбука, растущих m - 1 ночь, у которых заданы изначальная высота и скорость роста Можно подравнять ростки с i по j до величины T Надо сделать минимальное число стрижек, чтобы в день m высота всех ростков была h
Описание слайда:
Постановка задачи Есть n ростков бамбука, растущих m - 1 ночь, у которых заданы изначальная высота и скорость роста Можно подравнять ростки с i по j до величины T Надо сделать минимальное число стрижек, чтобы в день m высота всех ростков была h

Слайд 10


Как решать? Если все ростки в день m вырастают до величины h, то ответ 0 Если какой-то росток в день m в любом случае не может достичь величины h, то ответ -1 Во всех остальных случаях мы можем подстричь бамбук однажды – в последний день до высоты h, то есть ответ 1
Описание слайда:
Как решать? Если все ростки в день m вырастают до величины h, то ответ 0 Если какой-то росток в день m в любом случае не может достичь величины h, то ответ -1 Во всех остальных случаях мы можем подстричь бамбук однажды – в последний день до высоты h, то есть ответ 1

Слайд 11


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №11
Описание слайда:

Слайд 12


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №12
Описание слайда:

Слайд 13


Постановка задачи Дана последовательность цифр длины n Надо разбить её на 2 части так, чтобы первое число было не больше второго, и оба не начинались с нуля
Описание слайда:
Постановка задачи Дана последовательность цифр длины n Надо разбить её на 2 части так, чтобы первое число было не больше второго, и оба не начинались с нуля

Слайд 14


Как решать? Будем последовательно перебирать место разбиения последовательности Если длина второй части уже короче, чем длина первой, то это разбиение нам уже не подходит Если длины частей равны, то нужно просто сравнить 2 длинных числа Если вторая часть “длиннее” и не начинается с 0 – то это разбиение нам подходит
Описание слайда:
Как решать? Будем последовательно перебирать место разбиения последовательности Если длина второй части уже короче, чем длина первой, то это разбиение нам уже не подходит Если длины частей равны, то нужно просто сравнить 2 длинных числа Если вторая часть “длиннее” и не начинается с 0 – то это разбиение нам подходит

Слайд 15


Подводные камни Если длина строки 1, то ответ всегда 0 Если строка начинается с 0, то ответ всегда 0 Если второе число начинается на 0, то его считать не надо
Описание слайда:
Подводные камни Если длина строки 1, то ответ всегда 0 Если строка начинается с 0, то ответ всегда 0 Если второе число начинается на 0, то его считать не надо

Слайд 16


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №16
Описание слайда:

Слайд 17


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №17
Описание слайда:

Слайд 18


Постановка задачи Модификация задачи о Ханойской башне Изменение: со второго стержня мы можем переложить любое количество дисков сверху на какой-нибудь другой в том же порядке Надо найти минимальное количество действий для переноса с первого стержня на третий
Описание слайда:
Постановка задачи Модификация задачи о Ханойской башне Изменение: со второго стержня мы можем переложить любое количество дисков сверху на какой-нибудь другой в том же порядке Надо найти минимальное количество действий для переноса с первого стержня на третий

Слайд 19


Как решать? Будем считать динамику dp[from][to][k] – минимальное число действий нужно сделать, чтобы перенести со стержня from на стержень to ровно k дисков Если from = 2, то dp[from][to][k] = 1 Иначе, dp[from][to][k] = dp[from][mid][k - 1] + 1 + dp[mid][to][k - 1], где mid – не to, и не from
Описание слайда:
Как решать? Будем считать динамику dp[from][to][k] – минимальное число действий нужно сделать, чтобы перенести со стержня from на стержень to ровно k дисков Если from = 2, то dp[from][to][k] = 1 Иначе, dp[from][to][k] = dp[from][mid][k - 1] + 1 + dp[mid][to][k - 1], где mid – не to, и не from

Слайд 20


Приблизительное доказательство Нам обязательно надо n-1 диск перенести со стержня from, чтобы достать самый большой Стержень to перед переносом туда самого большого диска должен быть пустым
Описание слайда:
Приблизительное доказательство Нам обязательно надо n-1 диск перенести со стержня from, чтобы достать самый большой Стержень to перед переносом туда самого большого диска должен быть пустым

Слайд 21


Приблизительное доказательство (продолжение) Получается, что самый оптимальный способ перенести диски – перенести с from на mid ровно n-1 диск, перенести большой диск на стержень to, а потом опять перенести n-1 диск с mid на to
Описание слайда:
Приблизительное доказательство (продолжение) Получается, что самый оптимальный способ перенести диски – перенести с from на mid ровно n-1 диск, перенести большой диск на стержень to, а потом опять перенести n-1 диск с mid на to

Слайд 22


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №22
Описание слайда:

Слайд 23


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №23
Описание слайда:

Слайд 24


Постановка задачи Есть набор картриджей с параметрами: стоимость и количество страниц, которое может напечатать Найти минимальную сумму, которую нужно заплатить, чтобы мы могли распечатать ровно k страниц
Описание слайда:
Постановка задачи Есть набор картриджей с параметрами: стоимость и количество страниц, которое может напечатать Найти минимальную сумму, которую нужно заплатить, чтобы мы могли распечатать ровно k страниц

Слайд 25


Как решать? Нам имеет смысл рассматривать не более 200 картриджей Картридж, у которого отношение стоимости к количеству напечатанных страниц максимально, имеет номер opt Картридж с максимальным количеством страниц имеет номер max
Описание слайда:
Как решать? Нам имеет смысл рассматривать не более 200 картриджей Картридж, у которого отношение стоимости к количеству напечатанных страниц максимально, имеет номер opt Картридж с максимальным количеством страниц имеет номер max

Слайд 26


Как решать? (продолжение) Выгодно брать картридж opt, до тех пор когда количество страниц не станет меньше pmax*popt А для количества страниц до pmax*popt решим стандартную задачу о рюкзаке
Описание слайда:
Как решать? (продолжение) Выгодно брать картридж opt, до тех пор когда количество страниц не станет меньше pmax*popt А для количества страниц до pmax*popt решим стандартную задачу о рюкзаке

Слайд 27


Обоснование Имеет смысл считать только до pmax*popt , так как мы можем получить почти все остатки от деления на popt, не превышая pmax*popt. А, значит, этого хватает, чтобы понять, что алгоритм находит самое оптимальное решение.
Описание слайда:
Обоснование Имеет смысл считать только до pmax*popt , так как мы можем получить почти все остатки от деления на popt, не превышая pmax*popt. А, значит, этого хватает, чтобы понять, что алгоритм находит самое оптимальное решение.

Слайд 28


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №28
Описание слайда:

Слайд 29


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №29
Описание слайда:

Слайд 30


Постановка задачи Дано квадродерево на таблице из 0 и 1 Найти минимальное число вершин, которое может остаться, при изменении не более, чем k ячеек
Описание слайда:
Постановка задачи Дано квадродерево на таблице из 0 и 1 Найти минимальное число вершин, которое может остаться, при изменении не более, чем k ячеек

Слайд 31


Как решать? Посчитаем динамику на полном квадродереве, то есть в каждой вершине посчитаем - какое минимальное количество ячеек нужно изменить, чтобы в квадродереве с корнем в этой вершине было ровно m вершин
Описание слайда:
Как решать? Посчитаем динамику на полном квадродереве, то есть в каждой вершине посчитаем - какое минимальное количество ячеек нужно изменить, чтобы в квадродереве с корнем в этой вершине было ровно m вершин

Слайд 32


Обоснование Если таблица имеет размер n*n – то количество вершин в квадродереве O(n2) Каждая такая вершина “пересчитывается” за O(n4) T(n) = O(n4) + 4T(n/4) = O(n4) Итого: O(n4) – время работы программы
Описание слайда:
Обоснование Если таблица имеет размер n*n – то количество вершин в квадродереве O(n2) Каждая такая вершина “пересчитывается” за O(n4) T(n) = O(n4) + 4T(n/4) = O(n4) Итого: O(n4) – время работы программы

Слайд 33


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №33
Описание слайда:

Слайд 34


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №34
Описание слайда:

Слайд 35


Постановка задачи Дано k чисел Построить такое двоичное дерево, что числа, записанные в детях, меньше, чем число, записанное в вершине, не менее, чем на k
Описание слайда:
Постановка задачи Дано k чисел Построить такое двоичное дерево, что числа, записанные в детях, меньше, чем число, записанное в вершине, не менее, чем на k

Слайд 36


Как решать? Отсортируем числа в порядке убывания У вершины с индексом v – предком будет вершина с индексом [n/2] Не очень трудно убедиться, что если не выполняются условия задачи для этого ответа, то ответ равен -1
Описание слайда:
Как решать? Отсортируем числа в порядке убывания У вершины с индексом v – предком будет вершина с индексом [n/2] Не очень трудно убедиться, что если не выполняются условия задачи для этого ответа, то ответ равен -1

Слайд 37


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №37
Описание слайда:

Слайд 38


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №38
Описание слайда:

Слайд 39


Постановка задачи Даны 2 односторонние дороги, по которым машины едут к центру У машин есть 3 параметра: дорога, по которой едут, положение в начальный момент времени, скорость Надо найти такое разбиение периода светофора, чтобы максимальное число машин, которые одновременно стоят на перекрёстке, было минимально
Описание слайда:
Постановка задачи Даны 2 односторонние дороги, по которым машины едут к центру У машин есть 3 параметра: дорога, по которой едут, положение в начальный момент времени, скорость Надо найти такое разбиение периода светофора, чтобы максимальное число машин, которые одновременно стоят на перекрёстке, было минимально

Слайд 40


Как решать? Для каждой машины надо найти время, когда она доедет до перекрёстка Это время равно максимуму из её времени “без торможения” и из времен приезда машин, которые находятся ближе к перекрёстку
Описание слайда:
Как решать? Для каждой машины надо найти время, когда она доедет до перекрёстка Это время равно максимуму из её времени “без торможения” и из времен приезда машин, которые находятся ближе к перекрёстку

Слайд 41


Как решать? (продолжение) “Нужные отрезки” – (k(r+g)+g, (k+1)(r+g)) для первой и (k(r+g), k(r+g)+g) для второй прямой “Разобьём” время на блоки по x Нам нужно найти такое g, что максимум из количества машин на “нужных” отрезках была минимальной Каждая машина принадлежит какому-то блоку
Описание слайда:
Как решать? (продолжение) “Нужные отрезки” – (k(r+g)+g, (k+1)(r+g)) для первой и (k(r+g), k(r+g)+g) для второй прямой “Разобьём” время на блоки по x Нам нужно найти такое g, что максимум из количества машин на “нужных” отрезках была минимальной Каждая машина принадлежит какому-то блоку

Слайд 42


Как решать? (продолжение) Возьмём все времена по модулю x и отсортируем, а далее воспользуемся методом сканирующей прямой Изначально, g = 0 2 события: Машина с первой прямой успевает на зелёный Машина со второй прямой теперь не успевает на зелёный
Описание слайда:
Как решать? (продолжение) Возьмём все времена по модулю x и отсортируем, а далее воспользуемся методом сканирующей прямой Изначально, g = 0 2 события: Машина с первой прямой успевает на зелёный Машина со второй прямой теперь не успевает на зелёный

Слайд 43


Как решать? (продолжение) Для каждой машины мы знаем блок, которому она принадлежит При использовании сканирующей количество машин в блоках мы можем поддерживать с помощью дерева отрезков
Описание слайда:
Как решать? (продолжение) Для каждой машины мы знаем блок, которому она принадлежит При использовании сканирующей количество машин в блоках мы можем поддерживать с помощью дерева отрезков

Слайд 44


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №44
Описание слайда:

Слайд 45


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №45
Описание слайда:

Слайд 46


Постановка задачи Разбить числа от 1 до n на 3 группы, суммы чисел в которых равны
Описание слайда:
Постановка задачи Разбить числа от 1 до n на 3 группы, суммы чисел в которых равны

Слайд 47


Как решать? n <= 4 и n 1 (mod 3) – разбить на кучи нельзя Если мы умеем разбивать n, то умеем и n + 6 n = 5 – {{5}, {1, 4}, {2, 3}} n = 6 – {{1, 6}, {2, 5}, {3, 4}} n = 8 – {{4, 8}, {5, 7}, {1, 2, 3, 6}} n = 9 – {{7, 8}, {6, 9}, {1, 2, 3, 4, 5}}
Описание слайда:
Как решать? n <= 4 и n 1 (mod 3) – разбить на кучи нельзя Если мы умеем разбивать n, то умеем и n + 6 n = 5 – {{5}, {1, 4}, {2, 3}} n = 6 – {{1, 6}, {2, 5}, {3, 4}} n = 8 – {{4, 8}, {5, 7}, {1, 2, 3, 6}} n = 9 – {{7, 8}, {6, 9}, {1, 2, 3, 4, 5}}

Слайд 48


XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач, слайд №48
Описание слайда:

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию