{"problem":{"name":"J. Buoys","description":{"content":"The swimming area of Berhattan's city beach is marked out with n buoys. The buoys form a straight line. When the buoys were being put into the water, nobody cared to observe the same distance between ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10124J"},"statements":[{"statement_type":"Markdown","content":"The swimming area of Berhattan's city beach is marked out with n buoys. The buoys form a straight line. When the buoys were being put into the water, nobody cared to observe the same distance between each pair of adjacent buoys.\n\nNow the beach keeper wants the distance between any two adjacent buoys to be the same. He plans to shift some or all of the buoys without changing their respective order. To facilitate the task, he wants the total length of all shifts to be as small as possible.\n\nGiven coordinates of the buoys, you should find the minimum possible length of all shifts, as well as new coordinates of the buoys.\n\nThe first line of input contains a single integer n (2 ≤ n ≤ 400), n — the number of buoys. The second line contains buoys' integer coordinates x1, x2, ..., xn ( - 10000 ≤ xi ≤ 10000). No two given buoys will share the same place. The coordinates are given in strictly increasing order.\n\nTo the first line print a real number t — the minimum possible total length of required shifts. Output this value with at least 4 digits after the decimal point.\n\nTo the second line print n numbers — new coordinates of the buoys. The new coordinates should be printed in strictly increasing order with at least 7 digits after the decimal point. If there are several optimal ways to shift the buoys, you may output any of them.\n\nAll buoys are located on the Ox axis. You may move buoys only along the Ox axis.\n\n## Input\n\nThe first line of input contains a single integer n (2 ≤ n ≤ 400), n — the number of buoys. The second line contains buoys' integer coordinates x1, x2, ..., xn ( - 10000 ≤ xi ≤ 10000). No two given buoys will share the same place. The coordinates are given in strictly increasing order.\n\n## Output\n\nTo the first line print a real number t — the minimum possible total length of required shifts. Output this value with at least 4 digits after the decimal point.To the second line print n numbers — new coordinates of the buoys. The new coordinates should be printed in strictly increasing order with at least 7 digits after the decimal point. If there are several optimal ways to shift the buoys, you may output any of them.\n\n[samples]\n\n## Note\n\nAll buoys are located on the Ox axis. You may move buoys only along the Ox axis.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 2 $, be the number of buoys.  \nLet $ \\mathbf{x} = (x_1, x_2, \\dots, x_n) \\in \\mathbb{R}^n $ be the given strictly increasing coordinates of the buoys, with $ x_i < x_{i+1} $ for all $ i \\in \\{1, \\dots, n-1\\} $.  \n\nLet $ \\mathbf{y} = (y_1, y_2, \\dots, y_n) \\in \\mathbb{R}^n $ be the new coordinates of the buoys, satisfying $ y_1 \\leq y_2 \\leq \\dots \\leq y_n $, and $ y_i < y_{i+1} $ for all $ i \\in \\{1, \\dots, n-1\\} $.  \n\nLet $ d \\in \\mathbb{R}^+ $ be the common distance between adjacent buoys: $ y_{i+1} - y_i = d $ for all $ i \\in \\{1, \\dots, n-1\\} $.  \n\n**Constraints**  \n1. $ y_i \\in \\mathbb{R} $ for all $ i \\in \\{1, \\dots, n\\} $  \n2. $ y_{i+1} - y_i = d > 0 $ for all $ i \\in \\{1, \\dots, n-1\\} $  \n3. The sequence $ \\mathbf{y} $ must preserve the relative order of buoys: $ y_i $ corresponds to the buoy originally at $ x_i $.  \n\n**Objective**  \nMinimize the total shift length:  \n$$\n\\min_{\\mathbf{y}, d} \\sum_{i=1}^n |y_i - x_i|\n$$  \nsubject to $ y_i = y_1 + (i-1)d $ for all $ i \\in \\{1, \\dots, n\\} $.  \n\nEquivalently, minimize:  \n$$\n\\sum_{i=1}^n |y_1 + (i-1)d - x_i|\n$$  \nover $ y_1 \\in \\mathbb{R} $, $ d \\in \\mathbb{R}^+ $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10124J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}