Разбор добавил Александр Чистяков

Помимо двух- и трёхголовых драконов, введём новую породу - одноголовых (такие драконы получаются, если отрубить одну голову у двухголового или две головы у трёхголового).

Пусть в данный момент у нас имеется 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) памяти, что при аккуратном написании удовлетворяет требованиям из условия.