Косточки для Шарика 2
Косточки для Шарика 2
Рисунок Шишко Марины - 12.05.2010, 9 кл.
Наконец-то Печкин начал приносить для Шарика обещанные косточки... Так как косточек было много, а приближалась зима, Шарик начал складировать их по кучкам, причем в каждой кучке не более 100 косточек, а всего кучек не более, чем 10000.
"Замяучили меня эти споры по поводу двоичной или троичной логики" - подумал Матроскин, - "ведь все-равно троичную можно свести к двоичной", решил умный кот и тут же придумал новую игру. Он пронумеровал все кучки подряд и предложить Шарику не просто сидеть и ждать очередного прихода Печкина, а поиграть с ним в такую игру. Ходят по очереди, но Матроскин всегда первым. Игрок, делающий ход, сначала выбирает кучку с количеством косточек A, а потом B, соблюдая следующие требования:
Кучка A должна быть не пустой.
Кучка B должна быть строго меньше за A.
Кучка B также должна быть не пустой.
Обязательно должны выполнятся условия, что суммарно количество A + B не делится нацело на 2 и делится нацело на 3 (к вопросу о двоичной и троичной логиках... :) ).
Из кучки B взять произвольное, но больше нуля количество косточек.
Кто не смог сделать ход - тот проиграл.
Кто выигрывает в этой игре при оптимальной стратегии обеих игроков?
Giriş verilənləri
В первой строке задано количество игр между Матроскиным и Шариком за день T (1 ≤ T ≤ 100). Далее идет T строк, в каждой из которых сначала задано количество кучек N, а потом N чисел, определяющих количество косточек в соответсвующей кучке.
Çıxış verilənləri
Вывести одну строку, состоящую из последовательности T единиц или двоек: 1 - если выиграл Матроскин, 2 - Шарик.
Nümunə
2 2 1 2 7 1 3 3 2 2 1 2
12