октября 2011 года
Санкт-Петербург
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач презентация
Содержание
- 1. XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию. Разбор задач
- 2. Задача A Летопись
- 3. Автор задачи – Виталий Аксёнов Условие –
- 4. Постановка задачи Даны числа вида aa, bb
- 5. Как решать? Всего существует 6 перестановок из
- 6. Подводные камни на самом деле перестановки не
- 7. Задача B Икебана
- 8. Автор задачи – Алексей Цыпленков Условие –
- 9. Постановка задачи Есть n ростков бамбука, растущих
- 10. Как решать? Если все ростки в день
- 11. Задача C Номер страницы
- 12. Автор задачи – Михаил Дворкин Условие –
- 13. Постановка задачи Дана последовательность цифр длины n
- 14. Как решать? Будем последовательно перебирать место разбиения
- 15. Подводные камни Если длина строки 1, то
- 16. Задача D Пизанская башня
- 17. Автор задачи – Андрей Станкевич Условие –
- 18. Постановка задачи Модификация задачи о Ханойской башне
- 19. Как решать? Будем считать динамику dp[from][to][k] –
- 20. Приблизительное доказательство Нам обязательно надо n-1 диск
- 21. Приблизительное доказательство (продолжение) Получается, что самый оптимальный
- 22. Задача E Печать
- 23. Автор задачи – Георгий Корнеев Условие –
- 24. Постановка задачи Есть набор картриджей с параметрами:
- 25. Как решать? Нам имеет смысл рассматривать не
- 26. Как решать? (продолжение) Выгодно брать картридж opt,
- 27. Обоснование Имеет смысл считать только до pmax*popt
- 28. Задача F Квадродерево
- 29. Автор задачи – Павел Кротков, Михаил Дворкин
- 30. Постановка задачи Дано квадродерево на таблице из
- 31. Как решать? Посчитаем динамику на полном квадродереве,
- 32. Обоснование Если таблица имеет размер n*n –
- 33. Задача G Шпаги
- 34. Автор задачи – Юрий Петров Условие –
- 35. Постановка задачи Дано k чисел Построить такое
- 36. Как решать? Отсортируем числа в порядке убывания
- 37. Задача H Светофор
- 38. Автор задачи – Виталий Аксёнов Условие –
- 39. Постановка задачи Даны 2 односторонние дороги, по
- 40. Как решать? Для каждой машины надо найти
- 41. Как решать? (продолжение) “Нужные отрезки” – (k(r+g)+g,
- 42. Как решать? (продолжение) Возьмём все времена по
- 43. Как решать? (продолжение) Для каждой машины мы
- 44. Задача I Гири
- 45. Автор задачи – Михаил Дворкин Условие –
- 46. Постановка задачи Разбить числа от 1 до
- 47. Как решать? n
- 48. Спасибо за внимание! Вопросы? http://neerc.ifmo.ru/school
Задача A Летопись
Слайд 1XVIII Командная олимпиада школьников Санкт-Петербурга по информатике и программированию
Разбор задач
30
Слайд 3Автор задачи – Виталий Аксёнов
Условие – Алексей Цыпленков
Подготовка тестов – Демид
Кучеренко
Разбор – Алексей Цыпленков
Разбор – Алексей Цыпленков
Слайд 4Постановка задачи
Даны числа вида aa, bb и cc
Вывести все различные перестановки
этих чисел, соответствующие реальным датам
Слайд 5Как решать?
Всего существует 6 перестановок из aa, bb и cc
Каждую перестановку
проверяем на соответствие реальной дате
Сохраняем все и выкидываем одинаковые
Сохраняем все и выкидываем одинаковые
Слайд 6Подводные камни
на самом деле перестановки не всегда бывают различными – 01/01/01
Если
получилась дата вида dd/mm/00, значит, что дата соответствует 2100 -невисокосному году
Слайд 8Автор задачи – Алексей Цыпленков
Условие – Алексей Цыпленков
Подготовка тестов – Павел
Кунявский
Разбор – Павел Кунявский
Разбор – Павел Кунявский
Слайд 9Постановка задачи
Есть n ростков бамбука, растущих m - 1 ночь, у
которых заданы изначальная высота и скорость роста
Можно подравнять ростки с i по j до величины T
Надо сделать минимальное число стрижек, чтобы в день m высота всех ростков была h
Можно подравнять ростки с i по j до величины T
Надо сделать минимальное число стрижек, чтобы в день m высота всех ростков была h
Слайд 10Как решать?
Если все ростки в день m вырастают до величины h,
то ответ 0
Если какой-то росток в день m в любом случае не может достичь величины h, то ответ -1
Во всех остальных случаях мы можем подстричь бамбук однажды – в последний день до высоты h, то есть ответ 1
Если какой-то росток в день m в любом случае не может достичь величины h, то ответ -1
Во всех остальных случаях мы можем подстричь бамбук однажды – в последний день до высоты h, то есть ответ 1
Слайд 12Автор задачи – Михаил Дворкин
Условие – Ульяна Зотова
Подготовка тестов – Андрей
Комаров
Разбор – Олег Давыдов
Разбор – Олег Давыдов
Слайд 13Постановка задачи
Дана последовательность цифр
длины n
Надо разбить её на 2 части так,
чтобы первое число было не больше второго, и оба не начинались с нуля
Слайд 14Как решать?
Будем последовательно перебирать место разбиения последовательности
Если длина второй части
уже короче, чем длина первой, то это разбиение нам уже не подходит
Если длины частей равны, то нужно просто сравнить 2 длинных числа
Если вторая часть “длиннее” и не начинается с 0 – то это разбиение нам подходит
Если длины частей равны, то нужно просто сравнить 2 длинных числа
Если вторая часть “длиннее” и не начинается с 0 – то это разбиение нам подходит
Слайд 15Подводные камни
Если длина строки 1, то ответ всегда 0
Если строка начинается
с 0, то ответ всегда 0
Если второе число начинается на 0, то его считать не надо
Если второе число начинается на 0, то его считать не надо
Слайд 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
Если 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 перед переносом туда самого большого диска должен быть пустым
Стержень to перед переносом туда самого большого диска должен быть пустым
Слайд 21Приблизительное доказательство
(продолжение)
Получается, что самый оптимальный способ перенести диски – перенести с
from на mid ровно n-1 диск, перенести большой диск на стержень to, а потом опять перенести n-1 диск с mid на to
Слайд 23Автор задачи – Георгий Корнеев
Условие – Алина Дубатовка
Подготовка тестов – Аксёнов
Виталий
Разбор –Аксёнов Виталий
Разбор –Аксёнов Виталий
Слайд 24Постановка задачи
Есть набор картриджей с параметрами: стоимость и количество страниц, которое
может напечатать
Найти минимальную сумму, которую нужно заплатить, чтобы мы могли распечатать ровно k страниц
Найти минимальную сумму, которую нужно заплатить, чтобы мы могли распечатать ровно k страниц
Слайд 25Как решать?
Нам имеет смысл рассматривать не более 200 картриджей
Картридж, у которого
отношение стоимости к количеству напечатанных страниц максимально, имеет номер opt
Картридж с максимальным количеством страниц имеет номер max
Картридж с максимальным количеством страниц имеет номер max
Слайд 26Как решать?
(продолжение)
Выгодно брать картридж opt, до тех пор когда количество страниц
не станет меньше pmax*popt
А для количества страниц до pmax*popt решим стандартную задачу о рюкзаке
А для количества страниц до pmax*popt решим стандартную задачу о рюкзаке
Слайд 27Обоснование
Имеет смысл считать только до pmax*popt , так как мы можем
получить почти все остатки от деления на popt, не превышая pmax*popt. А, значит, этого хватает, чтобы понять, что алгоритм находит самое оптимальное решение.
Слайд 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) – время работы программы
Каждая такая вершина “пересчитывается” за O(n4)
T(n) = O(n4) + 4T(n/4) = O(n4)
Итого: O(n4) – время работы программы
Слайд 34Автор задачи – Юрий Петров
Условие – Алина Дубатовка, Андрей Станкевич
Подготовка тестов
– Павел Кротков
Разбор – Павел Кротков
Разбор – Павел Кротков
Слайд 35Постановка задачи
Дано k чисел
Построить такое двоичное дерево, что числа, записанные в
детях, меньше, чем число, записанное в вершине, не менее, чем на k
Слайд 36Как решать?
Отсортируем числа в порядке убывания
У вершины с индексом v –
предком будет вершина с индексом [n/2]
Не очень трудно убедиться, что если не выполняются условия задачи для этого ответа, то ответ равен -1
Не очень трудно убедиться, что если не выполняются условия задачи для этого ответа, то ответ равен -1
Слайд 38Автор задачи – Виталий Аксёнов
Условие – Андрей Комаров
Подготовка тестов – Павел
Кунявский
Разбор – Павел Кунявский
Разбор – Павел Кунявский
Слайд 39Постановка задачи
Даны 2 односторонние дороги, по которым машины едут к центру
У
машин есть 3 параметра: дорога, по которой едут, положение в начальный момент времени, скорость
Надо найти такое разбиение периода светофора, чтобы максимальное число машин, которые одновременно стоят на перекрёстке, было минимально
Надо найти такое разбиение периода светофора, чтобы максимальное число машин, которые одновременно стоят на перекрёстке, было минимально
Слайд 40Как решать?
Для каждой машины надо найти время, когда она доедет до
перекрёстка
Это время равно максимуму из её времени “без торможения” и из времен приезда машин, которые находятся ближе к перекрёстку
Это время равно максимуму из её времени “без торможения” и из времен приезда машин, которые находятся ближе к перекрёстку
Слайд 41Как решать?
(продолжение)
“Нужные отрезки” – (k(r+g)+g, (k+1)(r+g)) для первой и (k(r+g), k(r+g)+g)
для второй прямой
“Разобьём” время на блоки по x
Нам нужно найти такое g, что максимум из количества машин на “нужных” отрезках была минимальной
Каждая машина принадлежит какому-то блоку
“Разобьём” время на блоки по x
Нам нужно найти такое g, что максимум из количества машин на “нужных” отрезках была минимальной
Каждая машина принадлежит какому-то блоку
Слайд 42Как решать?
(продолжение)
Возьмём все времена по модулю x и отсортируем, а далее
воспользуемся методом сканирующей прямой
Изначально, g = 0
2 события:
Машина с первой прямой успевает на зелёный
Машина со второй прямой теперь не успевает на зелёный
Изначально, g = 0
2 события:
Машина с первой прямой успевает на зелёный
Машина со второй прямой теперь не успевает на зелёный
Слайд 43Как решать?
(продолжение)
Для каждой машины мы знаем блок, которому она принадлежит
При использовании
сканирующей количество машин в блоках мы можем поддерживать с помощью дерева отрезков
Слайд 45Автор задачи – Михаил Дворкин
Условие – Ульяна Зотова
Подготовка тестов – Андрей
Комаров
Разбор – Павел Кротков
Разбор – Павел Кротков
Слайд 47Как решать?
n
на кучи нельзя
Если мы умеем разбивать 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, то умеем и 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}}
_
_
_
