codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.