Codeforces Round 925 (Div. 3) |
---|
Закончено |
Саша подарил Ане на День святого Валентина массив $$$a$$$ из $$$n$$$ целых чисел. Ане не нужен этот массив, поэтому она предлагает его уничтожить, сыграв в игру.
Игроки ходят по очереди. Саша джентльмен, поэтому уступает право первого хода Ане.
Пропускать ходы игроки не могут. Игра заканчивается, когда Саша не может сделать ход, то есть после хода Ани осталось ровно одно число. Если это число не меньше $$$10^m$$$ (т.е., $$$\ge 10^m$$$), побеждает Саша. В противном случае побеждает Аня.
Можно показать, что игра всегда закончится. Сообщите, кто выиграет, если оба игрока играют оптимально.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следуют описание наборов.
В первой строке каждого набора даны целые числа $$$n$$$, $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^6$$$) — количество чисел в массиве и параметр, определяющий, когда побеждает Саша.
Во второй строке каждого набора даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив, который Саша подарил Ане.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите:
92 214 23 59 56 14 101 2007 800 15804 55000 123 30 410 106 4 6 2 3 1 10 9 10 71 161 1108 91 2 9 10 10 2 10 24 510 10 10 10
Sasha Anna Anna Sasha Sasha Anna Anna Anna Sasha
Рассмотрим первый набор входных данных.
Аня может развернуть число $$$2$$$, тогда Саша склеит числа $$$2$$$ и $$$14$$$, получив число $$$214$$$, что больше $$$10^2 = 100$$$. Если бы Аня развернула число $$$14$$$, Саша бы склеил числа $$$41$$$ и $$$2$$$, получив число $$$412$$$, что больше $$$10^2 = 100$$$. Других возможных ходов у Ани нет, поэтому она проигрывает.
Название |
---|