2255A.md (3557B)
1 Source: https://codeforces.com/problemset/problem/2255/A 2 3 A. Hot Potatoes at the Fairy Warehouse 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 On a quiet afternoon at the Fairy Warehouse, Ithea gathers Chtholly, Nephren, and the other leprechauns for one last game before dinner: Hot Potatoes. 22 23 There are $2n$ leprechauns sitting in a circle, numbered from $1$ to $2n$ clockwise. They are divided into two teams: leprechauns with odd numbers belong to the Red Team, while those with even numbers belong to the Blue Team. 24 25 Initially, some leprechauns hold a potato. The game then lasts for $k$ rounds. 26 27 At the beginning of each round, both teams know the current positions of all potatoes. Then, simultaneously, every leprechaun holding a potato does exactly one of the following: 28 29 * Keep the potato, or 30 * Pass the potato to the next leprechaun clockwise, provided that the next leprechaun does not hold a potato at the beginning of the round. 31 32 If the next leprechaun holds a potato at the beginning of the round, the current holder must keep their potato. Whether a potato can be passed depends only on the positions of the potatoes at the beginning of the round. 33 34 Under these rules, every leprechaun holds at most one potato at any time. 35 36 When all $k$ rounds are over, the final bell rings. Every leprechaun still holding a potato is eliminated from the game. The score of each team is defined as the number of eliminated leprechauns on the other team. All members of each team cooperate and share all available information to maximize their team's score. 37 38 Find the scores of the Red Team and the Blue Team if both teams play optimally. It can be shown that the scores under optimal play are uniquely determined. 39 40 Input 41 42 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 43 44 The first line of each test case contains two integers $n$ and $k$ ($1\le n\le 10^5$, $1\le k\le 10^9$) — half the number of leprechauns and the number of rounds. 45 46 The second line contains a binary string $s$ of length $2n$ ($s_i=\texttt{0}$ or $\texttt{1}$) describing the initial state of the game. If $s_i=\texttt{1}$, leprechaun $i$ initially holds a potato; otherwise, they do not. 47 48 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 49 50 Output 51 52 For each test case, print two integers — the scores of the Red Team and the Blue Team, respectively, if they play optimally. 53 54 Example 55 56 Input 57 58 ``` 59 6 60 61 2 1 62 63 1000 64 65 2 1 66 67 0011 68 69 3 2 70 71 101110 72 73 5 100000 74 75 1111111111 76 77 5 100000 78 79 0000000000 80 81 7 4 82 83 10011110101011 84 ``` 85 86 Output 87 88 ``` 89 1 0 90 91 0 2 92 93 3 1 94 95 5 5 96 97 0 0 98 99 7 2 100 ``` 101 102 Note 103 104 In the first test case, it is optimal for leprechaun $1$ to pass the potato to leprechaun $2$ in the only round. Afterwards, only leprechaun $2$, who belongs to the Blue Team, holds a potato. Therefore, the score of the Red Team is $1$, while the score of the Blue Team is $0$. 105 106 In the second test case, it is optimal for leprechaun $4$ to pass their potato to leprechaun $1$ in the only round. Note that leprechaun $3$ cannot pass their potato to leprechaun $4$, because leprechaun $4$ already holds a potato at the beginning of the round. 107 108 Here is a demonstration for the third test case: 109 110  111 112 Note that this is one possible optimal strategy for both teams. Other optimal strategies may exist, but the resulting scores are the same.