1033C.md (2414B)
1 Source: https://codeforces.com/problemset/problem/1033/C 2 3 C. Permutation Game 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 After a long day, Alice and Bob decided to play a little game. The game board consists of $n$ cells in a straight line, numbered from $1$ to $n$, where each cell contains a number $a_i$ between $1$ and $n$. Furthermore, no two cells contain the same number. 22 23 A token is placed in one of the cells. They take alternating turns of moving the token around the board, with Alice moving first. The current player can move from cell $i$ to cell $j$ only if the following two conditions are satisfied: 24 25 * the number in the new cell $j$ must be strictly larger than the number in the old cell $i$ (i.e. $a_j \gt a_i$), and 26 * the distance that the token travels during this turn must be a multiple of the number in the old cell (i.e. $|i-j|\bmod a_i = 0$). 27 28 Whoever is unable to make a move, loses. For each possible starting position, determine who wins if they both play optimally. It can be shown that the game is always finite, i.e. there always is a winning strategy for one of the players. 29 30 Input 31 32 The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of numbers. 33 34 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). Furthermore, there are no pair of indices $i \neq j$ such that $a_i = a_j$. 35 36 Output 37 38 Print $s$ — a string of $n$ characters, where the $i$-th character represents the outcome of the game if the token is initially placed in the cell $i$. If Alice wins, then $s_i$ has to be equal to "A"; otherwise, $s_i$ has to be equal to "B". 39 40 Examples 41 42 Input 43 44 ``` 45 8 46 3 6 5 4 2 7 1 8 47 ``` 48 49 Output 50 51 ``` 52 BAAAABAB 53 ``` 54 55 Input 56 57 ``` 58 15 59 3 11 2 5 10 9 7 13 15 8 4 12 6 1 14 60 ``` 61 62 Output 63 64 ``` 65 ABAAAABBBAABAAB 66 ``` 67 68 Note 69 70 In the first sample, if Bob puts the token on the number (not position): 71 72 * $1$: Alice can move to any number. She can win by picking $7$, from which Bob has no move. 73 * $2$: Alice can move to $3$ and $5$. Upon moving to $5$, Bob can win by moving to $8$. If she chooses $3$ instead, she wins, as Bob has only a move to $4$, from which Alice can move to $8$. 74 * $3$: Alice can only move to $4$, after which Bob wins by moving to $8$. 75 * $4$, $5$, or $6$: Alice wins by moving to $8$. 76 * $7$, $8$: Alice has no move, and hence she loses immediately.