{"problem":{"name":"B. Scapegoat","description":{"content":"Aori is very careless so she is always making troubles. One day she does it again, with N big troubles! But this time she seems to be at ease because she has found M Inklings to take all the blames. E","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10177B"},"statements":[{"statement_type":"Markdown","content":"Aori is very careless so she is always making troubles. One day she does it again, with N big troubles! But this time she seems to be at ease because she has found M Inklings to take all the blames. Each trouble can be measured by a severity number ai. Each trouble needs at least one Inkling to take the blame, and each Inkling can help Aori to take the blame for exactly one trouble. If two or more Inklings take the same trouble, they will take this blame together and discuss how to divide this trouble into.. some trivial things.. to reduce the pressure on each Inkling, as long as the total severity on Inklings is equal to the severity of this trouble.\n\nInklings are so warm so that Aori wants to think a way to let the variance of severity on each Inkling to be minimal. Could you help Aori make her scapegoats?\n\nFormally, the variance of variables is the expectation of the squared deviation of a variable from its mean:\n\nThe first line of the input gives the number of test cases, T. T test cases follow.\n\nFor each test case, the first line contains two integers N and M, where N is the number of troubles, and M is the number of Inklings. The next line contains N integers a1, a2, ..., aN representing the severity of the troubles that Aori makes.\n\nFor each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1) and _y_ is the minimal variance.\n\n_y_ will be considered correct if it is within an absolute or relative error of 10 - 8 of the correct answer.\n\nFor the first sample, Aori can let one Inkling to take the first trouble's blame, two Inklings for the second, and three Inklings for the third. The severity on each Inkling is 1 unit, so their variance should be 0.\n\n## Input\n\nThe first line of the input gives the number of test cases, T. T test cases follow.For each test case, the first line contains two integers N and M, where N is the number of troubles, and M is the number of Inklings. The next line contains N integers a1, a2, ..., aN representing the severity of the troubles that Aori makes.  1 ≤ T ≤ 100.  1 ≤ N ≤ M ≤ 2 × 105.  1 ≤ ai ≤ 10000.  . \n\n## Output\n\nFor each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1) and _y_ is the minimal variance._y_ will be considered correct if it is within an absolute or relative error of 10 - 8 of the correct answer.\n\n[samples]\n\n## Note\n\nFor the first sample, Aori can let one Inkling to take the first trouble's blame, two Inklings for the second, and three Inklings for the third. The severity on each Inkling is 1 unit, so their variance should be 0.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ n_k \\in \\mathbb{Z}^+ $ be the number of elements and $ a_k \\in \\mathbb{Z}^+ $ be the required average.\n\n**Constraints**  \n1. $ 1 \\le T \\le 10^5 $  \n2. For each $ k $: $ 1 \\le n_k, a_k \\le 10^9 $\n\n**Objective**  \nFor each test case $ k $, find the maximum number of distinct positive integers in a multiset $ S_k = \\{x_1, x_2, \\dots, x_{n_k}\\} $ such that:  \n$$\n\\frac{1}{n_k} \\sum_{i=1}^{n_k} x_i = a_k\n$$  \ni.e., $ \\sum_{i=1}^{n_k} x_i = n_k a_k $, and $ x_i \\in \\mathbb{Z}^+ $ for all $ i $.  \n\nMaximize $ |\\{x_1, x_2, \\dots, x_{n_k}\\}| $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10177B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}