{"problem":{"name":"G. Coin Game","description":{"content":"Alice and Bob are very smart guys and they like to play all kinds of games in their spare time. The most amazing thing is that they always find the best strategy, and that's why they feel bored again ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10053G"},"statements":[{"statement_type":"Markdown","content":"Alice and Bob are very smart guys and they like to play all kinds of games in their spare time. The most amazing thing is that they always find the best strategy, and that's why they feel bored again and again. They just invented a new game, as they usually did.   They are playing with coins. They have a row of $1 and $2 coins. They want to change this row so that all $1's are grouped together and all $2's are grouped together. They are just allowed to swap two neighbor coins.   Using the best strategy what is the minimum number of swaps required to do this task?\n\nEach test case is a line with a string composed of 1 and 2.   (1 ≤ length of the input string ≤ 25000)\n\nPrint the minimum number of swaps required to do this task.\n\n## Input\n\nEach test case is a line with a string composed of 1 and 2.   (1 ≤ length of the input string ≤ 25000)\n\n## Output\n\nPrint the minimum number of swaps required to do this task.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\{1, 2\\}^* $ be a string of length $ n $, representing a sequence of coins of denomination 1 or 2.\n\n**Constraints**  \n$ 1 \\leq n \\leq 25000 $\n\n**Objective**  \nCompute the minimum number of adjacent swaps required to group all 1s together and all 2s together (i.e., to obtain a string of the form $ 1^*2^* $ or $ 2^*1^* $).\n\nLet $ c_1 $ be the number of 1s in $ s $, and $ c_2 = n - c_1 $ the number of 2s.  \nThe target configurations are:  \n- $ 1^{c_1}2^{c_2} $  \n- $ 2^{c_2}1^{c_1} $\n\nDefine:  \n- $ S_1 $: minimum adjacent swaps to transform $ s $ into $ 1^{c_1}2^{c_2} $  \n- $ S_2 $: minimum adjacent swaps to transform $ s $ into $ 2^{c_2}1^{c_1} $\n\nThen the answer is:  \n$$\n\\min(S_1, S_2)\n$$\n\nWhere:  \n- $ S_1 = \\sum_{i: s_i = 2} \\left( \\text{number of 1s to the left of position } i \\right) $  \n- $ S_2 = \\sum_{i: s_i = 1} \\left( \\text{number of 2s to the left of position } i \\right) $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10053G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}