{"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\u003eAndré Claude Marzipan is the head chef at the French\n restaurant Le Chaud Chien. He owns a vast number of baking\n trays, which come in two sizes: \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e foot by \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e foot, and \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e foot by \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e feet. He stores them along\n \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e-foot deep shelves of\n various lengths. For example, on a shelf that is \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e feet long, he might store baking\n trays in either of the two ways shown below:\u003c/p\u003e\n\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/8cde326dc7dfc77dd63ac770959379ee?v\u003d1715309498\" alt\u003d\"\\includegraphics[width\u003d0.5\\textwidth ]{trays.jpg}\" style\u003d\"width:50.00%\"\u003e\u003cbr\u003e\n Figure G.1\n \u003c/center\u003e\n\n \u003cp\u003eOf course, there are many more than just these two ways, and\n in his off hours André often wonders how many different ways he\n can place trays on a given shelf. André is a bit of \u003cem\u003eun\n maniaque du rangement\u003c/em\u003e (neat freak), so he insists that the\n trays are always aligned along the two axes defined by the\n shelf edges, that the edges of the trays are always\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e foot multiples away\n from any edge, and that no portion of a tray extends beyond the\n shelf. The matter is complicated by the fact that often there\n are locations on the shelf where he does not want to put any\n baking trays, due to leaks above the shelf, dents in the\n shelf’s surface, etc. Since André is more adept at cuisine than\n counting, he needs a little help.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of two lines: the first line will contain\n two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\le m\\leq 24$\u003c/span\u003e indicates the length\n of the shelf (which is always \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e-feet deep) and \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e indicates the number of bad\n locations on the shelf. The next line will contain \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e coordinate pairs \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e indicating the locations where\n trays should not be placed, where \u003cspan class\u003d\"tex2jax_process\"\u003e$0\u0026lt;x\u0026lt;m$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$0\u0026lt;y\u0026lt;3$\u003c/span\u003e. No location will have\n integer coordinates and coordinates are specified to the\n nearest hundredth. If \u003cspan class\u003d\"tex2jax_process\"\u003e$n\u003d0$\u003c/span\u003e, this second line will be\n blank.\u003cbr\u003e\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput the number of ways that trays could be placed on the\n shelf.\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\u003e4 0\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e823\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\u003e4 2\n0.29 2.44 2.73 1.8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e149\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}