{"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 \u003cp\u003eIlliteracy is a simple puzzle game created by Le\n Sio.\u0026nbsp;\u003ca href\u003d\"https://open.kattis.com/problems/illiteracy#a0000000004\" class\u003d\"footnote\"\u003e\u003csup class\u003d\"footnotemark\"\u003e1\u003c/sup\u003e\u003c/a\u003e The game consists of a sequence of\n eight icons; the actual icons are very artistic, but for\n simplicity, we’ll label the icons using a capital letter\n \u003ctt class\u003d\"ttfamily\"\u003eA\u003c/tt\u003e—\u003ctt class\u003d\"ttfamily\"\u003eF\u003c/tt\u003e.\n Clicking any icon has a unique effect on the other icons, based\n on which icon is clicked and that icon’s position in the\n sequence. Most of the icons \u003cem\u003erotate\u003c/em\u003e the type of other\n icons. A rotation changes an \u003ctt class\u003d\"ttfamily\"\u003eA\u003c/tt\u003e to a\n \u003ctt class\u003d\"ttfamily\"\u003eB\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eB\u003c/tt\u003e to\n \u003ctt class\u003d\"ttfamily\"\u003eC\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eC\u003c/tt\u003e to\n \u003ctt class\u003d\"ttfamily\"\u003eD\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eD\u003c/tt\u003e to\n \u003ctt class\u003d\"ttfamily\"\u003eE\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eE\u003c/tt\u003e to\n \u003ctt class\u003d\"ttfamily\"\u003eF\u003c/tt\u003e, and \u003ctt class\u003d\"ttfamily\"\u003eF\u003c/tt\u003e\n back to \u003ctt class\u003d\"ttfamily\"\u003eA\u003c/tt\u003e.\u003c/p\u003e\n \u003cp\u003eHere’s what the icons do when you click on one, based on the\n type of the icon and its position \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e in the sequence (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\\leq x \\leq 8$\u003c/span\u003e):\u003c/p\u003e\n \u003ccenter\u003e\n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003cb class\u003d\"bfseries\"\u003eType\u003c/b\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left\"\u003e\n \u003cp\u003e\u003cb class\u003d\"bfseries\"\u003eEffect\u003c/b\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eA\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left\"\u003e\n \u003cp\u003eRotates the icons immediately to the left and right\n (at positions \u003cspan class\u003d\"tex2jax_process\"\u003e$x-1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$x+1$\u003c/span\u003e), ignoring any icon that\n doesn’t exist (when \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003d1$\u003c/span\u003e or \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e).\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eB\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left\"\u003e\n \u003cp\u003eIf the icon is at either end of the sequence, does\n nothing. Otherwise, changes the icon at position\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x+1$\u003c/span\u003e to the same\n type as the current icon at \u003cspan class\u003d\"tex2jax_process\"\u003e$x-1$\u003c/span\u003e.\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eC\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left\"\u003e\n \u003cp\u003eRotates the icon at position \u003cspan class\u003d\"tex2jax_process\"\u003e$9-x$\u003c/span\u003e.\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eD\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left\"\u003e\n \u003cp\u003eRotates all icons between position \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and the closest of the\n sequence’s two ends. (Does nothing if \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e is one of the two ends,\n and does not change the icon at position \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e itself). For example, if\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003d3$\u003c/span\u003e, the icons\n at \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003d1$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e would be\n rotated. If \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003d5$\u003c/span\u003e,\n then the icons at positions \u003cspan class\u003d\"tex2jax_process\"\u003e$6$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$7$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e would be rotated.\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eE\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left\"\u003e\n \u003cp\u003eIf the icon is at either end of the sequence, does\n nothing. Otherwise, let \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e be the number of icons\n between position \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and the closest of the\n sequence’s two ends. Rotates the two icons at positions\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x-y$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x+y$\u003c/span\u003e. For\n example, if \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003d3$\u003c/span\u003e,\n the icons at \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003d1$\u003c/span\u003e\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e would be\n rotated. If \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003d5$\u003c/span\u003e,\n the icons at positions \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e would be rotated.\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left\"\u003e\n \u003cp\u003eIf \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e is odd,\n rotates the icon at position \u003cspan class\u003d\"tex2jax_process\"\u003e$(x+9)/2$\u003c/span\u003e. If \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e is even, rotates the icon\n at position \u003cspan class\u003d\"tex2jax_process\"\u003e$x/2$\u003c/span\u003e.\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n \u003c/center\u003e\n \u003cp\u003eGiven a starting sequence of icons and a target sequence,\n what is the minimal number of clicks required to transform the\n starting sequence into the target sequence?\u003c/p\u003e\n \u003ch5\u003eExamples\u003c/h5\u003e\n \u003cp\u003eFor the cases below, we illustrate one possible minimal\n sequence of clicks to get from the top configuration to the\n bottom one. The carets indicate which icon on the previous line\n was clicked to generate the sequence on the following line. The\n sequence on the left takes \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e clicks; the sequence on the right\n takes \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e clicks.\u003c/p\u003e\n \u003ccenter\u003e\n \u003cpre\u003eABCDEFCD DCDAFCBA\n ^ ^ \nBCDDEFCD DCEAACBA\n ^ ^ \nBCEDEFCD DCEAACBC\n ^ \n DCEAACCC\n ^ \n ECEABCCC\n\u003c/pre\u003e\n \u003c/center\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of exactly two lines of eight characters\n each. The first line is the starting icon sequence, and the\n second is the target sequence. Each character on each line is\n one of the six capital letters \u003ctt class\u003d\"ttfamily\"\u003eA\u003c/tt\u003e,\n \u003ctt class\u003d\"ttfamily\"\u003eB\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eC\u003c/tt\u003e,\n \u003ctt class\u003d\"ttfamily\"\u003eD\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eE\u003c/tt\u003e, or\n \u003ctt class\u003d\"ttfamily\"\u003eF\u003c/tt\u003e. It will always be possible to\n reach the target sequence from the given starting sequence\n using a finite number of clicks.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput a single integer, the smallest number of icon clicks\n needed to get from the starting sequence to the target\n sequence.\u003c/p\u003e\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\u003eABCDEFCD\nBCEDEFCD\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 \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\u003eDCDAFCBA\nECEABCCC\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 \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\u003eABCDEFCD\nABCDEFCD\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 \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\u003eACFEFBEB\nEDBFEFDE\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e22\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}