Республиканская олимпиада по информатике 2010 года Заключительный этап Разбор задач Авторы разбора: А.О. Сикорский, С.И. Кашкевич. - презентация

1 Республиканская олимпиада по информатике 2010 года Заключительный этап Разбор задач Авторы разбора: А.О. Сикорский, С.И. Кашкевич

2 Конфетный розыгрыш Тур 1, задача 1 Пытались решить: 119 Решили полностью: 116 Среднее количество набранных баллов: 99.1

3 Конфетный розыгрыш Бочонок с минимальным числом непременно будет отброшен всеми детьми, которые его вытянут, и, следовательно, останется в мешке. Следовательно, результатом решения задачи будет сумма всех A i, за исключением минимального. Если совместить поиск минимального элемента и накопление суммы, то задачу можно решить за один просмотр массива A. Трудоёмкость решения этой задачи – O(N).

4 Спартакиада Тур 1, задача 2 Пытались решить: 119 Решили полностью: 86 Среднее количество набранных баллов: 88

5 Спартакиада Задача сводится к расчёту величины T i = A i * X + B i * Y + C i * Z для всех учеников школы и нахождению трёх учеников, для которых величина T i максимальна. Как и в предыдущей задаче, можно совместить поиск максимальных элементов и вычисление T i. Задачу также можно решить за один просмотр массивов A, B, C. Трудоёмкость решения этой задачи – O(N).

6 Морковная засуха Тур 1, задача 3 Пытались решить: 112 Решили полностью: 19 Среднее количество набранных баллов: 58

7 Морковная засуха Добавим к числу орошаемых горизонтальных борозд 0 -ю и N+1 -ю борозду, соответствующую границам поля. Тогда поле разбивается на N+1 горизонтальную полосу, ограниченную орошаемыми бороздами. Аналогичные рассуждения выполним для вертикальных полос. Обозначим соответственно через P i и Q i ширину вертикальной и горизонтальной полосы с номером i. Полосы разбиваются на три группы: 1. P i 2*K 1 2. P i > 2*(K 1 + K 2 ) 3. 2*K 1 < P i 2*(K 1 + K 2 )

8 Морковная засуха Для каждого участка, ограниченного орошаемыми бороздами, выполняем следующие рассуждения: Если хотя бы одна из полос, в которых лежит участок, относится к первому типу, безопасных гряд на этом участке нет. Иначе, если хотя бы одна из полос относится к третьему типу, то безопасные гряды образуют прямоугольник общей площадью ( P i - 2*K 1 ) * ( Q j - 2*K 1 ) Наконец, если обе полосы участка относятся к второму типу, безопасные гряды образуют «кольцо» площадью ( P i - 2*K 1 ) * ( Q j - 2*K 1 ) - ( P i - 2*(K 1 +K 2 )) * ( Q j - 2* (K 1 +K 2 ))

9 Морковная засуха Типы полос на рисунке из условия задачи: Трудоёмкость решения этой задачи – O(M*N)

10 Морковная засуха Существует и другое решение с трудоёмкостью O(M+N). Вначале просматриваем горизонтальные полосы и рассчитываем числовые величины S 1, S 2 и S 3. Изначально они равны нулю. В зависимости от типа полосы происходит увеличение этих величин: Если полоса принадлежит к второму типу, то S 2 := S 2 + ( Q j - 2*K 1 ), S 3 := S 3 + ( Q j - 2* (K 1 +K 2 )) Если полоса принадлежит к третьему типу, то S 1 := S 1 + ( Q j - 2*K 1 )

11 Морковная засуха Затем просматриваем вертикальные полосы. Если полоса принадлежит к второму типу, то количество безопасных гряд увеличивается на (P i - 2*K 1 ) *S 1 + (P i - 2*(K 1 +K 2 )) * S 3 Если полоса принадлежит к третьему типу, то количество безопасных гряд увеличивается на (P i - 2*K 1 ) *(S 1 +S 2 )

12 Видео сервис Тур 1, задача 4 Пытались решить: 102 Решили полностью: 6 Среднее количество набранных баллов: 25

13 Видео сервис Будем считать Иваново кемпингом с номером 0, а Славино – кемпингом с номером N+1. Введём функцию F(i, j) – искомая сумма коэффициентов при условии, что i сервисов расположены до кемпинга с номером j, а оставшиеся k-i сервисов – в кемпинге j (хоть это и запрещено условиями задачи). Тогда решение нашей задачи – F(k, N+1). Для этой функции будем строить рекуррентное соотношение.

14 Видео сервис Очевидно, F(0, 0) = 0. Рекуррентное соотношение для F(i, j) имеет вид при условии Решение про этой формуле имеет трудоёмкость O(N 3 ) и набирает 60 баллов.

15 Видео сервис Перепишем рекуррентное соотношение, вынося члены, не зависящие от t: Рассчитываемые величины помещаем в кучу, единую для всех j. При этом из кучи, возможно, придётся выбросить элементы, для которых условие (*) не выполняется. Такое решение имеет трудоёмкость O(N*K*logN) и набирает 100 баллов.

16 Бактериальное родство Тур 2, задача 1 Пытались решить: 119 Решили полностью: 116 Среднее количество набранных баллов: 99.3

17 Бактериальное родство Задача решается полным перебором. Просматриваем все модификации A x и B y для всех возможных x и y и рассчитываем степень родства для каждой пары. Для упрощения расчётов можно продублировать каждую строку и для модификаций A x и B y сравнивать символы A[x+t] и B[y+t] для всех возможных t. ATGATACGCAGTATGATACGCAGTATGCGTAGTATAATGCGTAGTATA

18 Стоп игра! Тур 2, задача 2 Пытались решить: 119 Решили полностью: 58 Среднее количество набранных баллов: 80.5

19 Стоп игра! Задача сводится к нахождению числа из интервала [L, R], для которого первый делитель, отличный от единицы, максимален (точнее, самого такого делителя). При этом имеет смысл проходить от больших чисел к меньшим: если мы найдём простое число, то перебор прекращается.

20 Брокер Тур 2, задача 3 Пытались решить: 119 Решили полностью: 27 Среднее количество набранных баллов: 66.6

21 Брокер Простейшее решение этой задачи состоит в моделировании процесса продажи и покупки акций и может быть реализовано следующим фрагментом программы: for i := 1 to K do if N>=i then {покупаем акцию} N := N-i else {продаём акцию} N := N+i; Такое решение набирает 50 баллов.

22 Брокер Для того, чтобы обнаружить закономерность и уменьшить количество итераций, рассмотрим поведение брокера при N=1. Когда количество денег уменьшается до нуля, брокер продаёт две акции подряд, иначе дни покупки и продажи чередуются __+_+__+_+_+_+_

23 Брокер Если баланс достигает нуля в день T, далее следуют продажа и T+1 цикл продажи – покупки. Следующее обнуление баланса наступит в день 3*(T+1). Таким образом, нам необходимо определить день R последнего обнуления баланса, а затем рассчитать окончательный баланс. В случае, когда изначально брокер имеет достаточно денег для нескольких покупок, необходимо выполнить указанный ранее цикл до первого обнуления баланса. Трудоёмкость этого решения – O(logN).

24 Шарики 2010 Тур 2, задача 4 Пытались решить: 116 Решили полностью: 1 Среднее количество набранных баллов: 38.8

25 Шарики 2010 Сведём начальную и конечную позицию воедино, добавив обозначения «шарик исчез» и «шарик появился»: Заметим, что если A + B C, то применять сдвиг нецелесообразно, достаточно выполнять лишь операции первого и второго типа (1 тест). Если отказаться от операции сдвига вообще, то можно получить 40 баллов.

26 Шарики 2010 Пусть K – целая часть от деления A + B на C. Тогда имеет смысл переместить шарик из красной в жёлтую позицию, если расстояние между ними не превосходит K и на этом пути нет запрещённых клеток. Осталось найти пары клеток, для которых надо выполнить сдвиг.

27 Шарики 2010 Для решения этой задачи можно пойти несколькими путями, например: Построить двудольный граф, вершины которого соответствуют красным и жёлтым клеткам. Рёбра графа связывают вершины разных цветов, расстояние между которыми не превышает K, а вес вершины равен минимальному расстоянию между клетками. В этом графе находим максимальное паросочетание минимального веса. Для K=4 и предыдущего примера имеем: 3 1 (3,3)(4,1) (3,2)