II Этап Всероссийской олимпиады школьников по информатике 2010-11 учебный год. Разбор задач.
День 1.
1. ЕГЭ B1
За одну секунду можно передать 3 сообщения (0, 1, 2). За две к каждому из сообщений длины 1 добавляется по 3 окончания (00, 01, 02, 10, 11, 12, 20, 21, 22). При увеличении длины сообщения на один, количество различных сообщений возрастает в 3 раза. Итоговая формула примет вид: 3N.
Необходимо учесть, что 320 = 3 486 784 401, что не укладывается в знаковый 32-х битный тип данных.
2. Сейф
В задаче требуется найти число размещений n элементов по 3. После упрощений формула примет вид: n*(n-1)*(n-2)
Очевидно, что при использовании формулы будет получено большое число, для вычисления которого нужно использовать тип данных int64.
3. Шашлыки
Для решения задачи можно провести симуляцию обмена. Выбираем первый шампур, который стоит не на своем месте, и переставляем его на нужную позицию. Необходимо учесть, что после обмена шампуров, на текущей позиции может оказаться шампур, который также нужно переставить. Продолжаем до тех пор, пока есть шампура, стоящие не на своем месте, и выводим количество обменов.
4. Лист в линию
Для начала подсчитаем, сколько кусочков получится при использовании только горизонтальных линий. Их будет N+1.
Для каждой наклонной линии нужно подсчитать, какое количество горизонтальных линий она пересекает. Соответственно, одна наклонная линия нам добавляет количество кусочков, равное количеству пересечений плюс один.
Для определения количества пересечений нужно посчитать ординату точки пересечения прямой с боковыми сторонами прямоугольника: yb = -xi и yt = W-xi. Если yb оказался меньше нуля, то можно считать его равным нулю, аналогично если yt оказался больше H, то можно считать его равным H. Осталось подсчитать, какое количество горизонтальных линий находятся внутри интервала.
Если считать количество горизонтальных линий в пределах между yb и yt циклом, то решение не пройдет по времени на больших тестах. Для быстрого подсчета количества линий нужно воспользоваться деревом отрезков. Заведем массив из H+1 элементов, в котором будем хранить количество линий расположенных ниже данной высоты. По этому массиву можно быстро определять количество линий, расположенных в нужных пределах.
День 2.
5. Аэропорт
Для того, чтобы уровнять количество стульев среди оставшихся пассажиров необходимо, оставшееся число стульев нацело делилось на количество человек. Поэтому Васе необходимо забрать число стульев, равное остатку от деления N на M. Так как Вася хочет забрать как минимум один стул, то в случае, когда N нацело делится на M, Васе необходимо забрать M стульев.
6. ЕГЭ В3
Если число A в некоторой системе счисления с основанием P должно оканчиваться на 5, то остаток от деления А на P должен быть равен 5. Полный перебор возможных оснований не даст полного решения.
Можно заметить, что остаток от деления (A - 5) на P будет равен 0. Это равенство означает, что основание системы счисления является делителем числа (A - 5). Нужно отметить, что не все делители будут искомыми основаниями. Для полного решения поиск делителей должен производиться до корня.
7. Трасса Е95
Одной из отличительных особенностей трассы является то, что на ней заправки расставлены равномерно. Этот факт означает, что между соседними заправками одинаковое расстояние — D. Тогда справедливы равенства: B - A = X×D и C - B = Y×D. Таким образом, нам нужно найти наибольший общий делитель чисел (B - A) и (C - B).
8. Новогодние игрушки
Для решения задачи сначала будем подбирать количество игрушек, которое в итоге будет находиться на каждой елке. Очевидно, что это количество не будет превышать общее количество игрушек, деленное на количество елок. Несложно доказать, что оптимальным значением количества игрушек на каждой елке будет являться количество игрушек елки, которая расположена по середине отсортированного списка елок по количеству игрушек. Если это значение превышает максимально допустимое, то используем максимально допустимое. После этого достаточно подсчитать у каждой елки количество необходимых операций.
Очевидно, что ответ может быть достаточно большим, и для его вычисления нужно использовать тип данных int64.