DMOPC '22 Contest 4 P5 - Blackboard Game

View as PDF

Submit solution


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

Author:
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.

Constraints

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

3
36 72 108

Sample Output

ALICE

Comments

There are no comments at the moment.