codeforces-scrape

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

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  ![](https://espresso.codeforces.com/45e2b71b9979cdb65198a6b629b54f7d540750ef.png) 
    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.