Тренировка проводится в режиме онлайн. ближе к 21 часам я выложу в ответе краткий письменный разбор, ссылку опубликую завтра.
Ссылка http://acm.math.spbu.ru:8087/~ejudge/team.cgi?contest_id=010041
Задача А.
Стандартная задача. Будем считать вероятность победы первого игрока если сейчас выпал префикс от 0 до i, первого или второго игрока (в случае если префикс и той и той выберем тот что больше, в случае равенства выберем первого). Далее смотрим линейную формулу перехода между вероятностями в случае орла или решки. Получим p[i]=p[r[i]]+p[q[i]] где r[i] и q[i] индексы состояний при решке и орле соответственно + имеем равенство для конечных состояний (когда выпала строка целиком) 0 и 1. Решаем систему уравнений и выводим p[0]. Переходы между состояниями в виду малого размера строк и отсутствия вложенности посчитать легко)
Задача B.
Нужно посчитать количество остатков по модулю L принемаемых нечетное число раз. Решается массивом.
Задача C.
Делаем ленивой динамикой по состоянию обработано n первых человек у последнего премия k осталось денег в фонде l, при этом обрезаем по факту того что денег нам хватит чтобы оставшимся заплатить по минимуму.
Задача D.
Если число одно то выводим степень, если больше то ответ не превышает максимальное в 300ой степени. храним сет изначально из 1, размером не более 100000. Как забираем число из сета, добавляем туда его умноженное на все множители, для ускорения можно сравнивать логарифмы, а при близкой точности уже сами числа. Чем больше чисел тем меньше будет ответ, а если чисел мало то новых добавлений будет мало.
Задача E.
надо возвести матрицу перехода
1 1 1
1 0 0
0 1 0 в N-ю степень в дабле(аккуратно обрабатывая мантиссу, чтобы не переполнялась) и по модулю 1000
Задача F.
Динамика по отрезку массива и нетерминальному символу, считает может ли данный отрезок быть получен из данного нетерминала
Задача G.
Здесь нужно воспользоваться формулой эйлера она дает F = 2 + V - N заметим что каждая точка пересечения двух фигур увеличивает число ребер на 2 а число вершин на 1, то есть прибавляет 1 к результату. то есть ответ 2 + число точек пересечения далее считая сколько каждая из фигур может пересекаться с каждой другой имеем 2 + 2m(m-1) + 4mn + n(n-1) + 3p(p-1) + 6pn + 6pm Учитывая ограничения можно перебрать p и m до 100(ну или честно перебирать чтобы значение формулы не превосходил n таких вариантов тоже будет не очень много), а далее получить n решая квадратное уравнение.
Задача H.
Заливаем на каждый отрезок по равному объему воды ставя невидиые стенки, если где то она нужна удаляем ее и перераспределяем воду, при каждом таком перераспределении работаем по сути с трапецией
Задача I.
наибольшая реализуется последовательным приписыванием чисел в порядке убывания то слева то справа, наименьшая чередованием текущих макисмальных и минимальных элементов:
...n-6 n-4 n-2 n n-1 n-3 n-5 ....
n 1 n-1 2 n-2 3 ....
Задача J.
Бин поиск по ответу, после этого каждого следующего агента минимизируем но чтобы расстояние не было меньше M, находим максимальное M для которого это получится.
