Всем привет!

Привожу разбор задач для раунда #78.

Еще раз приношу свои извинения за ситуацию с задачей B (div. 1) / D (div. 2). Также, приношу свои извинения за недооценку сложности задач. По крайней мере, надеюсь, что задачи показались участникам интересными.

В этой задаче необходимо округлить число по обычным математическим правилам, за исключением случая, когда последняя цифра целой части числа равна 9: в этом случае необходимо было вывести "GOTO Vasilisa.". Можно заметить, что для проверки того, что дробная часть числа не меньше 0.5, достаточно рассмотреть только первую цифру сразу после десятичной точки. Если эта цифра равна 5 или больше - мы добавляем 1 к последней цифре целой части числа, и задача решения. Возможно, самым удобным способом обработки входных данных (которые, как было указано в условии, могли быть очень длинными), было использование строковых переменных.

В задаче нужно было аккуратно проверить что требовалось по условию. Прежде всего, проверим, что все объемы компота во входных данных равны - в этом случае выведем "Exemplary pages.". В противном случае найдем два кубка с наибольшим и наименьшим объемами. Предположим, что их номера a и b, и объемы компота в них соответственно v[a] и v[b]. Теперь предположим, что до предполагаемого переливания их объемы были равны V. Тогда они содержали 2V миллилитров компота до (и после) переливания. Поэтому, необходимо проверить, что (v[a] + v[b]) делится на 2. Если это не так - выводим "Unrecoverable confihuration.". В противном случае присвоим кубкам предполагаемый объем компота до переливания: v[a] = v[b] = (v[a] + v[b])/2. Теперь, если только одно переливание было совершено, объемы компота во всех кубках должны стать равны, и мы выводим соответствующее сообщение "... ml. from ... to ...". Если объемы не равны, выводим "Unrecoverable configuration".

В этой задаче необходимо найти количество различных раскрасок граней куба шестью заданными цветами. Вероятно, самое простое решение данной задачи - как то упорядочить грани (скажем, 0 - передняя, 1 - задняя, 2 - верхняя, 3 - нижняя, 4 - левая, 5 - правая), затем рассмотреть 720 = 6! размещений цветов по граням. Каждое размещение есть некоторая перестановка заданных на входе символов. Для каждого размещения мы находим все 24 возможных вращения куба с заданной раскраской - получаем 24 строки символов Лексикографически минимальная строка будет представителем этой раскраски. Ответ к задаче - количество различных представителей.

В этой задаче предполагалось численное решение. Но сначала нужно рассмотреть несколько случаев. Ниже без потери общности мы считаем a <= b.

1. l <= a <= b. В этом случае ответ ограничен длиной гроба, поэтому ответ есть l, и понятно, что гроб размерами l x l может быть пронесен через коридор (a, b) - будем обозначать размеры коридора таким образом.

2. a < l <= b. В этом случае ответ есть a, и понятно, что никакое большее число не может быть ответом. В самом деле, в противном случае гроб размерами (w > a) x (l > a) невозможно пронести через коридор (a, b).

3. a <= b < l. Этот случай наиболее общий, здесь мы должны повернуть гроб в месте изгиба коридора. Для максимизации ширины гроба, мы хотим перемещать его таким образом, что один угол гроба касается одной из внешних стен коридора (предположим, самая нижняя стена на рисунке к задаче), а другой угол, прилегающий к той же длинной стороне гроба, касается другой внешней стены коридора (самая левая стена на рисунке к задаче). Введем систему координат таким образом, что нижняя стена будет осью OX, а левая стена - осью OY. Предположим, что в процессе "вращения" один угол гроба находится в точке (x,0) (0 <= x <= l), тогда другой угол гроба должен быть в точке (0,sqrt(l*l-x*x)). И ответ, который мы ищем, есть min {расстояние от отрезка (x,0) - (0,sqrt(l*l-x*x)) до точки (a,b) }, где min{} берется по всем 0 <= x <= l. Обозначим расстояние в точке x за f(x). Поскольку f(x*) минимальна в некоторой точке x* и возрастает слева и справа от x*, можно использовать тернарный поиск для нахождения ее минимума.

В этой задаче возможно также и точное решение: задача сводится к минимизации косого произведения векторов (a-x,b) and (-x,sqrt(l*l-x*x)) по x. Однако эта задача сводится к нахождению корней многочлена четвертой степени, что, вероятно, не есть самое удачное решение в условиях 2-х часового контеста.

Эта задача по мотивам известной головоломки "Ханойские башни", в которой диаметры некоторых дисков могут быть равны. Как же ее решить? Хорошая (и в то же время несложная) вещь, которую можно сделать - написать решение BFS-ом для проверки оптимальности ваших идей для небольших входных данных (кстати, BSF работает достаточно быстро практически для всех башен, имеющих до 10 дисков) и затем попытаться придумать оптимальный алгоритм решения головоломки.

Пусть C (x1, x2, ..., xn) будет решением задачи (под "решением" здесь мы подразумеваем оптимальное количество ходов - сами ходы могут быть легко получены с использованием рекурсивной процедуры; также "решение" есть количество ходов переместить группу дисков с одного стержня на любой другой стержень (а не какой-либо конкретный) ) головоломки, когда мы имеем x1 одинаковых самых больших дисков, x2 одинаковых дисков, вторых по величине, и так далее. И пусть U (x1, x2, ..., xn) будет решением головоломки когда разрешено не сохранять порядок дисков (необходимо соблюдать условие первоначальной головоломки не класть большие диски на меньшие, но в конце диски равного диаметра могут лежать как угодно).

Тогда одно из оптимальных решений задачи следующее:

C (x1, x2, ..., xn) = U (x1, x2, ..., xn) если x1 = 1 (*)

C (x1, x2, ..., xn) = 2*x1 - 1 если n = 1 (**)

C (x1, x2, ..., xn) = U (x2, ..., xn) + x1 + U (x2, ..., xn) + x1 + C (x2, ..., xn). (***)

U (x1, x2, ..., xn) = U (x2, ..., xn) + x1 + U (x2, ..., xn) (****)

Почему так? Можно заметить, что U() - "почти" решение нашей задачи: оно "переворачивает" группу самых нижних одинаковых дисков, порядок остальных дисков остается тем же! (попробуйте понять почему)

Поэтому верно (*).

(**) довольно очевидно.

(***) означает следующее: переместить (x2, ..., xn) со стержня 1 на стержень 2 без сохранения порядка. Затем переместить x1 одинаковых дисков со стержня 1 на стержень 3, затем переместить (x2, ..., xn) со стержня 2 на стержень 1 без сохранения порядка (но оказывается, что после того, как мы применим U() к той же самой группе дисков дважды, порядок сохраняется!), затем переместить x1 равных дисков со стержня 3 на стержень 2, и затем использовать C() для перемещения (x2, ..., xn) со стержня 1 на стержень 2 (здесь мы используем C() для сохранения первоначального порядка дисков). Так что (***) тоже верно.

А (****) довольно очевидное выражение для U(): переместим все диски кроме группы самых больших дисков тем же алгоритмом, затем переместим самые большие диски (вот почему если x1 > 1, порядок дисков в самой большой группе "переворачивается"), и затем переместим все остальные диски к группе x1 тем же самым алгоритмом.

Эта задача была на оптимальную игру в эту "простую-на-первый-взгляд" игру. Ключевая вещь, которую нужно было понять - это то, что называть только карты, которых у вас нет на руках, не всегда оптимально. Иногда оптимально попытаться обмануть соперника, назвав карту, которая имеется у вас на рука. В этом случае... да, он может подумать, что карта, которую вы назвали - это карта на столе, и проиграть своим следующим ходом. Теперь задача - понять, когда выгодно использовать стратегию уменьшения количества карт соперника, когда - блефовать как описано выше и когда пытаться угадать карту на столе. Но вместо "когда" верный вопрос - "как часто", поскольку перед нами не что иное, как обычная матричная игра с постоянной суммой, и оптимальной стратегией является смесь этих трех стратегий (то есть, на каждом ходу - выбор одной из трех с некоторыми вероятностями). Но сначала сконструируем матрицу. Игрок 1 имеет три чистые стратегии: "игра" (когда он играет в игру и на самом деле пытается определить карты соперника и карту на стоде), "угадывание" (когда он пытается угадать карту на столе) и "блеф" (когда он пытается обмануть соперника, чтобы тот проиграл, назвав в качестве карты на столе карту, которая на самом деле в руке первого игрока). В свою очередь, если первый игрок использовал стратегию "блефа", или в результате использования стратегии "игра" случайно назвал карту на столе, его соперник имеет две альтернативы: "проверка" (то есть, поверить первому игроку, что он не назвал карту в своей руке и попытаться угадать карту на столе, назвав эту карту) и "далее" (то есть, решить, что это была стратегия "блеф" и игра просто должна быть продолжена, но с исключением карты, названной первым игроком, из списка возможных карт на столе). Обозначим P(m,n) вероятность выиграть игру, когда первый игрок имеет на руках m карт, а второй игрок - n карт. Тогда P(m,n) есть цена матричной игры со следующей матрицей (строки - стратегии первого игрока, столбцы - стратегии второго игрока):

                                  "проверка"                                    "далее"

"игра"              n/(n+1)*(1-P(n-1,m))        1/(n+1) + n/(n+1)*(1-P(n-1,m))

"угадывание"            1/(n+1)                                     1/(n+1)

"блеф"                            1                                       1-P(n,m-1)

Как получить числа в матрице? Рассмотрим первую строку: стратегия "игра" первого игрока, "проверка" второго игрока. Первый игрок просто называет наугад одну из n+1 карт. С вероятностью 1/(n+1) от называет карту на столе, второй проверяет ее и выигрывает (так что вероятность выиграть для первого игрока 0), с вероятностью n/(n+1) первый игрок называет одну из карт на руках второго игрока, и игра продолжается, второй игрок выигрывает с вероятностью P(n-1,m) в этом случае. Тогда общая вероятность выигрыша первого игрока с таким сочетанием чистых стратегий есть n/(n+1)*(1-P(n-1,m)). Так же точно заполняются остальные элементы матрицы. Затем мы решаем игру (это можно сделать либо напрямую, или одной формулой, если заметить, что стратегия "угадывание" неоптимальна в случае когда m>=1 и n>=1 и в матрице нет седловых точек) и получаем ответ для исходной задачи - P(m,n).

И последнее, что нужно заметить: когда m==0 понятно, что своим ходом второй игрок выигрывает, поэтому первый должен "угадывать", и P(0,n) = 1/(n+1). Когда n==0 P(m,0)==1 - первый просто совершает одно верное угадывание.