{"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:40.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/8022bdbd282d58ffb0a6703ae8d9f886?v\u003d1714823862\" alt\u003d\"/problems/spinningup/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e“Sabotage!” exclaimed J.R. Diddly, president and founder\n of Diddly Widgets Inc.\n\n \u003cp\u003e“Vandalism, perhaps. Nothing’s actually been damaged.”\n responded Robert Lackey, the chief accountant.\u003c/p\u003e\n\n \u003cp\u003eBoth were staring up at the large counter suspended above\n the factory floor, a counter that had faithfully recorded the\n number of widgets that had come off the assembly line since the\n factory was opened. But someone had changed the number being\n displayed so that it formed...\u003c/p\u003e\n\n \u003cp\u003e“It’s a palindrome.” said Lackey. “It reads the same\n forwards as backwards.”\u003c/p\u003e\n\n \u003cp\u003e“What I don’t understand,” said Diddly, “is why our security\n guards didn’t catch the vandals during their regular sweeps. It\n must have taken them hours to click forward to this new number,\n one step at a time.”\u003c/p\u003e\n\n \u003cp\u003e“No.” replied Lackey. “Although we only advance the\n rightmost digit each time a new widget is built, it’s possible\n to spin any of the digits. With a little planning, this might\n have taken only a few seconds.”\u003c/p\u003e\n\n \u003ch2\u003eDescription\u003c/h2\u003e\n\n \u003cp\u003eConsider a digital counter consisting of \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e wheels, each showing a digit from\n \u003ctt class\u003d\"tt\"\u003e0\u003c/tt\u003e to \u003ctt class\u003d\"tt\"\u003e9\u003c/tt\u003e. Each wheel is\n mounted so that it can advance to the next digit in a single\n step, \u003cem\u003ee.g.\u003c/em\u003e, from \u003ctt class\u003d\"tt\"\u003e3\u003c/tt\u003e to \u003ctt class\u003d\"tt\"\u003e4\u003c/tt\u003e, or from \u003ctt class\u003d\"tt\"\u003e8\u003c/tt\u003e to \u003ctt class\u003d\"tt\"\u003e9\u003c/tt\u003e.\u003c/p\u003e\n\n \u003cp\u003eIt is also possible to advance from digit \u003ctt class\u003d\"tt\"\u003e9\u003c/tt\u003e to digit \u003ctt class\u003d\"tt\"\u003e0\u003c/tt\u003e. However, when this\n happens, the wheel on its immediate left will also advance to\n the next digit automatically. This can have a cascade effect on\n multiple wheels to the left, but they all happen in a single\n step.\u003c/p\u003e\n\n \u003cp\u003eGiven the current setting of the counter, find the smallest\n number of steps until one can reach a palindrome. The\n palindrome must respect leading zeros, \u003cem\u003ee.g.\u003c/em\u003e,\n \u003ctt class\u003d\"tt\"\u003e0011\u003c/tt\u003e is not a palindrome.\u003c/p\u003e\n\n \u003cp\u003eFor example, for input \u003ctt class\u003d\"tt\"\u003e610\u003c/tt\u003e, it takes\n four steps. This can be done by incrementing the \u003ctt class\u003d\"tt\"\u003e6\u003c/tt\u003e wheel four times, resulting in \u003ctt class\u003d\"tt\"\u003e010\u003c/tt\u003e.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eInput will consist of single line containing an integer of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$40$\u003c/span\u003e digits. The number of digits in\n the input is the number of wheels on the counter. Numbers may\n contain leading zeros.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003ePrint a single line of output containing one integer, the\n minimum number of wheel advances required to produce a\n palindrome.\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\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\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\u003e009990001\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\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 3\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\u003e29998\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\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 4\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\u003e610\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\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 5\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\u003e981\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\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 6\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\u003e9084194700940903797191718247801197019268\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e54\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}