{"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\u003eA well-known puzzle is to “tour” all the squares of an\n \u003cspan class\u003d\"tex2jax_process\"\u003e$8 \\times 8$\u003c/span\u003e chessboard\n using a knight, which is a piece that can move only by jumping\n one square in one direction and two squares in an orthogonal\n direction. The knight must visit every square of the\n chessboard, without repeats, and then return to its starting\n square. There are many ways to do this, and the chessboard size\n is manageable, so it is a reasonable puzzle for a human to\n solve.\u003c/p\u003e\n \u003cp\u003eHowever, you have access to a computer, and some coding\n skills! So, we will give you a harder version of this problem\n on a rectangular \u003cspan class\u003d\"tex2jax_process\"\u003e$m \\times\n n$\u003c/span\u003e chessboard with an additional constraint: the knight\n may never cross its own path. If you imagine its path\n consisting of straight line segments connecting the centers of\n squares it jumps between, these segments must form a simple\n polygon; that is, no two segments intersect or touch, except\n that consecutive segments touch at their common end point. This\n constraint makes it impossible to visit every square, so\n instead you must maximize the number of squares the knight\n visits. We keep the constraint that the knight must return to\n its starting square. Figure\u0026nbsp;1 shows an optimal solution\n for the first sample input, a \u003cspan class\u003d\"tex2jax_process\"\u003e$6\n \\times 6$\u003c/span\u003e board.\u003c/p\u003e\n \u003cdiv id\u003d\"fig:sixbysix\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/a446a27482eccfc5b625d53d540ed73c?v\u003d1715544626\" alt\u003d\"\\includegraphics[width\u003d0.3\\textwidth ]{sixbysix.pdf}\" style\u003d\"width:30.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: An optimal solution for a \u003cspan class\u003d\"tex2jax_process\"\u003e$6 \\times 6$\u003c/span\u003e board.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of a single line containing two integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le m \\le 8$\u003c/span\u003e) and \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le n \\le 10^{15}$\u003c/span\u003e), giving the dimensions of the\n rectangular chessboard.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eDisplay the largest number of squares that a knight can\n visit in a tour on an \u003cspan class\u003d\"tex2jax_process\"\u003e$m \\times\n n$\u003c/span\u003e chessboard that does not cross its path. If no such\n tour exists, display \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e.\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\u003e6 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\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\u003e8 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\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\u003e7 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e80\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\u003e2 6\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 "}}]}