- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Девятая Всероссийская командная олимпиада школьников по программированию презентация
Содержание
- 1. Девятая Всероссийская командная олимпиада школьников по программированию
- 2. A. Место у прохода, пожалуйста Автор задачи
- 3. Обозначения n – количество кресел l –
- 4. Расположение кресел по длине Максимальное количество кресел
- 5. Расположение кресел по ширине Необходимое количество рядов
- 6. Ответ на задачу Расположение проходов после нечетных
- 7. B. Мост Автор задачи – Андрей Станкевич
- 8. Река Берега реки – ломаные, бесконечные в
- 9. Мост Если ответ – L, то всегда
- 10. Расстояние от точки до отрезка Найдем расстояние
- 11. C. Почти беспрефиксные коды Автор задачи –
- 12. Определение Почти беспрефиксный код уровня k –
- 13. Решение с сортировкой Отсортируем все строки в
- 14. Решение бором Добавим все слова в бор
- 15. Пример бора Для строк: aaa, aab, ac, ba, bb, ca
- 16. Решение хешами Вычислим значения хеш-функции для префиксов
- 17. D. Обход в глубину Автор задачи –
- 18. Исходный код Если функция dfs вызвана для
- 19. Будем называть: Непосещенные вершины – белыми Полностью
- 20. Если мы в вершине v: В черные
- 21. E. Драгоценные камни Автор задачи – Федор
- 22. Какие пары считать? Строка S Определены упорядоченные
- 23. Как решать? Представим пары таблицей логического типа
- 24. F. Интересные числа Автор задачи – Федор
- 25. Какие числа интересны? Число x является интересным,
- 26. Легко найти Количество интересных чисел, не превышающих некоторое число y Принцип включения-исключения
- 27. Двоичный поиск Необходимо найти минимальное y, что
- 28. Альтернативный подход Строим число, подбирая цифры со
- 29. Альтернативный подход Определим длину искомого числа Количество
- 30. G. Оптимизация Автор задачи – Сергей Копелиович
- 31. Обозначения M – число частей проекта mi
- 32. Критерий оптимизирующей операции Каждую операцию можно задать
- 33. Сведение к задаче о количестве инверсий в
- 34. H. Шкафы Автор задачи – Владимир Гуровиц
- 35. Динамическое программирование f(h) – максимальное число полок,
- 36. Жадный алгоритм Из двух самых нижних полок
- 37. I. Архимедова спираль Автор задачи – Владимир
- 38. Уравнения движения α(t) = ω∙t ρ(t) =
- 39. Преобразование уравнений Несложными преобразованиями задача сводится к
- 40. График f(t) при a=2
- 41. Варианты решения Для поиска максимума выпуклой функции
- 42. Варианты решения Перебрать все t из диапазона
- 43. Тернарный поиск Задача: Дана функция f(t), выпуклая
- 44. Тернарный поиск Возможны два случая: f(x1) ≤
- 45. Тернарный поиск: Код while (a + ε
- 46. J. Сумма Автор задачи – Роман Сатюков
- 47. Представим числа A, B и C в
- 48. Найдем натуральные x, y и z, такие что: Тогда исходная задача имеет решение:
- 49. Случай когда A,B,C не делятся на 10
- 50. Случай n=m=0: Получается уравнение A+B=C·10k. Поскольку числа
- 51. Спасибо за внимание! Вопросы?
A. Место у прохода, пожалуйста Автор задачи – Андрей Станкевич Условие – Андрей Станкевич Подготовка тестов – Владимир Ульянцев Разбор – Владимир Ульянцев
Слайд 1Девятая Всероссийская командная олимпиада школьников по программированию
Разбор задач
23 ноября 2008 года
Санкт-Петербург
Слайд 2A. Место у прохода, пожалуйста
Автор задачи – Андрей Станкевич
Условие – Андрей
Станкевич
Подготовка тестов – Владимир Ульянцев
Разбор – Владимир Ульянцев
Подготовка тестов – Владимир Ульянцев
Разбор – Владимир Ульянцев
Слайд 3Обозначения
n – количество кресел
l – длина салона
w – ширина салона
x –
длина кресла
y – ширина кресла
a – ширина прохода
y – ширина кресла
a – ширина прохода
Слайд 4Расположение кресел по длине
Максимальное количество кресел в ряду rowSize = l
/ x
Случай rowSize = 0
Случай rowSize = 0
Слайд 5Расположение кресел по ширине
Необходимое количество рядов
rows = (n + rowSize
- 1) / rowSize
Допустимое количество проходов
aisles = (w - rows * y) / a
Условие на количество проходов
Допустимое количество проходов
aisles = (w - rows * y) / a
Условие на количество проходов
Слайд 6Ответ на задачу
Расположение проходов после нечетных рядов
2 * aisles * rowSize
– максимальное количество кресел, которое можно поставить у прохода
Ответ - min(n, 2 * aisles * rowSize)
Ответ - min(n, 2 * aisles * rowSize)
Слайд 7B. Мост
Автор задачи – Андрей Станкевич
Условие – Андрей Станкевич
Подготовка тестов –
Антон Феськов
Разбор – Антон Феськов
Разбор – Антон Феськов
Слайд 8Река
Берега реки – ломаные, бесконечные в обе стороны
Требуется построить мост через
реку минимальной длины
Слайд 9Мост
Если ответ – L, то всегда существует мост длины L, построенный
через вершину ломаной, образующей один из берегов реки
Достаточно для каждой вершины каждой ломаной проверить расстояние до каждого отрезка и луча второй ломаной
Достаточно для каждой вершины каждой ломаной проверить расстояние до каждого отрезка и луча второй ломаной
Слайд 10Расстояние от точки до отрезка
Найдем расстояние от точки C до отрезка
AB
Если
Иначе это min(a, b)
Если
Иначе это min(a, b)
то расстояние до отрезка есть расстояние до прямой, содержащей этот отрезок
Слайд 11C. Почти беспрефиксные коды
Автор задачи – Антон Феськов
Условие – Андрей Станкевич
Подготовка
тестов – Сергей Поромов
Разбор – Сергей Поромов
Разбор – Сергей Поромов
Слайд 12Определение
Почти беспрефиксный код уровня k – набор слов, у которых наибольший
общий префикс имеет длину не более k
Слайд 13Решение с сортировкой
Отсортируем все строки в лексикографическом порядке
Будем добавлять в искомый
набор слово, если его общий префикс с предыдущим не превышает по длине k
Слайд 14Решение бором
Добавим все слова в бор
Будем выводить всевозможными способами префиксы длины
(k+1), далее только одно их продолжение
Требует много памяти
Требует много памяти
Слайд 16Решение хешами
Вычислим значения хеш-функции для префиксов длины (k+1) всех строк
Отсортируем
значения хеш-функции
Для каждого значения хеш-функции выведем одного представителя
Для каждого значения хеш-функции выведем одного представителя
Слайд 17D. Обход в глубину
Автор задачи – Елена Андреева, Виктор Матюхин
Условие –
Андрей Станкевич
Подготовка тестов – Олег Давыдов
Разбор – Антон Феськов
Подготовка тестов – Олег Давыдов
Разбор – Антон Феськов
Слайд 18Исходный код
Если функция dfs вызвана для вершины u, то среди программа
находит минимальную по номеру непосещенную вершину v, такую что в графе есть ребро (u, v) и вызывает dfs(v)
Слайд 19Будем называть:
Непосещенные вершины – белыми
Полностью обработанные вершины – черными
Те вершины, которые
находятся в стеке вызовов (остальные) – серыми
Слайд 20Если мы в вершине v:
В черные вершины нет дополнительных ребер
Ребро (u,
v) можно добавить только если w < v
Рассмотрены все пары вершин
Рассмотрены все пары вершин
Слайд 21E. Драгоценные камни
Автор задачи – Федор Царев
Условие – Федор Царев
Подготовка тестов
– Антон Феськов
Разбор – Антон Феськов
Разбор – Антон Феськов
Слайд 22Какие пары считать?
Строка S
Определены упорядоченные пары типов камней: (a1, b1), (a2,
b2), . . . , (ak, bk)
Найти количество пар индексов (i, j) таких что 1 ≤ i < j ≤ n и существует такое число q (1 ≤ q ≤ k), что Si = aq и Sj = bq
Найти количество пар индексов (i, j) таких что 1 ≤ i < j ≤ n и существует такое число q (1 ≤ q ≤ k), что Si = aq и Sj = bq
Слайд 23Как решать?
Представим пары таблицей логического типа M[a,b] = true если пара
(a, b) красивая и false иначе
Прибавляем по символу в конец текущей строки. Храним количество символов каждого типа в текущей строке (cnt[c])
Пересчет: для j-го символа:
Прибавляем по символу в конец текущей строки. Храним количество символов каждого типа в текущей строке (cnt[c])
Пересчет: для j-го символа:
for c = ‘a’ .. ‘z’
if (M[c, Sj]) then inc(result, cnt[c]);
Слайд 24F. Интересные числа
Автор задачи – Федор Царев
Условие – Федор Царев
Подготовка тестов
– Сергей Поромов
Разбор – Федор Царев
Разбор – Федор Царев
Слайд 25Какие числа интересны?
Число x является интересным, если максимальная степень k, на
которое x делится, нечетна
110002 = 2410 делится на 8=23, но не делится на 16=24
110002 = 2410 делится на 8=23, но не делится на 16=24
Слайд 26Легко найти
Количество интересных чисел, не превышающих некоторое число y
Принцип включения-исключения
Слайд 27Двоичный поиск
Необходимо найти минимальное y, что f(y)=n
Инвариант f(hi) ≥ n, f(low)
< n
while (low + 1 < hi) {
long middle = (low + hi) / 2;
if (calc(middle, k) >= n) {
hi = middle;
} else {
low = middle;
}
}
out.println(hi);
while (low + 1 < hi) {
long middle = (low + hi) / 2;
if (calc(middle, k) >= n) {
hi = middle;
} else {
low = middle;
}
}
out.println(hi);
Слайд 28Альтернативный подход
Строим число, подбирая цифры со старших разрядов
f(L) – количество чисел
длины L, в которых первая и последняя цифры – не нули
Слайд 29Альтернативный подход
Определим длину искомого числа
Количество интересных чисел заданной длины g(L)
При восстановлении
важно хранить позицию последней ненулевой цифры
Слайд 30G. Оптимизация
Автор задачи – Сергей Копелиович
Условие – Роман Сатюков
Подготовка тестов –
Роман Сатюков
Разбор – Роман Сатюков
Разбор – Роман Сатюков
Слайд 31Обозначения
M – число частей проекта
mi – время выполнения i-ой части проекта
pi
– номер работника, которому назначена i-ая часть проекта
wi – время выполнения всех работ, назначенных работнику номер pi (i=1..M).
wi – время выполнения всех работ, назначенных работнику номер pi (i=1..M).
Слайд 32Критерий оптимизирующей операции
Каждую операцию можно задать номерами частей проекта, которые меняются
местами – (i, j).
Пара (i, j) – оптимизирующая, если и только если выполняются условия:
Пара (i, j) – оптимизирующая, если и только если выполняются условия:
Слайд 33Сведение к задаче о количестве инверсий в последовательности
Отсортируем части проекта в
порядке возрастания величины mi.
Пусть pi = –(wi – mi).
Тогда надо найти количество инверсий в полученном массиве p.
Эта задача решается за O(MlogM).
Пусть pi = –(wi – mi).
Тогда надо найти количество инверсий в полученном массиве p.
Эта задача решается за O(MlogM).
Слайд 34H. Шкафы
Автор задачи – Владимир Гуровиц
Условие – Андрей Станкевич
Подготовка тестов –
Федор Царев
Разбор – Федор Царев
Разбор – Федор Царев
Слайд 35Динамическое программирование
f(h) – максимальное число полок, находящихся не выше высоты h,
которые можно открыть
Интересных высот мало – рассматривать высоты внутри полок нет смысла
Интересных высот мало – рассматривать высоты внутри полок нет смысла
Слайд 36Жадный алгоритм
Из двух самых нижних полок разумно выдвинуть ту, которая ниже
Дальше
– аналогично
Слайд 37I. Архимедова спираль
Автор задачи – Владимир Ульянцев
Условие – Федор Царев
Подготовка тестов
– Владимир Ульянцев
Разбор – Роман Сатюков
Разбор – Роман Сатюков
Слайд 38Уравнения движения
α(t) = ω∙t
ρ(t) = R + V∙t
x(t)= ρ(t) ∙ cos(α(t))
y(t)=
ρ(t) ∙ sin(α(t))
x(t)= (R + V∙t) ∙ cos(ω∙t)
y(t)= (R + V∙t) ∙ sin(ω∙t)
Найти минимум и максимум каждой функции при 0 ≤ t ≤ T
x(t)= (R + V∙t) ∙ cos(ω∙t)
y(t)= (R + V∙t) ∙ sin(ω∙t)
Найти минимум и максимум каждой функции при 0 ≤ t ≤ T
Слайд 39Преобразование уравнений
Несложными преобразованиями задача сводится к задаче поиска максимума функции
при условии
Замечание: можно считать что tmax – tmin<2
Слайд 41Варианты решения
Для поиска максимума выпуклой функции можно применить тернарный поиск.
Максимумы функции
находятся в корнях ее производной. Корни производной можно найти с помощью двоичного поиска.
Слайд 42Варианты решения
Перебрать все t из диапазона [tmin;tmax] с некоторым шагом ε
и найти значение t1 с наибольшим значением f(t1). После этого перебрать все t в некоторой окрестности t1 с некоторым шагом ε2 (уточнить найденное t1).
Слайд 43Тернарный поиск
Задача: Дана функция f(t), выпуклая вверх на отрезке [a, b].
Требуется найти её максимум.
Инвариант: максимум функции достигается где-то на отрезке [a, b]
Разделим отрезок на три равные части: [a, x1], [x1, x2], [x2, b].
Инвариант: максимум функции достигается где-то на отрезке [a, b]
Разделим отрезок на три равные части: [a, x1], [x1, x2], [x2, b].
Слайд 44Тернарный поиск
Возможны два случая:
f(x1) ≤ f(x2)
f(x1) > f(x2)
В первом случае максимум
не может достигаться на отрезке [a, x1]. Переходим к отрезку [x1, b].
Во втором случае максимум не может достигаться на отрезке [x2, b]. Переходим к отрезку [a, x2].
Длина отрезка [a, b] каждый раз уменьшается в полтора раза.
Во втором случае максимум не может достигаться на отрезке [x2, b]. Переходим к отрезку [a, x2].
Длина отрезка [a, b] каждый раз уменьшается в полтора раза.
Слайд 45Тернарный поиск: Код
while (a + ε < b) {
double x1 =
(2·a + b) / 3;
double x2 = (a + 2·b) / 3;
if (f(x1) ≤ f(x2))
a = x1;
else
b = x2;
}
double x2 = (a + 2·b) / 3;
if (f(x1) ≤ f(x2))
a = x1;
else
b = x2;
}
Слайд 46J. Сумма
Автор задачи – Роман Сатюков
Условие – Роман Сатюков
Подготовка тестов –
Роман Сатюков
Разбор – Роман Сатюков
Разбор – Роман Сатюков
Слайд 47Представим числа A, B и C в следующем виде:
Числа A’, B’
и C’ не делятся на 10
Утверждение: Задача для чисел A, B, C имеет решение ⬄ задача для чисел A’, B’, C’ имеет решение
Утверждение: Задача для чисел A, B, C имеет решение ⬄ задача для чисел A’, B’, C’ имеет решение
Слайд 49Случай когда A,B,C не делятся на 10
Можно считать, что не более
двух чисел из n, m, k больше нуля (если нет – уменьшим n, m и k на единицу).
Утверждение: Максимум одно из чисел из n, m, k больше нуля.
Получается три случая: n=m=0, n=k=0 и m=k=0.
Утверждение: Максимум одно из чисел из n, m, k больше нуля.
Получается три случая: n=m=0, n=k=0 и m=k=0.
Слайд 50Случай n=m=0:
Получается уравнение A+B=C·10k.
Поскольку числа A, B и C заданы в
десятичной системе исчисления, то найти такое k можно за время, пропорциональное числу цифр в числах A, B, C.
Случай n=k=0:
Получается уравнение A+B·10m=C, которое преобразуется к уравнению C–A=B·10m.
Это уравнение аналогично уравнению, полученному в случае n=m=0.
Случай m=k=0: Аналогично предыдущему случаю.
Случай n=k=0:
Получается уравнение A+B·10m=C, которое преобразуется к уравнению C–A=B·10m.
Это уравнение аналогично уравнению, полученному в случае n=m=0.
Случай m=k=0: Аналогично предыдущему случаю.
