Analysis QR2 RCC 2015
Задача A. Турникеты в метро.
Идея: Дмитрий Филиппов.
Реализация: Дмитрий Филиппов.
Разбор: Виталий Аксёнов.
По условию задачи нужно найти момент времени, когда числа, отображаемые на турникете у двух мальчиков, будут отличаться в k раз. В первую очередь разберём случай k=1, в этом случае ответ — YES, если на обоих турникетах показывается 99 или если a = b. Иначе, несложно заметить, что правильный момент времени наступит не раньше, чем у какого-то мальчика количество поездок станет меньше 99. Перейдём сразу к первому такого моменту. У нас осталось всего не более 99 вариантов подходящих дней. Переберём и проверим каждый из них на то, что он удовлетворяет условию задачи.
Задача В. Игра.
Идея: Николай Ведерников.Реализация: Николай Ведерников.
Разбор: Николай Ведерников.
По условию задачи нужно найти математическое ожидание длины пути с первого уровня до последнего. Для этого воспользуемся методом динамическим программированием.
В dp[i][j] будет хранить математическое ожидание длины пути, если мы начнем на i-м этаже в j-ой комнате и пойдём до последнего уровня. Тогда ответ на нашу задачу будет хранится в dp[1][1].
Будет решать задачу с последнего уровня до первого. Понятно, что dp[n + 1][x] = 0, где x от 1 до n + 1. Теперь зная ответ для (k + 1)-го уровня, посчитаем значение динамики для k.
- Если a[k][j][0] < a[k][j][1], тогда dp[k][j] = dp[k + 1][j] + a[k][j][0]. Где a[k][j][0] — длина коридора с k-го уровня j-ой комнаты в j-ую комната на (k + 1)-ом уровне. А a[k][j][1] — длина коридора с k-го уровня j-ой комнаты в (j + 1)-ую комната на (k + 1)-ом уровне.
- Если a[k][j][0] > a[k][j][1], тогда dp[k][j] = dp[k + 1][j + 1] + a[k][j][1].
- Если a[k][j][0] = a[k][j][1], тогда dp[k][j] = (dp[k + 1][j] + dp[k + 1][j + 1]) / 2 + a[k][j][0]. Так как мы могли равно вероятно пойти как по первому коридору, так и по второму с равной вероятностью.
После подсчёта ответ на задачу будет храниться в dp[1][1].
Задача С. Палочки и Шарниры.
Идея: Георгий Корнеев.Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.
В этой задаче нам дана последовательность палочек, соединенных шарнирами, которая может принимать форму любой ломаной, с ребрами равными длинам соответствующих палочек. В условии эта фигура была названа цепочкой. Нужно найти минимальный радиус такой окружности, что в нее можно поместить цепочку, при этом центр окружности должен совпадать с началом первой палочки.
Рассмотрим решение с помощью двоичного поиска по ответу. Очевидно, что если цепочка помещается в окружность, то она поместится и в окружность большего радиуса.
Теперь надо научиться проверять, что окружность может вместить в себя цепочку. Идея проста: наберем максимальное количество палочек, такое что их суммарная длина меньше либо равна радиусу окружности. Если больше палочек нет, то задача решена. Иначе, смотрим, можем ли поместить следующую: если ее длина минус сумма предыдущих больше радиуса (развернули ее в шарнире на 180 градусов, и она вышла за пределы окружности), значит, уместить цепочку в эту окружность нельзя, иначе — на окружности найдется точка, на которую можно положить следующий шарнир, а значит, эта палочка поместится. Теперь проверяем, что длина оставшихся палочек меньше диаметра окружности, что равносильно тому, что мы можем разложить все оставшиеся шарниры на окружность, и цепочка поместится в окружность.
Задача D. Числа Фибоначчи.
Идея: Илья Збань.
Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.
По условию задачи нужно найти сумму k-ых степеней первых n чисел Фибоначчи по модулю 109+23. Самое первое действие заключалось в разложении модуля на множители: 109+23 = 3·112·61·45161. Давайте посчитаем нужную сумму по каждому из этих модулей и восстановим по Китайской Теореме об Остатках ответ на задачу.
Для каждого модуля по отдельности задача решается следующим образом. Найдём период чисел Фибоначчи. Для наших модулей они получаются небольшими, и предпериод всегда равен 0. Посчитаем сумму k-ых степеней чисел Фибоначчи на данном периоде и ещё небольшом кусочке. Тогда ответ на задачу при фиксированном n будет равен сумме нескольких периодов и сумма на маленьком кусочке.
Получив ответ для каждой из меньших задач, восстанавливаем ответ для начальной задачи.
К сожалению, на данном этапе задача не заканчивалась. Нужно придумать любую оптимизацию для того, чтобы программа прошла по времени. Можно было применить следующие: избавиться от двойного взятия по модулю при быстром возведении в степень, предварительно предподсчитав числа в степенях степени двойки, либо возводить не в степень k, а воспользоваться теоремой Эйлера и возводить в степень по модулю φ.
Задача E. Телепорты.
Идея: Илья Збань.Реализация: Илья Збань.
Разбор: Илья Збань.
В задаче дано n точек-телепортов, от которых можно отразиться, и требуется проверить, можно ли добраться из стартовой точки до конечной.
Заметим, что два отражения подряд относительно точек i, j прибавят к координате текущей точки вектор f(i, j) = (2(xj — xi), 2(yj — yi)). Если мы знаем, что в ответе четное число отражений, то задачу можно свести к следующей: можно ли представить вектор (xf — xs, yf — ys) суммой векторов f(i, j). Случай с нечетным числом векторов в ответе сводится к задаче с четным числом, если первым действием отразить стартовую точку относительно любого телепорта (может показаться, что нужно перебрать все n вариантов первого хода, но на самом деле это не обязательно) и попытаться решить задачу с четным числом векторов в ответе.
Заметим, что не нужно использовать все n2 векторов f(i, j): f(i, j) = f(1, j) — f(1, i). Итак, у нас в рассмотрении остался всего n-1 вектор. Утверждается, что целочисленную линейную оболочку целочисленных векторов можно представить как целочисленную линейную оболочку всего двух некоторых векторов, т.е. эта оболочка — некоторая сетка на плоскости.
Будем добавлять в рассмотренное множество векторы по одному и поддерживать два вектора, задающие линейную комбинацию всех уже добавленных. Один вектор будет иметь вид v1 = (x1, 0), где x1 — минимально возможное положительное, а второй — v2 = (x2, y2), где y2 — минимально возможное положительное, и 0 ≤ x2 < x1.
Пока все добавленные векторы коллинеарны, используя алгоритм Евклида легко находить, какой единственный вектор может представить своей линейной комбинацией все остальные. Как только в рассмотренном множестве появляется хотя бы одна пара неколлинеарных векторов, векторы пересчитываются иначе. Пусть добавлен был вектор v3.
Чтобы найти новый вектор v1, надо посмотреть на GCD двух векторов: старого v1, и вектора с минимальным x вида (x, 0), представимого линейной комбинацией векторов v2 и v3. Для этого нужно найти минимальное решение уравнения k2 · y2 + k3 · y3 = 0.
Чтобы найти новый вектор v2, надо рассмотреть вектор вида k2 · v2 + k3 · v3. Нужно найти любое решение уравнения k2 · y2 + k3 · y3 = GCD(y2, y3), и прибавить несколько раз новый v1, чтобы гарантировать минимальность по х-координате.
Зная два вектора, задающие сетку, легко проверить, что данный вектор представим в виде их целочисленной линейной комбинации: нужно всего лишь проверить, что его коэффициенты разложения по этим двум векторам являются целыми числами.
Комментарии (0)
