Всем привет!
Привожу разбор задач для раунда #78.
Еще раз приношу свои извинения за ситуацию с задачей B (div. 1) / D (div. 2). Также, приношу свои извинения за недооценку сложности задач. По крайней мере, надеюсь, что задачи показались участникам интересными.
Задача A (div. 2) - Помогите Тридевятому царству
В этой задаче необходимо округлить число по обычным математическим правилам, за исключением случая, когда последняя цифра целой части числа равна 9: в этом случае необходимо было вывести "GOTO Vasilisa.". Можно заметить, что для проверки того, что дробная часть числа не меньше 0.5, достаточно рассмотреть только первую цифру сразу после десятичной точки. Если эта цифра равна 5 или больше - мы добавляем 1 к последней цифре целой части числа, и задача решения. Возможно, самым удобным способом обработки входных данных (которые, как было указано в условии, могли быть очень длинными), было использование строковых переменных.
Задача B (div. 2) - Помогите Повару Герасиму
В задаче нужно было аккуратно проверить что требовалось по условию. Прежде всего, проверим, что все объемы компота во входных данных равны - в этом случае выведем "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".
Задача A (div. 1) / C (div. 2) - Помогите Василисе Премудрой
В этой задаче необходимо найти количество различных раскрасок граней куба шестью заданными цветами. Вероятно, самое простое решение данной задачи - как то упорядочить грани (скажем, 0 - передняя, 1 - задняя, 2 - верхняя, 3 - нижняя, 4 - левая, 5 - правая), затем рассмотреть 720 = 6! размещений цветов по граням. Каждое размещение есть некоторая перестановка заданных на входе символов. Для каждого размещения мы находим все 24 возможных вращения куба с заданной раскраской - получаем 24 строки символов Лексикографически минимальная строка будет представителем этой раскраски. Ответ к задаче - количество различных представителей.
Задача B (div. 1) / D (div. 2) - Помогите Царю
К сожалению, первоначальное авторское решение данной задачи оказалось неверным. Однако, оптимальность нижеприведенного алгоритма была показана Knuth и Yao в 1976. Ограничение на n в задаче теперь изменено до 10000.
Процесс бросания монетки и принятия решений относительно того, какую из заданных n альтернатив выбрать может быть естественным образом описан бинарным деревом (возможно, бесконечным). Каждый бросок добавляет две новые ветки из каждой свободной вершины дерева (изначально, дерево состоит из одной свободной вершины). Каждый раз, когда количество свободных вершин становится не меньше n, мы превращаем ровно n свободных вершин в листья (по одному листу на каждую из n альтернатив), и продолжаем процесс с оставшимися свободными вершинами. Например, для n == 3 мы получаем следующее бесконечное бинарное дерево:
o
/ \
o o
/ \ / \
1 2 3 o
/ \
... ...
Теперь наша задача свелась к тому, чтобы посчитать ожидаемую длину случайного пути из корня в какой-нибудь лист в этом дереве. Можно заметить, что дерево рекурсивно: поскольку количество свободных вершин на каждом уровне дерева строго меньше n, ситуация (последовательность "срезаний" - то есть превращения свободных вершин в листья) будет повторяться с периодом не больше n. После того, как мы это заметили, вывести соответствующие формулы не слишком сложно. Поскольку числа в ответе могут быть порядка 2^n, необходимо реализовывать длинную арифметику, или использовать Java.BigInteger.
Задача C (div. 1) / E (div. 2) - Помогите Гному Грише
В этой задаче предполагалось численное решение. Но сначала нужно рассмотреть несколько случаев. Ниже без потери общности мы считаем 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-х часового контеста.
Задача D (div. 1) - Помогите монахам
Эта задача по мотивам известной головоломки "Ханойские башни", в которой диаметры некоторых дисков могут быть равны. Как же ее решить? Хорошая (и в то же время несложная) вещь, которую можно сделать - написать решение 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 тем же самым алгоритмом.
Problem E (div. 1) - Помогите Крокодилу Гене
Эта задача была на оптимальную игру в эту "простую-на-первый-взгляд" игру. Ключевая вещь, которую нужно было понять - это то, что называть только карты, которых у вас нет на руках, не всегда оптимально. Иногда оптимально попытаться обмануть соперника, назвав карту, которая имеется у вас на рука. В этом случае... да, он может подумать, что карта, которую вы назвали - это карта на столе, и проиграть своим следующим ходом. Теперь задача - понять, когда выгодно использовать стратегию уменьшения количества карт соперника, когда - блефовать как описано выше и когда пытаться угадать карту на столе. Но вместо "когда" верный вопрос - "как часто", поскольку перед нами не что иное, как обычная матричная игра с постоянной суммой, и оптимальной стратегией является смесь этих трех стратегий (то есть, на каждом ходу - выбор одной из трех с некоторыми вероятностями). Но сначала сконструируем матрицу. Игрок 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 - первый просто совершает одно верное угадывание.
s = map(int, raw_input().split('.'))
if s[0] % 10 == 9: print('GOTO Vasilisa.')
else: print(s[0] + (str(s[1])[0] >= '5'))
(почему-то в первой правке видно лучше, хотя когда я разместил комментарий, было по-другому)
s = raw_input().split('.')
if s[0][-1] == '9':
elif s[1][0] >= '5':
P.S. Советую ознакомиться с этой штукой http://www.python.org/dev/peps/pep-0008/
Приведение к числу действительно не нужно, но это же удобнее: одна ветка условия становится ненужной.
Со рекомендуемым стилем ещё раз ознакомился, пока что есть привычка писать однокомандые действия в той же строке, эх.
(Am I correct, that with such a strategies infinitely long games are possible, but with the probability 0?)
Maybe I'm missing something, but I still don't understand. Why our position is determined by numbers n and m? We know the history of the moves of our opponent, so we can probably extract some information about his cards from his moves. I can't understand why we can consider a step-by-step game as a game on such a small matrix (as far as I understand, it is a game on matrix of size 3n + m + 1 × 3n + m + 1, rows and columns correspond to strategies). Can you write the proof more clearly? I.e., we need to prove at least that with our strategy like this any other strategy of our opponent would be worse for him (note that his strategy is not necessarily a function , as you assumed, but can be a function (he can use history)).
Another (and more challenging) option is to publish your code and I'll try to write a code for an opponent so that it would play against your strategy better than your strategy itself :)
Кстати, это русская ветка, что я мучаюсь?
Смотри, у тебя в любой момент матричная игра, но состояние тебе известно, будто это игра с полной информацией. Таким образом, ты проводишь расчет, будто это игра с полной информацией, по дереву, т.е. в оптимизации данного момента ты учитываешь ВСЁ будущее, в том числе ВСЕ последствия любого твоего хода.
Приведу небольшой пример.
Мы играем в шахматы, только после каждого хода играем в матричную игру, матрица которой зависит от наличия пешки на a2. Возможным исходом этой игры является убирание с доски пешки a2, продолжение партии, или ничья с последующим распиванием пива. Будем считать, что распивание пива будет при любом исходе, и самоцелью ни одного из участников не является. Ведь понятно, что никакую историю нам помнить не надо, кроме того, что стоит на доске?
Можно считать, что мы поняли, блефует Чебурашка или нет, сразу, как только мы сказали, верим ему или нет. Или Чебурашка упускает мгновенный выигрыш.
Представим, что после каждого ответа "нет" мы играем в "верю - не верю".
Если мы верим противнику, мы мгновенно проверяем карту на столе. Этот случай не ведет к продолжению игры.
Если мы не верим противнику, и мы не угадали, то следующим ходом противник вскроет карту.
Таким образом, мы уже к следующему своему ходу точно будем знать, что это было (если он состоялся - противник блефовал и мы правильно ему не верим).
======================================
Просто любой параметр, который влияет, есть часть состояния игры. Если матричная игра будет зависеть от первого хода партии, надо будет его помнить.
В данном случае утверждается, что состояние этой игры - количество неизвестных карт.
after 6! factorial arrangement how i can figure out the 24 rotations for each lexicographical arrangement.
I am very weak at visualizing cubes symmetry.
can anyone help?
thanks in advance.
For each rotation, we can choose which face to be the "top" face. (6 choices)
Once you choose the top face, the "bottom" face is fixed.
Then, for the "side" faces, there are 4 possible arrangements - namely, rotating the cube along the axis passing through the center of the top face and that of the bottom face, by 0, 90, 180, or 270 degrees. (4 choices)
So, these are the
6 x 4 = 24
rotations.
(Each possible rotation is determined by identifying the top face, and how you perform the 2nd rotation.)
The statement actually writes: two dices, A and B, are defined to be equivalent, if you can (3D-) rotate A in some way, such that A and B looks the same from any viewing angle. And it turns out that, there are 24 ways to rotate A. (see my previous comment)
(*) Imagine now you have a particular dice, A, and now that its six faces are already printed with some fixed colors. You wish to know this dice A is equivalent to which of the remaining 6! - 1 dices. Actually, what you need to do is to rotate dice A using the aforementioned 24 ways, and check against the remaining 6! - 1 dices, to see if A and B matches.
And you do this checking (*) for each of the 6! dice A.
Как доказать, что ходить всегда выгодно? Возможность пропуска хода возникает после блефа у противоположного участника.
Еще не очень хорошо выглядит вопрос, что, когда второй игрок делает выбор в матричной игре, ему известна информация, изменяющая априорные вероятности случаев. Но здесь я пока сам не очень понял, проблема ли это, пытаюсь сам разобраться :)
Это значит, что тестов с очень длинными числами нет в тестсете, или что их вообще нет? Если вообще нет, то почему?
Upd: я всё понял, теперь просто ограничения до 10 000.
Может кто-нибудь объяснить откуда берётся 8/3 в приведённом примере?
Есть ли какая-то литература, статьи, которые близки к этой теме?
Спасибо.
The answer for the DIV2 C question is the same as number of stereoisomers , of different types
deleted