У многих сильных студентов Чемпионат Урала :)

Пока такой функционал не реализован на сайте RCC

У меня такая же проблема, кажется, что если зарегистрироваться после начала тура, то в нём нельзя участвовать.

(1,1) -> (2,1) -> (3,1) => 5 * 0,25
(1,1) -> (2,1) -> (3,2) => 5 * 0,25
(1,1) -> (2,2) -> (3,2) => 6 * 0,50

В сумме 5,5

Логиниться я правда начал где-то через полчаса после начала, my bad. Но это же не повод меня совсем не пускать:(

Платформа codeforces действительно одна из лучших, если не самая лучшая. Но к желанию mail.ru проводить контесты на своей площадке я отношусь спокойно (google и yandex проводят же). Все было бы хорошо, если бы не этот ГИГАНТСКИЙ шрифт. Они считают программистов по умолчанию слепыми? Уменьшить масштаб не вариант, ибо при нормальном размере текста задач остальное становится слишком мелким и сбоку огромные пустые полосы. Смилуйтесь, если не хотите менять дизайн — сделайте условия в pdf на olymp.sty! С остальным сможно смириться, но не с необходимостью постоянно прокручивать и читать одно слово на весь экран.

А чего удалили? Интересно же, что заплюсовали. Или было много-много мата на дизайн сайта, судя по ответу?

Интересно, почему сила плюсомета не угасает даже с УДАЛЕНИЕМ комментария?

Мой код, получивший WA1 на их сайте, зашел в тренировке с первой попытки. ¯_(ツ)_/¯

Я делал рекурсию с мемоизацией. Логика простейшая:

    if (l < r)
        res = recurse(i + 1, j) + l;
    else if (r < l)
        res = recurse(i + 1, j + 1) + r;
    else
        res = 0.5 * (recurse(i + 1, j) + l) + 0.5 * (recurse(i + 1, j + 1) + r);

Довольно простая, храним два массива prob[][], expected[][] — вероятность и мат. ожидание в какой то клетке.
Код.

Для каждой комнаты динамикой считаем вероятность туда попасть и для каждого коридора, выходящего из этой комнаты, плюсуем к ответу его <длину> * <вероятность попасть в комнату, откуда выходим> * <вероятность пойти по этому корридору (0, 0.5 или 1)>

Для первой степени оказывается не очень интересно

1) Смотрим, что 10^9 + 23 = 3 * 121 * 61 * 45161.
2) Для каждого из этих множителей находим период Пизано (период последовательности Фибоначчи по этому модулю). Считаем частичные суммы нужных нам степеней по этому модулю, а также сумму на всем периоде. По этим величинам нетрудно найти нужное нам значение по рассматриваемому множителю.
3) Зная значение интересующей нашей величины по взаимно простым модулям, можно найти значение по модулю их произведения, используя китайскую теорему об остатках.

Модуль составной, 45161 * 22143 (22143 тоже составное но не важно). Можно решить по каждому модулю отдельно и потом китайской теоремой об остатках соединить. По первому модулю последовательность ФФиббонначчи зацикливается после 45160 элементов, по второму вообще после 1320. Можно эти ~50000 предпосчитать и потом возвести все в степень К. Потому считаем сумму всех нужное число раз и ещё раз проходим чтобы посчитать сумму оставшегося куска.

У меня с быстрым возведением в степень в long long не зашло (вообще достаточно int'а). Я ещё делал K %= phi(mod) но тут можно напороться на то, что если K = t * phi(mod) то не сработает для чисел, не взаимнопростых с mod, очень долго отлавливал этот кейс.

(пример фейла: 6 = pow(3, 8, 15) ≠ pow(3, 0, 15) = 1. Тут phi(15) = 8.

У меня зашел бинпоиск. Зная радиус, проходимся по массиву и пытаемся жадно лезть к краю окружности, и проверям, что каждая палка влезает.

У меня зашел какой то треш: http://pastebin.com/uv9DFf2J. Я использовал соображения, что либо ответ это максимальная палка делить на 2, либо есть какая-то палка, которую мы не успеем сделать диаметром, т.к. палки впереди нее не достают в сумме до окружности.

В любом случае радиус будет не меньше первого отрезка. Дальше идем по всем палкам и стараемся самую длинную положить на диаметр. Она кладется, когда сумма всех предыдущих ей палок больше половины ее длинны. А все последующие палки будем укладывать так, чтобы обе точки лежали на окружности. Тогда на каждом ходу мы сможем положить палку, не меньшую текущего радиуса.

Радиус не может быть меньше, чем:

1. длина первой палочки;

2. половина длины какой-либо палочки кроме первой;

3. длина какой-то палочки минус сумма длин предыдущих палочек.

1 и 2 — очевидно почему, 3 — нам нужно чтобы самая большая палочка стала диаметров окружности, а для этого нам нужно успеть прийти к этой окружности от центра.

У меня пара оптимизаций для возведения в степень помогла. (На intах вместо long long, и K %= phi(mod)).

А почему не выводятся тесты на которых валится сабмит? Они же все равно публичные, зачем прятать. А так легче дебажить было бы.

TL по D бы уменьшить... моё решение получало TL на RCC, здесь заходит за 2.2. Я бы поставил 2 секунды.

Тоже получал на контесте только WA1 на GNU C++ по A, B и C.

В тренировке те же, судя по времени редактирования, решения получают WA1 по A, (хотя локально ответы на выложенных тестах совпадают), TL10 по B и AC по С.

Написал в форму обратной связи.

Под наиболее дефолтной сборкой MinGW под винду вывод long double не работает никак вообще. Ни cout, ни printf("%lf") ни printf(не-знаю-что-еще). Потому что оно использует printf из вижаковской libmsvcrt, а там long double нет по каким-то очевидным причинам.