{"problem":{"name":"C. Cow run","description":{"content":"Farmer John and Bessie have devised a new exercise game for the cows. The cows are running on a circular track of length M (2 ≤ M ≤ 109) starting from the same position. The game proceeds in N (1 ≤ N ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10020C"},"statements":[{"statement_type":"Markdown","content":"Farmer John and Bessie have devised a new exercise game for the cows. The cows are running on a circular track of length M (2 ≤ M ≤ 109) starting from the same position. The game proceeds in N (1 ≤ N ≤ 14) rounds using a deck of 8N cards each with a number Xi (0 ≤ Xi < M) written on it.\n\nEach round FJ moves the top 8 cards into a separate pile and selects either the top 4 or bottom 4 cards for Bessie to play with. Bessie then chooses either the top 2 cards or bottom 2 cards of the 4 cards FJ selected. After this FJ calls out the number on the top card, Xtop, and the cows run a distance of R·Xtop, where R is the total distance the cows have run so far. Bessie then calls out the number on the bottom card, Xbottom, and the cows run a distance of Xbottom. \n\nFJ is concerned that after the exercise the cows will be too tired to get back to the beginning of the track if they end up too far away. He believes if the cows end up more than a distance of K (0 ≤ K ≤ ⌊ M / 2⌋) from their starting position they won't be able to get back home. \n\nIt is guaranteed that if FJ plays correctly, he will always be able to ensure the cows can come home, irrespective of the moves made by Bessie! For each round, your task is to determine which half of the cards FJ should choose such that no matter what Bessie does from that point on, FJ can always get the cows home. Bessie will then make the move provided in the input and you can then continue onto the next round. Note that even though Bessie's moves are provided to you in the input, you are to specify moves for FJ that would have worked no matter what Bessie chooses (so it is effectively as if FJ does not really know what Bessie will do during her moves).\n\nLine 1: Three space-separated integers N, M, K \n\nLine 2: A string of N characters. If the i-th character is 'T', it means Bessie will select the top 2 cards in the i-th round. Otherwise, the i-th character will be 'B' to indicate Bessie will select the bottom 2 cards in the i-th round.\n\nLines 3..N + 2: Each line contains eight integers representing the 8 cards to be used that round from top to bottom.\n\nA string of N characters where the i-th character is 'T' if FJ should choose the top 4 cards or 'B' if FJ should choose the bottom 4 cards in the ith round. If there are multiple ways to get the cows home, choose the lexicographically first (that is, the string that is alphabetically smallest). \n\nThe cows must end up exactly where they started to be able to come home. Note that FJ is not aware of what choices Bessie is going to make beforehand. If FJ did know, he could have chosen the bottom half each time.\n\n## Input\n\nLine 1: Three space-separated integers N, M, K Line 2: A string of N characters. If the i-th character is 'T', it means Bessie will select the top 2 cards in the i-th round. Otherwise, the i-th character will be 'B' to indicate Bessie will select the bottom 2 cards in the i-th round.Lines 3..N + 2: Each line contains eight integers representing the 8 cards to be used that round from top to bottom.\n\n## Output\n\nA string of N characters where the i-th character is 'T' if FJ should choose the top 4 cards or 'B' if FJ should choose the bottom 4 cards in the ith round. If there are multiple ways to get the cows home, choose the lexicographically first (that is, the string that is alphabetically smallest). \n\n[samples]\n\n## Note\n\nThe cows must end up exactly where they started to be able to come home. Note that FJ is not aware of what choices Bessie is going to make beforehand. If FJ did know, he could have chosen the bottom half each time.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $, $ M \\in \\mathbb{Z}^+ $, $ K \\in \\mathbb{Z}_{\\ge 0} $ with $ 1 \\le N \\le 14 $, $ 2 \\le M \\le 10^9 $, $ 0 \\le K \\le \\lfloor M/2 \\rfloor $.  \nLet $ B = b_1 b_2 \\dots b_N \\in \\{T, B\\}^N $ be the sequence of Bessie’s fixed choices per round.  \nFor each round $ i \\in \\{1, \\dots, N\\} $, let $ C_i = (x_{i,1}, x_{i,2}, \\dots, x_{i,8}) \\in [0, M)^8 $ be the sequence of 8 card values from top to bottom.\n\nLet $ R_0 = 1 $, and for $ i \\ge 1 $, define $ R_i $ as the cumulative multiplier after round $ i $, updated as:  \n- If FJ chooses top 4: $ R_i = R_{i-1} \\cdot x_{i,1} + x_{i,4} $  \n- If FJ chooses bottom 4: $ R_i = R_{i-1} \\cdot x_{i,5} + x_{i,8} $  \n(Bessie’s choice then determines the final distance multiplier in round $ i $:  \n- If $ b_i = T $: $ D_i = R_{i-1} \\cdot x_{i,1} + x_{i,2} $  \n- If $ b_i = B $: $ D_i = R_{i-1} \\cdot x_{i,4} + x_{i,3} $)  \n\nLet $ D_i \\mod M $ be the position of the cows after round $ i $.\n\n**Constraints**  \n1. $ R_0 = 1 $  \n2. After all $ N $ rounds, the final position $ D_N \\mod M $ must satisfy $ D_N \\equiv 0 \\pmod{M} $ (i.e., back to start).  \n3. FJ must choose for each round $ i $: either top 4 or bottom 4, **without knowing** Bessie’s future choices, but **guaranteeing** that **no matter** what Bessie does in all future rounds, a sequence of choices exists to reach $ D_N \\equiv 0 \\pmod{M} $.  \n4. Bessie’s choices $ b_i $ are known in advance and fixed.  \n5. Among all valid FJ sequences, choose the lexicographically smallest (i.e., prioritize 'T' over 'B').\n\n**Objective**  \nFind the lexicographically smallest string $ F = f_1 f_2 \\dots f_N \\in \\{T, B\\}^N $ such that:  \nFor each $ i \\in \\{1, \\dots, N\\} $,  \n- If $ f_i = T $, then the top 4 cards $ (x_{i,1}, x_{i,2}, x_{i,3}, x_{i,4}) $ are selected;  \n- If $ f_i = B $, then the bottom 4 cards $ (x_{i,5}, x_{i,6}, x_{i,7}, x_{i,8}) $ are selected;  \nand for **every possible** sequence of Bessie’s choices consistent with $ b_1, \\dots, b_N $, the resulting final position $ D_N \\equiv 0 \\pmod{M} $.\n\n(Note: Since Bessie’s choices are fixed and known, the only uncertainty is in FJ’s choices — but FJ must commit to a choice per round such that **all possible future paths** (i.e., the fixed Bessie moves) lead to $ D_N \\equiv 0 \\pmod{M} $. This is a backward dynamic programming problem over the rounds.)\n\n**Formal Objective (Backward DP)**  \nDefine $ \\text{dp}[i][r] $: whether it is possible, from round $ i $ onward, to reach $ D_N \\equiv 0 \\pmod{M} $ given current multiplier $ r \\equiv R_{i-1} \\pmod{M} $.  \nWe compute backwards from $ i = N $ to $ i = 1 $.  \nFor each round $ i $, for each possible $ r \\in \\mathbb{Z}_M $,  \n- If FJ chooses **top 4**:  \n  - Bessie chooses $ b_i $:  \n    - If $ b_i = T $: next multiplier = $ r \\cdot x_{i,1} + x_{i,2} $  \n    - If $ b_i = B $: next multiplier = $ r \\cdot x_{i,1} + x_{i,3} $  \n  - So the resulting multipliers are $ m_1 = r \\cdot x_{i,1} + x_{i,2} $, $ m_2 = r \\cdot x_{i,1} + x_{i,3} $  \n  - Then we require $ \\text{dp}[i+1][m_1] \\land \\text{dp}[i+1][m_2] $ to be true  \n- If FJ chooses **bottom 4**:  \n  - Bessie chooses $ b_i $:  \n    - If $ b_i = T $: next multiplier = $ r \\cdot x_{i,5} + x_{i,6} $  \n    - If $ b_i = B $: next multiplier = $ r \\cdot x_{i,5} + x_{i,7} $  \n  - So multipliers: $ m_3 = r \\cdot x_{i,5} + x_{i,6} $, $ m_4 = r \\cdot x_{i,5} + x_{i,7} $  \n  - Require $ \\text{dp}[i+1][m_3] \\land \\text{dp}[i+1][m_4] $  \n\nBase case: $ \\text{dp}[N+1][r] = \\text{true} $ iff $ r \\equiv 0 \\pmod{M} $\n\nWe compute $ \\text{dp}[i][r] $ backwards, and for each round, pick the lexicographically smallest option ('T' before 'B') that leads to a valid continuation.\n\n**Output**: The string $ F $ of length $ N $, where each $ f_i \\in \\{T, B\\} $ is chosen greedily lexicographically (T first) such that the backward DP condition holds.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10020C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}