2123D.md (2315B)
1 Source: https://codeforces.com/problemset/problem/2123/D 2 3 D. Binary String Battle 4 5 time limit per test 6 7 2 seconds 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 Alice and Bob are given a binary string $s$ of length $n$, and an integer $k$ ($1\leq k \lt n$). 22 23 Alice wins if she is able to transform all characters of $s$ into zeroes. If Alice is unable to win in a finite number of moves, then Bob wins. 24 25 Alice and Bob take turns, with Alice going first. 26 27 * On Alice's turn, she may choose any subsequence$^{\text{∗}}$ of length $k$ in $s$, then set all characters in that subsequence to zero. 28 * On Bob's turn, he may choose any substring$^{\text{†}}$ of length $k$ in $s$, then set all characters in that substring to one. 29 30 Note that Alice wins if the string consists of all zeros at any point during the game, including in between Alice's and Bob's turns. 31 32 Determine who wins with optimal play. 33 34 $^{\text{∗}}$A subsequence of a string $s$ is a set of characters in $s$. Note that these characters do not have to be adjacent. 35 36 $^{\text{†}}$A substring of a string $s$ is a contiguous group of characters in $s$. Note that these characters must be adjacent. 37 38 Input 39 40 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 41 42 The first line of each test case contains two integers $n$ and $k$ ($2\leq n \leq 2\cdot 10^5$, $1\leq k \lt n$). 43 44 The second line of each test case contains a binary string $s$ of length $n$. 45 46 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 47 48 Output 49 50 For each test case, output on a single line "Alice" if Alice wins with optimal play, and "Bob" if Bob wins with optimal play. 51 52 You can output the answer in any case (upper or lower). For example, the strings "aLiCe", "alice", "ALICE", and "alICE" will be recognized as "Alice". 53 54 Example 55 56 Input 57 58 ``` 59 6 60 61 5 2 62 63 11011 64 65 7 4 66 67 1011011 68 69 6 1 70 71 010000 72 73 4 1 74 75 1111 76 77 8 3 78 79 10110110 80 81 6 4 82 83 111111 84 ``` 85 86 Output 87 88 ``` 89 Bob 90 Alice 91 Alice 92 Bob 93 Bob 94 Alice 95 ``` 96 97 Note 98 99 In the third sample, Alice can choose the subsequence consisting of $s_2$, turning $s$ into $000000$. Then she wins immediately. 100 101 In the fourth sample, it can be shown that there is no way for Alice to guarantee that she can turn $s$ into $0000$ within a finite number of moves.