Тренировки

Тренировка в четверг 26.09.2013

basil-ast
25 сентября 2013, 14:39

Тренировка проводится в режиме онлайн. ближе к 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 для которого это получится.

5 комментариев
Подписаться на комментарии к посту
Комментарий удалён

перого ставим в минимальное как и просят по условию, далее ставим воторого в ближайшую к первому и так далее

Понятно как по первому расставить остальных. Непонятно куда его ставить.

цитируя условие "а первый агент должен всегда располагаться в месте с наименьшей возможной координатой"

Как найти эту наименьшую возможную координату? Может быть, я неправильно понимаю условие: сначала максимизируется минимальное расстояние между соседними, потом минимизируется максимальное расситояние между соседними и потом минимизируется координата первого?

Нет это условие задачи, чтобы агент был в минимально возможной координате, а уже по модулю этого факта ищется максимум