{"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\u003eYour friend Robin is a superhero. When you first found out\n about this, you figured “everybody needs a hobby, and this\n seems more exciting than stamp collecting,” but now you are\n really thankful that somebody is doing something about the\n crime in your hometown.\u003c/p\u003e\n \u003cp\u003eEvery night, Robin patrols the city by jumping from roof to\n roof and watching what goes on below. Naturally, superheroes\n need to respond to crises immediately, so Robin asked you for\n help in figuring out how to get around your hometown\n quickly.\u003c/p\u003e\n \u003cp\u003eYour hometown is built on a square grid, where each block is\n \u003cspan class\u003d\"tex2jax_process\"\u003e$w \\times w$\u003c/span\u003e meters. Each\n block is filled by a single building. The buildings may have\n different heights (see Figure\u0026nbsp;1). To get from one building\n to another (not necessarily adjacent) building, Robin makes a\n single jump from the center of the roof of the first building\n to the center of the roof of the second building. Robin cannot\n change direction while in the air, but can choose the angle at\n which to lift off.\u003c/p\u003e\n \u003cdiv id\u003d\"fig:jump\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/f0ed2d9d5ad1732660b325d04e5b4c66?v\u003d1715987367\" alt\u003d\"\\includegraphics[width\u003d0.95\\textwidth ]{sample1}\" style\u003d\"width:95.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Cross-section of buildings corresponding\n to the first sample input. Buildings are shown in black,\n and the jump from the roof at \u003cspan class\u003d\"tex2jax_process\"\u003e$(1,1)$\u003c/span\u003e to the roof at\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(4,1)$\u003c/span\u003e is shown\n with a green line.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003cp\u003eOf course, Robin only wants to perform jumps without\n colliding with any buildings. Such collisions do little damage\n to a superhero, but building owners tend to get irritated when\n someone crashes through their windows. You explain the physics\n to Robin: “All your jumps are done with the same initial\n velocity \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e, which has a\n horizontal component \u003cspan class\u003d\"tex2jax_process\"\u003e$v_\n d$\u003c/span\u003e towards the destination and vertical component\n \u003cspan class\u003d\"tex2jax_process\"\u003e$v_ h$\u003c/span\u003e upwards, so\n \u003cspan class\u003d\"tex2jax_process\"\u003e$v_ d^2 + v_ h^2 \u003d v^2$\u003c/span\u003e.\n As you travel, your horizontal velocity stays constant\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$v_ d(t) \u003d v_ d$\u003c/span\u003e), but\n your vertical velocity is affected by gravity (\u003cspan class\u003d\"tex2jax_process\"\u003e$v_ h(t) \u003d v_ h - t \\cdot g$\u003c/span\u003e), where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$g \u003d 9.80665 \\text { m}/\\text\n {s}^2$\u003c/span\u003e in your hometown. Naturally, your cape allows you\n to ignore the effects of air resistance. This allows you to\n determine your flight path and ...” at which point you notice\n that Robin has nodded off – less math, more super-heroing!\u003c/p\u003e\n \u003cp\u003eSo it falls to you: given a layout of the city and the\n location of Robin’s secret hideout, you need to determine which\n building roofs Robin can reach, and the minimum number of jumps\n it takes to get to each roof.\u003c/p\u003e\n \u003cp\u003eNote that if Robin’s jump passes over the corner of a\n building (where four buildings meet), then the jump needs to be\n higher than all four adjacent buildings.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input starts with a line containing six integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ x$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ y$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell _ x$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell _ y$\u003c/span\u003e. These represent the size\n \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ x \\times d_ y$\u003c/span\u003e of the\n city grid (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le d_ x,d_ y \\le\n 20$\u003c/span\u003e) in blocks, the width of each building (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le w \\le 10^3$\u003c/span\u003e) in meters, Robin’s\n takeoff velocity (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le v \\le\n 10^3$\u003c/span\u003e) in meters per second, and the coordinates\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell _ x,\\ell _ y$\u003c/span\u003e) of\n Robin’s secret hideout (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le\n \\ell _ x \\le d_ x$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le\n \\ell _ y \\le d_ y$\u003c/span\u003e).\u003c/p\u003e\n \u003cp\u003eThe first line is followed by a description of the heights\n of the buildings in the city grid. The description consists of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ y$\u003c/span\u003e lines, each\n containing \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ x$\u003c/span\u003e\n non-negative integers. The \u003cspan class\u003d\"tex2jax_process\"\u003e$j^{th}$\u003c/span\u003e line contains the heights for\n buildings \u003cspan class\u003d\"tex2jax_process\"\u003e$(1,j), (2,j), \\dots ,\n (d_ x,j)$\u003c/span\u003e. All heights are given in meters and are at\n most \u003cspan class\u003d\"tex2jax_process\"\u003e$10^3$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eDisplay the minimum number of jumps Robin needs to get from\n the secret hideout to the roof of each building. If there is no\n way to reach a building’s roof, display \u003ctt class\u003d\"ttfamily\"\u003eX\u003c/tt\u003e instead of the number of jumps. Display the\n buildings in the same order as given in the input file, split\n into \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ y$\u003c/span\u003e lines, each\n containing \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ x$\u003c/span\u003e\n values.\u003c/p\u003e\n \u003cp\u003eYou may assume that changing the height of any building by\n up to \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-6}$\u003c/span\u003e would not\n change the answers.\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\u003e4 1 100 55 1 1\n10 40 60 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 1 1 1\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\u003e4 4 100 55 1 1\n0 10 20 30\n10 20 30 40\n20 30 200 50\n30 40 50 60\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 1 1 2\n1 1 1 2\n1 1 X 2\n2 2 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}