{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"hlce","formal_name":"Humanity's Last Code Exam","introduction":"ICPC World FinalsとIOIの競技プログラミング問題を使い、問題解決とコード生成の能力を評価します。公式紹介では235問を収録し、今回の取得は公開ICPCデータ146問を対象とします。\n\nHumanity'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"},"task_id":"3e66111f-a54e-558f-9cb9-0d9f10883b23","task_key":"ICPC~2dWorld~2dFinals--examples--2020~5fL","task_revision_id":"1","upstream_id":"2020_L","short_description":"Sweep Stakes","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem Statement\\n\\nYou may have already won! In fact, you did already win! You won your very own island, in the deepest reaches of the unexplored ocean! Well, mostly unexplored. As it happens, there was a small military base there before you, and when they packed up and flew out they left behind an assortment of scraps, munitions, tunnels, ... and unexploded defensive ordnance. That’s right: You now possess your very own minefield.\\n\\nThe minefield consists of an \\\\(m \\\\times n\\\\) grid, with any square of the grid holding 0 or 1 mines. Fortunately, you were able to recover the engineers’ plans from when they deployed the mines. Unfortunately, the exact locations of the mines were never written down: the engineers had a preselected independent probability of deploying a mine in each square. However, you do know how many mines were placed in total.\\n\\nYou would like to estimate how safe various parts of your island are. Write a program to compute the probability of mine counts over various subsets of the minefield.\\n\\n### Input\\n\\nThe first line of input contains four integers \\\\(m\\\\), \\\\(n\\\\), \\\\(t\\\\), and \\\\(q\\\\), where \\\\(m\\\\) and \\\\(n\\\\) (\\\\(1 \\\\leq m, n \\\\leq 500\\\\)) are the dimensions of the minefield, \\\\(t\\\\) (\\\\(0 \\\\leq t \\\\leq mn\\\\)) is the total number of mines, and \\\\(q\\\\) (\\\\(0 \\\\leq q \\\\leq 500\\\\)) is the number of queries. \\n\\nThe second line contains \\\\(m\\\\) real numbers \\\\(p_1, p_2, \\\\ldots, p_m\\\\) (\\\\(0 \\\\leq p_i \\\\leq 0.1\\\\) for all \\\\(i\\\\), with at most six digits after the decimal point specified), and the third line contains \\\\(n\\\\) real numbers \\\\(q_1, q_2, \\\\ldots, q_n\\\\) (\\\\(0 \\\\leq q_j \\\\leq 0.1\\\\) for all \\\\(j\\\\), with at most six digits after the decimal point specified). The preselected probability of the engineers placing a mine on square \\\\((i, j)\\\\) is \\\\(p_i + q_j\\\\). All choices of whether to place a mine on a given square were made independently, and the value of \\\\(t\\\\) is chosen so that the probability of deploying exactly \\\\(t\\\\) mines is at least \\\\(10^{-5}\\\\).\\n\\nEach of the remaining \\\\(q\\\\) lines describes a single query. Each of those lines begins with an integer \\\\(s\\\\) (\\\\(0 \\\\leq s \\\\leq 500\\\\)), followed by \\\\(s\\\\) pairs of integers \\\\(i\\\\) and \\\\(j\\\\) (\\\\(1 \\\\leq i \\\\leq m, 1 \\\\leq j \\\\leq n\\\\)), which are the coordinates of \\\\(s\\\\) distinct squares in the grid.\\n\\n### Output\\n\\nFor each query with \\\\(s\\\\) squares, output \\\\(s + 1\\\\) real numbers, which are the probabilities of the \\\\(s\\\\) given squares containing 0, 1, ..., \\\\(s\\\\) mines. Your answer should have an absolute error of at most \\\\(10^{-6}\\\\).\\n\\n### Sample Input 1\\n```\\n2 2 1 2\\n0.05 0.05\\n0.05 0.05\\n1 1 1\\n2 2 1 1 2\\n```\\n\\n### Sample Output 1\\n```\\n0.75 0.25\\n0.5 0.5 0\\n```\\n\\n### Sample Input 2\\n```\\n3 4 3 4\\n0.02 0.04 0.06\\n0.005 0.07 0.035 0.09\\n1 3 2\\n3 1 4 2 4 3 4\\n4 1 2 2 3 3 1 1 4\\n8 1 1 1 2 1 3 2 1 2 3 3 1 3 2 3 3\\n```\\n\\n### Sample Output 2\\n```\\n0.649469772 0.350530228\\n0.219607636 0.527423751 0.237646792 0.015321822\\n0.267615440 0.516222318 0.201611812 0.014550429 0\\n0.054047935 0.364731941 0.461044157 0.120175967 0 0 0 0 0\\n```\",\"question_title\":\"Sweep Stakes\"}","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":[]}