{"problem":{"name":"D. Denouncing Mafia","description":{"content":"The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10234D"},"statements":[{"statement_type":"Markdown","content":"The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be an even integer denoting the number of digits in the ticket.  \nLet $ s \\in \\{0,1,\\dots,9,\\texttt{?}\\}^n $ be the ticket string, where $ \\texttt{?} $ denotes an erased digit.  \nLet $ q $ be the number of `?` characters in $ s $, with $ q $ even.  \nPartition $ s $ into two halves:  \n- Left half $ L = s[1:\\frac{n}{2}] $, right half $ R = s[\\frac{n}{2}+1:n] $.  \nLet $ S_L $ be the sum of known digits in $ L $, $ S_R $ the sum of known digits in $ R $.  \nLet $ q_L $ be the number of `?` in $ L $, $ q_R $ the number of `?` in $ R $, so $ q_L + q_R = q $.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 2 \\cdot 10^5 $  \n2. $ q $ is even, $ 0 \\le q \\le n $  \n3. Players alternate turns, Monocarp first. Each turn, a player replaces one `?` with a digit in $ \\{0,1,\\dots,9\\} $.  \n4. Game ends when all `?` are filled.  \n\n**Objective**  \nDetermine the winner under optimal play:  \n- Bicarp wins if $ S_L + \\text{sum of digits added to } L = S_R + \\text{sum of digits added to } R $.  \n- Monocarp wins otherwise.  \n\nLet $ d = S_R - S_L $ be the initial difference.  \nLet $ x $ be the total sum added to $ L $, $ y $ the total sum added to $ R $.  \nBicarp wins iff $ x - y = d $.  \nTotal moves: $ q $, Monocarp makes $ \\frac{q}{2} $ moves, Bicarp makes $ \\frac{q}{2} $ moves.  \nMonocarp controls $ \\frac{q_L + q_R}{2} $ moves total, but can choose any `?` position.  \nBicarp responds optimally.  \n\n**Key Insight**  \nThe game reduces to:  \n- Monocarp aims to prevent $ x - y = d $.  \n- Bicarp aims to achieve $ x - y = d $.  \n- Each player chooses a position (left or right) and assigns a digit 0–9.  \n\nDefine:  \n- $ a = q_L $, $ b = q_R $, so $ a + b = q $.  \n- Let $ m = \\frac{q}{2} $: each player makes $ m $ moves.  \n\nMonocarp can choose to play on left or right; Bicarp responds.  \nBicarp wins if and only if:  \n$$\nd = \\frac{9}{2}(b - a)\n$$  \nand both players play optimally.  \n\n**Final Condition**  \nBicarp wins if and only if:  \n$$\nS_R - S_L = \\frac{9}{2}(q_L - q_R)\n$$  \nOtherwise, Monocarp wins.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10234D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}