DMOPC '22 Contest 4 P5 - Blackboard Game

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Alice and Bob are playing a game. At first, there are N positive integers written on the blackboard. They then take turns making a move, with Alice going first, which consists of the following: choose any integer X on the blackboard, erase X, and write 2 positive integers Y and Z on the blackboard, such that Y \cdot Z=X and \gcd(Y,Z) > 1. The first player who is unable to make a move loses. Find who wins the game if both players play optimally.


1 \le N \le 5\,000

2 \le A_i \le 10^{12}

Subtask 1 [10%]

A_i is a power of 2.

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line contains the integer N.

The next line contains N space-separated integers, representing the list A of positive integers initally written on the blackboard.

Output Specification

Output ALICE if Alice wins, otherwise output BOB.

Sample Input

36 72 108

Sample Output



There are no comments at the moment.