Pinely Round 4 (Div. 1 + Div. 2) |
---|
Закончено |
Алиса и Боб играют в игру с $$$n$$$ кучками камней, где $$$i$$$-я кучка содержит $$$a_i$$$ камней. Игроки делают ходы по очереди, причем Алиса ходит первой.
На каждом ходу игрок выполняет следующие три шага:
Игрок, который не сможет сделать ход, проигрывает.
Определите, кто выиграет, если оба игрока играют оптимально.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество куч камней.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — количество камней в кучах.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите «Alice» (без кавычек), если Алиса выиграет, и «Bob» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «alIcE», «Alice» и «alice» будут считаться одинаковыми.
422 133 5 744 6 8 1058 8 8 8 8
Bob Alice Alice Bob
В первом наборе входных данных есть $$$2$$$ кучи камней с количествами камней $$$2$$$ и $$$1$$$ соответственно. Поскольку ни $$$1$$$, ни $$$2$$$ не могут быть разделены на два простых числа, Алиса не может сделать ход, поэтому Боб выигрывает.
Во втором наборе входных данных есть $$$3$$$ кучи камней с $$$3$$$, $$$5$$$ и $$$7$$$ камнями соответственно. Алиса может выбрать $$$k = 1$$$, удалить кучу из $$$7$$$ камней, а затем разделить кучу из $$$5$$$ камней на две кучи камней с простыми количествами $$$2$$$ и $$$3$$$. В итоге получится $$$3$$$ кучки камней с $$$3$$$, $$$2$$$ и $$$3$$$ камнями соответственно, в результате чего у Боба не остается ни одного допустимого хода, и Алиса выигрывает.
В третьем наборе входных данных есть $$$4$$$ кучи камней с $$$4$$$, $$$6$$$, $$$8$$$ и $$$10$$$ камнями соответственно. Алиса может выбрать $$$k = 2$$$ и удалить две кучи камней $$$8$$$ и $$$10$$$. Далее она делит кучу камней $$$4$$$ на две кучи камней с простыми количествами $$$2$$$ и $$$2$$$, а кучу камней $$$6$$$ — на две кучи камней $$$3$$$ и $$$3$$$. После этого у Боба не остается допустимых ходов, и Алиса выигрывает.
В четвертом наборе входных данных есть $$$5$$$ куч камней, каждая из которых содержит $$$8$$$ камней. Можно показать, что если оба игрока играют оптимально, то победит Боб.
Название |
---|