eolymp
bolt
Try our new interface for solving problems
Məsələlər

Косточки для Шарика 2

Косточки для Шарика 2

Zaman məhdudiyyəti 10 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Рисунок Шишко Марины - 12.05.2010, 9 кл.

Наконец-то Печкин начал приносить для Шарика обещанные косточки... Так как косточек было много, а приближалась зима, Шарик начал складировать их по кучкам, причем в каждой кучке не более 100 косточек, а всего кучек не более, чем 10000.

"Замяучили меня эти споры по поводу двоичной или троичной логики" - подумал Матроскин, - "ведь все-равно троичную можно свести к двоичной", решил умный кот и тут же придумал новую игру. Он пронумеровал все кучки подряд и предложить Шарику не просто сидеть и ждать очередного прихода Печкина, а поиграть с ним в такую игру. Ходят по очереди, но Матроскин всегда первым. Игрок, делающий ход, сначала выбирает кучку с количеством косточек A, а потом B, соблюдая следующие требования:

  • Кучка A должна быть не пустой.

  • Кучка B должна быть строго меньше за A.

  • Кучка B также должна быть не пустой.

  • Обязательно должны выполнятся условия, что суммарно количество A + B не делится нацело на 2 и делится нацело на 3 (к вопросу о двоичной и троичной логиках... :) ).

  • Из кучки B взять произвольное, но больше нуля количество косточек.

  • Кто не смог сделать ход - тот проиграл.

Кто выигрывает в этой игре при оптимальной стратегии обеих игроков?

Giriş verilənləri

В первой строке задано количество игр между Матроскиным и Шариком за день T (1T100). Далее идет T строк, в каждой из которых сначала задано количество кучек N, а потом N чисел, определяющих количество косточек в соответсвующей кучке.

Çıxış verilənləri

Вывести одну строку, состоящую из последовательности T единиц или двоек: 1 - если выиграл Матроскин, 2 - Шарик.

Nümunə

Giriş verilənləri #1
2
2 1 2
7 1 3 3 2 2 1 2
Çıxış verilənləri #1
12