Региональный этап всероссийской олимпиады школьников по информатике 1 тур 1 февраля 2014 года. - презентация

1 Региональный этап всероссийской олимпиады школьников по информатике 1 тур 1 февраля 2014 года

2 Разбор задачи – Тимур Хисматуллин Задача 1. «POBEDA-2014»

3 Имеется 4 типа треугольников. Также дано количество треугольников конкретного типа. Требуется найти максимальную длину стороны квадрата, который можно замостить этими треугольниками, стороны которого параллельны осям «монитора». Постановка задачи Задача 1. «POBEDA-2014»

4 Для того, чтобы нарисовать единичный квадрат, требуется либо по одному треугольнику типа 1 и 2, либо по одному треугольнику типа 3 и 4. Идея задачи Задача 1. «POBEDA-2014»

5 o Таким образом, из a 1 треугольников типа 1 и a 2 треугольников типа 2 можно составить не более min{a 1, a 2 } квадратов, а из a 3 треугольников типа 3 и a 4 треугольников типа 4 – min{a 3, a 4 } квадратов. o Итого: K = min{a 1, a 2 } + min{a 3, a 4 } квадратов единичной длины. o Осталось решить задачу: какой максимальный квадрат можно составить из K единичных квадратов. Идея решения Задача 1. «POBEDA-2014»

6 o Для этого можно перебрать все квадраты натуральных чисел(1, 4, 9, 16, …), пока не встретится число, большее K. В этом случае сложность алгоритма будет равна О(К 1/2 ) o Либо извлечь из K квадратный корень и округлить результат до ближайшего целого вниз. В этом случае сложность алгоритма будет равна О(1) Решения задачи Задача 1. «POBEDA-2014»

7 o На ограничения o На сложность алгоритма o На встроенные библиотеки На что стоило обратить внимание? Задача 1. «POBEDA-2014»

8 Разбор задачи – Тимур Хисматуллин Задача 2. «Список школ»

9 Дано несколько строк, в каждой из которой содержится натуральное число без ведущих нулей и какие-то другие символы, не являющиеся цифрами. Необходимо найти количество различных чисел, которые встречаются во входных данных не более пяти раз. Постановка задачи Задача 2. «Список школ»

10 Для начала необходимо сформировать массив из этих чисел. Для этого нужно извлечь их из строк. Научимся выделять число из строки s. Замечание: так как число в строке может быть довольно большим(порядка 100 цифр), то следует хранить его как строку. Идея решения Задача 2. «Список школ»

11 while s[i] not in ' ': i := i + 1 start := i while i < len(s) and s[i] in ' ': i := i +1 finish := i После выполнения этого фрагмента программы подстрока строки s от символа с номером start до символа с номером finish (не включительно) и есть искомое число. Следует выделить этот номер и сохранить его в массиве sch. Выделение числа Задача 2. «Список школ»

12 o На Pascal: sch[k] := copy(string, start, length); o На C++: sch[k] = s.substr(start, length); Выделение подстроки из строки Задача 2. «Список школ» В основных языках программирования существуют встроенные функции, извлекающие подстроку из строки.

13 Выделение подстроки из строки Задача 2. «Список школ»

14 Выделение подстроки из строки Задача 2. «Список школ»

15 Выделение подстроки из строки Задача 2. «Список школ»

16 Выделение подстроки из строки Задача 2. «Список школ»

17 Выделение подстроки из строки Задача 2. «Список школ»

18 Выделение подстроки из строки Задача 2. «Список школ»

19 Выделение подстроки из строки Задача 2. «Список школ»

20 Выделение подстроки из строки Задача 2. «Список школ»

21 Выделение подстроки из строки Задача 2. «Список школ»

22 Выделение подстроки из строки Задача 2. «Список школ»

23 Выделение подстроки из строки Задача 2. «Список школ»

24 Выделение подстроки из строки Задача 2. «Список школ»

25 Выделение подстроки из строки Задача 2. «Список школ»

26 Выделение подстроки из строки Задача 2. «Список школ»

27 Выделение подстроки из строки Задача 2. «Список школ»

28 После прочтения всех строк, мы имеем массив чисел (записанных как строки) sch. Теперь необходимо среди них найти те, которые встречаются не более 5 раз. Это можно сделать, например, следующим образом: отсортировать строки в лексикографическом порядке. Равные строки будут идти подряд. Решение Задача 2. «Список школ»

29 Теперь, чтобы получить искомый ответ, осталось подсчитать, сколько раз встречается в массиве каждое число, и сформировать список чисел, встречающихся не более 5 раз. Это можно сделать, например, с использованием следующего фрагмента программы на языке Pascal: Нахождение ответа Задача 2. «Список школ»

30 count := 1; result := 0; for i := 2 to n do begin if (sch[i] = sch[i – 1]) then count := count + 1 else if (count

31 o На ограничение на размер числа o На выделение подстроки из строки o На время работы сортировки На что стоило обратить внимание? Задача 2. «Список школ»

32 Задача 3. «Межрегиональная олимпиада» Разбор – Кузьмичев Дмитрий

33 Разберем вначале частичное решение, основанное на предположении, что все задачи оцениваются одинаково. Представим каждую задачу отрезком на оси времени. Тогда задача сводится к классической: из заданного множества отрезков на прямой выбрать наибольшее количество отрезков, не имеющих общих точек. Для решения этой задачи можно использовать следующий алгоритм. Вначале выберем из всех отрезков тот, который заканчивается левее всех. Из отрезков, которые начинаются правее него, опять выберем отрезок, заканчивающийся левее всех и т.д. Частичное решение Задача 3. «Межрегиональная олимпиада»

34 Не сложно определить, что реализация этого алгоритма имеет асимптотическую сложность O(N 2 ). Более эффективное решение можно получить, отсортировав все начала и концы отрезков и пройдя слева направо по отсортированному массиву. Такое решение с учетом использования быстрой сортировки имеет уже асимптотическую сложность O(N log N). Улучшенное частичное решение Задача 3. «Межрегиональная олимпиада»

35 Идея решения: динамическое программирование Будем рассматривать только интересные моменты времени, а именно s[i] и s[i] + t[i], т.е. времена начала задания и конца. Сложим их все в массив times, отсортируем, удалим совпадающие Полное решение Задача 3. «Межрегиональная олимпиада»

36 Считаем динамику dp[j] – сколько максимум можем заработать баллов до момента времени times[j] включительно, т.е закончив выполнять задания в момент times[j]. Будем еще поддерживать B – момент времени, при котором dp[B] максимально. Значения массива dp и B будут меняться по ходу выполнения программы Полное решение Задача 3. «Межрегиональная олимпиада»

37 Для пересчета будем двигаться по временам times в порядке их возрастания. Пусть сейчас обрабатывается момент времени times[i]. Обновим B, т.е. проверим, что если dp[i] > dp[B], то B теперь равно i. Полное решение Задача 3. «Межрегиональная олимпиада»

38 Посмотрим, какие задания сейчас начинаются. Если есть задание под номером k, которое заканчивается в момент times[j], то пробуем улучшить dp[j] суммой dp[B] + c[k]. Это значит, что мы что-то делали до момента times[i] (с максимальной выгодой dp[B]), а затем приняли задание под номером k и его выполнили, получив дополнительно c[k] баллов Полное решение Задача 3. «Межрегиональная олимпиада»

39 Таким образом, в конце dp[B] – ответ на вопрос, сколько максимум баллов можно набрать. Но нужно еще восстановить последовательность заданий, выполнение которых дает такой результат Полное решение Задача 3. «Межрегиональная олимпиада»

40 Для этого будет помимо самой динамики запоминать еще пару from[j] –. Она в пересчете динамики обновляется соответствующим образом, т.е. если dp[B] + c[k] больше dp[j], то from[j] присваиваем Полное решение Задача 3. «Межрегиональная олимпиада»

41 Восстановление ответа в конце будет выглядеть следующим образом: присвоить cur значение B; Пока from[cur].second не равен 0 { Добавить в ответ from[cur].second cur присвоить from[cur].first; } Полное решение Задача 3. «Межрегиональная олимпиада»

42 Время выполнения должно быть O(n*log(n)), для этого нужна любая быстрая сортировка, а также для каждого задания k нужно найти время его начала и конца в массиве times (например, бинпоиском) Полное решение Задача 3. «Межрегиональная олимпиада»

43 Ответ на вопрос задачи может быть достаточно большим, поэтому необходимо было использовать 64-битный тип данных для подсчета значений массива dp (long long в C++, int64 в Pascal) Полное решение Задача 3. «Межрегиональная олимпиада»

44 Задача 4 «Дом Мэра» Разбор – Кузьмичев Дмитрий

45 Частичные решения Задача 4 «Дом Мэра» Если рассматривать небольшие ограничения, то решение задачи может быть следующим. Построим граф, соответствующий городу без застройки, при этом вершинам графа будут соответствовать перекрестки, а ребрам – дороги. Затем удалим в графе все ребра, попавшие в застроенные кварталы (сложность такой процедуры равна O(n * площадь города)). В полученном графе начнем поиск в ширину из точки (0, 0), чтобы определить расстояния до всех возможных расположений будущего дома Мэра, и выберем из них самое близкое. Восстанавливая путь при реализации поиска в ширину стандартным способом, можно найти точки поворота пути.

46 Частичные решения Задача 4 «Дом Мэра» Если площадь города велика, а кварталов застройки не много, то можно воспользоваться сжатием координат. Для этого при построении графа будем использовать только те горизонтали и вертикали, на которых расположены мэрия, будущие дома или границы кварталов застройки.

47 Полное решение Задача 4 «Дом Мэра» Основная идея решения в том, что искомые пути бывают всего двух принципиально разных видов: Первый: идем на север (возможно, на нулевое расстояние), затем поворачиваем, идем, поворачиваем снова в том же направлении, доходим до конца

48 Полное решение Задача 4 «Дом Мэра» Второй: идем на север (возможно, на нулевое расстояние), затем поворачиваем, идем, поворачиваем в другом направлении, доходим до конца

49 Полное решение Задача 4 «Дом Мэра» Легко видеть, что пути второго типа всегда короче путей первого типа, их длина равна просто сумме модулей координат конца пути Будем решать задачу для каждого варианта дома отдельно. Обозначим за H точку, соответствующую этому дому Найдем, насколько далеко на север от точки (0, 0) мы можем пройти (получится отрезок [0; x1]), а также как далеко на юг и на север можно пройти от точки H (отрезок [x2;x3]). Для этого переберем все строения и посмотрим, какие ограничения каждое из них накладывает на эти два отрезка

50 Полное решение Задача 4 «Дом Мэра» Очевидно, мы можем иметь возможность пройти по горизонтальной линии только в пересечении отрезков [0;x1] и [x2;x3], обозначим его [b1;b2] Однако, этому могут мешать строения. Чтобы найти, где можно сделать горизонтальный переход, а где - нет, применим метод сканирующей прямой, а именно будем двигаться ей, например, снизу вверх и поддерживать баланс – величину, которая равна количеству строений, которые уже начались, но еще не закончились. Соответственно, события бывают всего двух видов – строение началось, строение закончилось. Эти события нужно посортировать

51 Полное решение Задача 4 «Дом Мэра» Примеры (красным показаны отрезки, на которых возможен горизонтальный переход без учета ограничения отрезком [b1;b2], синим – отрезки [0;x1] и [x2;x3]

52 Полное решение Задача 4 «Дом Мэра» Таким образом мы обработаем все события, проверив все полученные варианты горизонтальных переходов на оптимальность и выбрав лучший. Сложность алгоритма - O(N*log(N)) для каждого варианта дома, т.к. самая долгая часть – это сортировка событий для использования метода сканирующей прямой. Суммарная сложность – O(k * N*log(N)) Не надо забывать про крайние случаи, а именно, когда H лежит на осях OX или OY. Они могут быть легко разобраны