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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

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

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

Слайд 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

Описание слайда:

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