{"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":"f1dfde9a-df36-5c26-9c41-6b13830c1815","task_key":"ICPC~2dWorld~2dFinals--examples--2011~5fE","task_revision_id":"3","upstream_id":"2011_E","short_description":"Coffee Central","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem Description\\n\\nIs it just a fad or is it here to stay? You’re not sure, but the steadily increasing number of coffee shops that are opening in your hometown has certainly become quite a draw. Apparently, people have become so addicted to coffee that apartments that are close to many coffee shops will actually fetch higher rents.\\n\\nThis has come to the attention of a local real-estate company. They are interested in identifying the most valuable locations in the city in terms of their proximity to large numbers of coffee shops. They have given you a map of the city, marked with the locations of coffee shops. Assuming that the average person is willing to walk only a fixed number of blocks for their morning coffee, you have to find the location from which one can reach the largest number of coffee shops. As you are probably aware, your hometown is built on a square grid layout, with blocks aligned on north-south and east-west axes. Since you have to walk along streets, the distance between intersections \\\\((a, b)\\\\) and \\\\((c, d)\\\\) is \\\\(|a - c| + |b - d|\\\\).\\n\\n### Input\\n\\nThe input contains several test cases. Each test case describes a city. The first line of each test case contains four integers \\\\(dx, dy, n, \\\\text{and } q\\\\). These are the dimensions of the city grid \\\\(dx \\\\times dy\\\\) \\\\((1 \\\\leq dx, dy \\\\leq 1000)\\\\), the number of coffee shops \\\\(n\\\\) \\\\((0 \\\\leq n \\\\leq 5 \\\\cdot 10^5)\\\\), and the number of queries \\\\(q\\\\) \\\\((1 \\\\leq q \\\\leq 20)\\\\). Each of the next \\\\(n\\\\) lines contains two integers \\\\(x_i\\\\) and \\\\(y_i\\\\) \\\\((1 \\\\leq x_i \\\\leq dx, 1 \\\\leq y_i \\\\leq dy)\\\\); these specify the location of the \\\\(i\\\\)-th coffee shop. There will be at most one coffee shop per intersection. Each of the next \\\\(q\\\\) lines contains a single integer \\\\(m\\\\) \\\\((0 \\\\leq m \\\\leq 10^6)\\\\), the maximal distance that a person is willing to walk for a cup of coffee.\\n\\nThe last test case is followed by a line containing four zeros.\\n\\n### Output\\n\\nFor each test case in the input, display its case number. Then display one line per query in the test case. Each line displays the maximum number of coffee shops reachable for the given query distance \\\\(m\\\\) followed by the optimal location. For example, the sample output shows that 3 coffee shops are within query distance 1 of the optimal location \\\\((3, 4)\\\\), 4 shops are within query distance 2 of optimal location \\\\((2, 2)\\\\), and 5 shops are within query distance 4 of optimal location \\\\((3, 1)\\\\). If there are multiple optimal locations, pick the location that is furthest south (minimal positive integer y-coordinate). If there is still a tie, pick the location furthest west (minimal positive integer x-coordinate).\\n\\nFollow the format of the sample output.\\n\\n### Sample Input\\n\\n```\\n4 4 5 3\\n1 1\\n1 2\\n3 3\\n4 4\\n2 4\\n1\\n2\\n4\\n0 0 0 0\\n```\\n\\n### Output for the Sample Input\\n\\n```\\nCase 1:\\n3 (3,4)\\n4 (2,2)\\n5 (3,1)\\n```\",\"question_title\":\"Coffee Central\"}","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":[]}