{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"hlce","formal_name":"Humanity's Last Code Exam","introduction":"Humanity's Last Code Exam evaluates problem solving and code generation using ICPC World Finals and IOI problems. The project describes 235 problems; this import selects its public ICPC dataset of 146 problems.","introduction_ja":"","introduction_en":"","category":"Category not supplied","task_count":null,"acquisition_status":"Acquisition status not supplied","official_url":"https://humanity-s-last-code-exam.github.io/website/","indexing_mode":"noindex","profile":{"resources":[],"task_format":"","scoring":"","metric":"","size":"","answer_access":"","license":"","citation":"","maintainer":"","released":"","why_hard":"","related":[]}},"task_id":"77aa4a2f-58f7-536b-96c9-c560c2a0e2c3","task_key":"ICPC~2dWorld~2dFinals--examples--2018~5fE","task_revision_id":"2","upstream_id":"2018_E","short_description":"Getting a Jump on Crime","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem Statement\\n\\nYour friend Robin is a superhero. When you first found out about this, you figured “everybody needs a hobby, and this seems more exciting than stamp collecting,” but now you are really thankful that somebody is doing something about the crime in your hometown.\\n\\nEvery night, Robin patrols the city by jumping from roof to roof and watching what goes on below. Naturally, superheroes need to respond to crises immediately, so Robin asked you for help in figuring out how to get around your hometown quickly.\\n\\nYour hometown is built on a square grid, where each block is \\\\(w \\\\times w\\\\) meters. Each block is filled by a single building. The buildings may have different heights. To get from one building to another (not necessarily adjacent) building, Robin makes a single jump from the center of the roof of the first building to the center of the roof of the second building. Robin cannot change direction while in the air, but can choose the angle at which to lift off.\\n\\nOf course, Robin only wants to perform jumps without colliding with any buildings. Such collisions do little damage to a superhero, but building owners tend to get irritated when someone crashes through their windows. You explain the physics to Robin: “All your jumps are done with the same initial velocity \\\\(v\\\\), which has a horizontal component \\\\(v_d\\\\) towards the destination and vertical component \\\\(v_h\\\\) upwards, so \\\\(v_d^2 + v_h^2 = v^2\\\\). As you travel, your horizontal velocity stays constant (\\\\(v_d(t) = v_d\\\\)), but your vertical velocity is affected by gravity (\\\\(v_h(t) = v_h - t \\\\cdot g\\\\)), where \\\\(g = 9.80665 \\\\, \\\\text{m/s}^2\\\\) in your hometown.\\n\\nNaturally, your cape allows you to ignore the effects of air resistance. This allows you to determine your flight path and ...” at which point you notice that Robin has nodded off – less math, more super-heroing!\\n\\nSo it falls to you: given a layout of the city and the location of Robin’s secret hideout, you need to determine which building roofs Robin can reach, and the minimum number of jumps it takes to get to each roof.\\n\\nNote that if Robin’s jump passes over the corner of a building (where four buildings meet), then the jump needs to be higher than all four adjacent buildings.\\n\\n### Input\\n\\nThe input starts with a line containing six integers \\\\(dx, dy, w, v, \\\\ell_x, \\\\ell_y\\\\). These represent the size \\\\(dx \\\\times dy\\\\) of the city grid \\\\((1 \\\\leq dx, dy \\\\leq 20)\\\\) in blocks, the width of each building \\\\((1 \\\\leq w \\\\leq 10^3)\\\\) in meters, Robin’s takeoff velocity \\\\((1 \\\\leq v \\\\leq 10^3)\\\\) in meters per second, and the coordinates \\\\((\\\\ell_x, \\\\ell_y)\\\\) of Robin’s secret hideout \\\\((1 \\\\leq \\\\ell_x \\\\leq dx, 1 \\\\leq \\\\ell_y \\\\leq dy)\\\\).\\n\\nThe first line is followed by a description of the heights of the buildings in the city grid. The description consists of \\\\(dy\\\\) lines, each containing \\\\(dx\\\\) non-negative integers. The \\\\(j\\\\)-th line contains the heights for buildings \\\\((1, j), (2, j), \\\\ldots, (dx, j)\\\\). All heights are given in meters and are at most \\\\(10^3\\\\).\\n\\n### Output\\n\\nDisplay the minimum number of jumps Robin needs to get from the secret hideout to the roof of each building. If there is no way to reach a building’s roof, display `X` instead of the number of jumps. Display the buildings in the same order as given in the input file, split into \\\\(dy\\\\) lines, each containing \\\\(dx\\\\) values.\\n\\nYou may assume that changing the height of any building by up to \\\\(10^{-6}\\\\) would not change the answers.\\n\\n### Sample Input 1\\n\\n```\\n4 1 100 55 1 1\\n10 40 60 10\\n```\\n\\n### Sample Output 1\\n\\n```\\n0 1 1 1\\n```\\n\\n### Sample Input 2\\n\\n```\\n4 4 100 55 1 1\\n0 10 20 30\\n10 20 30 40\\n20 30 200 50\\n30 40 50 60\\n```\\n\\n### Sample Output 2\\n\\n```\\n0 1 1 2\\n1 1 1 2\\n1 1 X 2\\n2 2 2 3\\n```\",\"question_title\":\"Getting a Jump on Crime\"}","display_format":"text","language":"","answer_status":"published","assets":[],"source_url":"https://humanity-s-last-code-exam.github.io/website/","history":"initial import","indexing_mode":"noindex","subproblems":[],"grids":[]}