codeforces-scrape

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

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.