{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:32.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/cf6c6d575df0901636204dd30f9bfc5e?v\u003d1715678377\" alt\u003d\"/problems/arranginghat/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\u003cem\u003eArranging Hat\u003c/em\u003e is a cushy job indeed; high impact\n work, absolute authority, and 364 days of holiday every year.\n However, the hat has decided that it can do even better—it\n would like very much to become a tenured professor.\n\n \u003cp\u003eRecently the hat has been reading computer science papers in\n its ample spare time, and of course, being an arranging hat, it\n is particularly interested in learning more about sorting\n algorithms.\u003c/p\u003e\n\n \u003cp\u003eThe hat’s new contribution is to a class of algorithms known\n as \u003cem\u003elossy\u003c/em\u003e sorting algorithms. These usually work by\n removing some of the input elements in order to make it easier\n to sort the input (e.g., the Dropsort algorithm), instead of\n sorting all the input.\u003c/p\u003e\n\n \u003cp\u003eThe hat is going to go one better—it is going to invent a\n lossy sorting algorithm for numbers that does not remove any\n input numbers and even keeps them in their original place, but\n instead changes some of the digits in the numbers to make the\n list sorted.\u003c/p\u003e\n\n \u003cp\u003eThe lossiness of the sorting operation depends on how many\n digits are changed. What is the smallest number of digits that\n need to be changed in one such list of numbers, to ensure that\n it is sorted?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line containing the integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le n \\le 40$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le m \\le 400$\u003c/span\u003e), the number of\n numbers and the number of digits in each number,\n respectively.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines each\n containing an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le v \u0026lt; 10^{m}$\u003c/span\u003e). The\n numbers are zero-padded to exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e digits.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eWrite a sorted version of the array, after making a minimum\n number of digit changes to make the numbers sorted (the numbers\n must remain zero-padded to \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e digits). If there are multiple\n optimal solutions, you may give any of them.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e5 3\n111\n001\n000\n111\n000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e001\n001\n001\n111\n200\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e15 3\n999\n888\n777\n666\n555\n444\n333\n222\n111\n222\n333\n444\n555\n666\n999\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e199\n288\n377\n466\n555\n644\n733\n822\n911\n922\n933\n944\n955\n966\n999\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}