Помимо двух- и трёхголовых драконов, введём новую породу - одноголовых (такие драконы получаются, если отрубить одну голову у двухголового или две головы у трёхголового).
Пусть в данный момент у нас имеется A - одноголовых драконов, B - двухголовых и C - трёхголовых.
Отметим, что каждая тройка чисел (A,B,C) однозначно задаёт: выиграем мы, стартуя из этой позиции, или проиграем.
Если все три числа равны 0, то в этой позиции мы проиграли (противник уже успел перерубить оставшихся драконов).
Иначе есть несколько возможных вариантов развития событий:
Если A > 0
можно перейти в (A-1,B,C) //Отрубаем 1 голову у одноголового
Если B > 0
можно перейти в (A+1,B-1,C) //Отрубаем 1 голову у двухглавого
можно перейти в (A,B-1,C) //Отрубаем 2 головы у двухглавого
Если С > 0
можно перейти в (A,B+1,C-1) //Отрубаем 1 голову у трёхглавого
можно перейти в (A+1,B,C-1) //Отрубаем 2 головы у трёхглавого
можно перейти в (A,B,C-1) //Отрубаем 3 головы у трёхглавого
Если хотя бы в одном из рассмотренных случаев нам удастся перейти в проигрышное положение, то это значит, что текущая позиция выигрышная для богатыря (он сможет перевести противника в заведомо проигрышное положение), в противном случае - он сам проиграл.
Создадим трёхмерный массив W размерами [N+M+1][N+1][M+1], описывающий состояние для данного количества драконов, где в ячейке W[i][j][k] хранится
1, если начиная из такой позиции богатырь выигрывает
-1, если проигрывает
0, если результат для данной ячейки ещё не определён.
(Из-за маленького объёма предоставляемой памяти размер ячейки массива не должен превышать 1 байта).
Как мы уже отметили W[0][0][0] = -1.
Так как суммарное количество голов у драконов конечно, и после каждого удара богатыря оно уменьшается, то рано или поздно кто-то из богатырей окажется в этой позиции. Следовательно запустив рекурсивно функцию заполнения массива по описанному выше алгоритму мы сможем определить выигрышность или проигрышность исходной позиции W[0][N][M].
Таким образом, если после заполнения массива W[0][N][M] равно 1, то выигрывает первый богатырь, иначе - второй.
Чтобы вывести удовлетворяющие начальные ходы надо ещё раз просмотреть содержимое ячеек, описывающих события, возможно, следующие за исходным и вывести описание ударов, переводящих противника в проигрышное положение.
Сложность программы: так как, узнав значение для ячейки W[i][j][k] мы больше его не пересчитываем и 0 <= i <= N+M, 0 <= j <= N, 0 <= k <= M, то всего придётся обрабатывать не более (N+M)*N*M следовательно данная программа требует O((N+M)*N*M) времени и
O((N+M)*N*M) памяти, что при аккуратном написании удовлетворяет требованиям из условия.
Алеша Попович и Добрыня Никитич сражаются со стаей двух- и трехголовых драконов. Они по очереди взмахивают мечами, и одним махом могут отрубить любое (по своему желанию) число голов, но только у одного дракона. Отрубивший последнюю голову у последнего дракона получает в жены прекрасную принцессу.
Кто из богатырей (начинающий или второй) может получить в жены принцессу независимо от действий другого?
Входные данные
Во входном файле записано два числа N и M — количество двух- и трехголовых драконов соответственно (оба числа целые из диапазона от 0 до 100).
Выходные данные
В выходной файл выведите сначала число 1 или 2 определяющее, кто из богатырей имеет все шансы получить в жены принцессу (1 — тот, кто начинает, 2 — второй). В случае 1 выведите также все варианты его первого хода, которые к этому приводят: сначала выведите количество различных выигрышных ходов (при этом отрубание одинакового количества голов у разных двухголовых драконов считается одним и тем же ходом, так же и для трехголовых), а затем сами ходы. Каждый ход задается парой чисел: первое число определяет у сколькиголового дракона нужно отрубать головы, а второе — сколько голов нужно отрубать.