Помогите разобраться с олимпиадной задачей

Условие задачи (для Ъ, которые не ходят по ссылкам):

Саруман Белый и Гэндальф Серый решили сыграть в игру. Победителю достаётся Кольцо Всевластия. Перед игроками лежат кольца, соединённые в K цепочек. Для каждого кольца известно содержание золота в нём в процентах — целое число от 1 до 100. Ходят по очереди. За ход разрешается выбрать одну из цепочек и какое-то кольцо из этой цепочки и дематериализовать все кольца из данной цепочки с процентным содержанием золота не больше, чем у выбранного. При этом, понятно, цепочка может распасться на несколько. Игра продолжается на оставшихся цепочках. Тот, кто дематериализовал последнее кольцо, выиграл. Первым ходит Гэндальф. Определите, может ли Гэндальф выиграть и, если может, какой первый ход он должен для этого сделать.

Исходные данные

В первой строке дано целое число K (1 ≤ K ≤ 50). В следующих K строках приведены описания цепочек в следующем формате: сперва дана длина цепочки — целое число от 1 до 100, затем — процентные содержания золота в кольцах цепочки. Числа в строке разделены пробелом.

Результат

Выведите «S», если Кольцо Всевластия достанется Саруману. В противном случае выведите в первой строке «G», а во второй пару чисел, описывающих выигрышный первый ход Гэндальфа — номер цепочки и номер кольца в ней. Цепочки и кольца внутри цепочек нумеруются с 1. Если существует несколько выигрышных первых ходов, выведите ход с наименьшим номером цепочки, если и таких несколько — с наименьшим номером кольца.

НИМ, конечно же, уже рассматривал?

Рассматривал, конечно же.

Пока пришла только одна идея: прямое применение теории Спрага-Гранди

И даже решение нимообразное написал: http://pastebin.com/6msDF1i7

но оно при тех ограничениях обламывается на 6 тесте

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

Не канает. Не всегда игровую сумму можно свести к нулю, нужен перебор.

> Определите, может ли Гэндальф выиграть и, если может, какой первый ход он должен для этого сделать.

Позвать Фродо и ко.

Динамическое программирование по парам индексов начального и конечного элементов цепочки, ИМХО.