Презентация XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач абсолютно бесплатно. Урок-презентация на эту тему содержит всего 48 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:48 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.37 MB
- Просмотров:107
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда:
№2 слайд
Содержание слайда:
№3 слайд
Содержание слайда:
№4 слайд
Содержание слайда: Постановка задачи
Даны числа вида aa, bb и cc
Вывести все различные перестановки этих чисел, соответствующие реальным датам
№5 слайд
Содержание слайда: Как решать?
Всего существует 6 перестановок из aa, bb и cc
Каждую перестановку проверяем на соответствие реальной дате
Сохраняем все и выкидываем одинаковые
№6 слайд
Содержание слайда: Подводные камни
на самом деле перестановки не всегда бывают различными – 01/01/01
Если получилась дата вида dd/mm/00, значит, что дата соответствует 2100 -невисокосному году
№7 слайд
Содержание слайда:
№8 слайд
Содержание слайда:
№9 слайд
Содержание слайда: Постановка задачи
Есть n ростков бамбука, растущих m - 1 ночь, у которых заданы изначальная высота и скорость роста
Можно подравнять ростки с i по j до величины T
Надо сделать минимальное число стрижек, чтобы в день m высота всех ростков была h
№10 слайд
Содержание слайда: Как решать?
Если все ростки в день m вырастают до величины h, то ответ 0
Если какой-то росток в день m в любом случае не может достичь величины h, то ответ -1
Во всех остальных случаях мы можем подстричь бамбук однажды – в последний день до высоты h, то есть ответ 1
№11 слайд
Содержание слайда:
№12 слайд
Содержание слайда:
№13 слайд
Содержание слайда: Постановка задачи
Дана последовательность цифр
длины n
Надо разбить её на 2 части так, чтобы первое число было не больше второго, и оба не начинались с нуля
№14 слайд
Содержание слайда: Как решать?
Будем последовательно перебирать место разбиения последовательности
Если длина второй части уже короче, чем длина первой, то это разбиение нам уже не подходит
Если длины частей равны, то нужно просто сравнить 2 длинных числа
Если вторая часть “длиннее” и не начинается с 0 – то это разбиение нам подходит
№15 слайд
Содержание слайда: Подводные камни
Если длина строки 1, то ответ всегда 0
Если строка начинается с 0, то ответ всегда 0
Если второе число начинается на 0, то его считать не надо
№16 слайд
Содержание слайда:
№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
№20 слайд
Содержание слайда: Приблизительное доказательство
Нам обязательно надо n-1 диск перенести со стержня from, чтобы достать самый большой
Стержень to перед переносом туда самого большого диска должен быть пустым
№21 слайд
Содержание слайда: Приблизительное доказательство
(продолжение)
Получается, что самый оптимальный способ перенести диски – перенести с from на mid ровно n-1 диск, перенести большой диск на стержень to, а потом опять перенести n-1 диск с mid на to
№22 слайд
Содержание слайда:
№23 слайд
Содержание слайда:
№24 слайд
Содержание слайда: Постановка задачи
Есть набор картриджей с параметрами: стоимость и количество страниц, которое может напечатать
Найти минимальную сумму, которую нужно заплатить, чтобы мы могли распечатать ровно k страниц
№25 слайд
Содержание слайда: Как решать?
Нам имеет смысл рассматривать не более 200 картриджей
Картридж, у которого отношение стоимости к количеству напечатанных страниц максимально, имеет номер opt
Картридж с максимальным количеством страниц имеет номер max
№26 слайд
Содержание слайда: Как решать?
(продолжение)
Выгодно брать картридж opt, до тех пор когда количество страниц не станет меньше pmax*popt
А для количества страниц до pmax*popt решим стандартную задачу о рюкзаке
№27 слайд
Содержание слайда: Обоснование
Имеет смысл считать только до pmax*popt , так как мы можем получить почти все остатки от деления на popt, не превышая pmax*popt. А, значит, этого хватает, чтобы понять, что алгоритм находит самое оптимальное решение.
№28 слайд
Содержание слайда:
№29 слайд
Содержание слайда:
№30 слайд
Содержание слайда: Постановка задачи
Дано квадродерево на таблице из 0 и 1
Найти минимальное число вершин, которое может остаться, при изменении не более, чем k ячеек
№31 слайд
Содержание слайда: Как решать?
Посчитаем динамику на полном квадродереве, то есть в каждой вершине посчитаем - какое минимальное количество ячеек нужно изменить, чтобы в квадродереве с корнем в этой вершине было ровно m вершин
№32 слайд
Содержание слайда: Обоснование
Если таблица имеет размер n*n – то количество вершин в квадродереве O(n2)
Каждая такая вершина “пересчитывается” за O(n4)
T(n) = O(n4) + 4T(n/4) = O(n4)
Итого: O(n4) – время работы программы
№33 слайд
Содержание слайда:
№34 слайд
Содержание слайда:
№35 слайд
Содержание слайда: Постановка задачи
Дано k чисел
Построить такое двоичное дерево, что числа, записанные в детях, меньше, чем число, записанное в вершине, не менее, чем на k
№36 слайд
Содержание слайда: Как решать?
Отсортируем числа в порядке убывания
У вершины с индексом v – предком будет вершина с индексом [n/2]
Не очень трудно убедиться, что если не выполняются условия задачи для этого ответа, то ответ равен -1
№37 слайд
Содержание слайда:
№38 слайд
Содержание слайда:
№39 слайд
Содержание слайда: Постановка задачи
Даны 2 односторонние дороги, по которым машины едут к центру
У машин есть 3 параметра: дорога, по которой едут, положение в начальный момент времени, скорость
Надо найти такое разбиение периода светофора, чтобы максимальное число машин, которые одновременно стоят на перекрёстке, было минимально
№40 слайд
Содержание слайда: Как решать?
Для каждой машины надо найти время, когда она доедет до перекрёстка
Это время равно максимуму из её времени “без торможения” и из времен приезда машин, которые находятся ближе к перекрёстку
№41 слайд
Содержание слайда: Как решать?
(продолжение)
“Нужные отрезки” – (k(r+g)+g, (k+1)(r+g)) для первой и (k(r+g), k(r+g)+g) для второй прямой
“Разобьём” время на блоки по x
Нам нужно найти такое g, что максимум из количества машин на “нужных” отрезках была минимальной
Каждая машина принадлежит какому-то блоку
№42 слайд
Содержание слайда: Как решать?
(продолжение)
Возьмём все времена по модулю x и отсортируем, а далее воспользуемся методом сканирующей прямой
Изначально, g = 0
2 события:
Машина с первой прямой успевает на зелёный
Машина со второй прямой теперь не успевает на зелёный
№43 слайд
Содержание слайда: Как решать?
(продолжение)
Для каждой машины мы знаем блок, которому она принадлежит
При использовании сканирующей количество машин в блоках мы можем поддерживать с помощью дерева отрезков
№44 слайд
Содержание слайда:
№45 слайд
Содержание слайда:
№46 слайд
Содержание слайда: Постановка задачи
Разбить числа от 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}}
№48 слайд
Содержание слайда:
Скачать все slide презентации XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач одним архивом:
