{"trustable":false,"sections":[{"title":"statement","value":{"format":"MD","content":"The Burger King owns several restaurants along a highway. Recently, they have decided to build several depots along the highway, each one located at a restaurant and supplying several of the restaurants with the needed ingredients. Naturally, these depots should be placed so that the average distance between a restaurant and its assigned depot is minimized. You are to write a program that computes the optimal positions and assignments of the depots.\n\nTo make this more precise, the management of Burger King has issued the following specification:\n\nYou will be given the positions of $n$ restaurants along the highway as $n$ integers $d_1, d_2, d_3,...,d_n$ $(d_1 \u003c d_2 \u003c ...\u003c d_n)$ (these are the distances measured from the company’s headquarter, which happens to be at the same highway). Furthermore, a integer $k (k\\le n)$ will be given, the number of depots to be built.\n\nThe $k$ depots will be built at the locations of $k$ different restaurants. Each restaurant will be\nassigned to the closest depot, from which it will then receive its supplies. To minimize shipping costs, the total distance sum, defined as \n\n$\\sum\\limits_{n}^{i\u003d1}$| $d_i$ − (position of depot serving restaurant $i$) |\n\nmust be as small as possible.\n\nWrite a program that computes the positions of the $k$ depots, such that the total distance sum is minimized.\n"}},{"title":"Input","value":{"format":"MD","content":"The input contains several testcases. \n\nEach testcase starts with a line containing the two integers $n$ $(1\\le n\\le 200)$ and $k$ $(1\\le k\\le 30, k\\le n)$.\n\nFollowing this will $n$ lines containing one integer each, giving the positions $d_i$ $(0\\le d_i\\le 10^9)$ of the restaurants, ordered increasingly.\n\nThe input file will end with a case starting with $n \u003d k \u003d 0$. This case should not be processed.\n"}},{"title":"Output","value":{"format":"MD","content":"For each testcase, first output the number of the chain. Then output an optimal placement of the depots as follows: for each depot output a line containing its position and the range of restaurants it serves.\n\nIf there is more than one solution, you can output any of them. After the depot descriptions output a line containing the total distance sum, as defined in the problem text.\n\nOutput a blank line after each test case."}},{"title":"","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 3\n5\n6\n12\n19\n20\n27\n4 3\n1\n2\n3\n4\n0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eChain 1\nDepot 1 at restaurant 2 serves restaurants 1 to 3\nDepot 2 at restaurant 4 serves restaurants 4 to 5\nDepot 3 at restaurant 6 serves restaurant 6\nTotal distance sum \u003d 8\n\nChain 2\nDepot 1 at restaurant 1 serves restaurant 1\nDepot 2 at restaurant 2 serves restaurant 2\nDepot 3 at restaurant 3 serves restaurants 3 to 4\nTotal distance sum \u003d 1\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}