{"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":"1d7d298b-37a5-5966-ad25-4929501c04e0","task_key":"ICPC~2dWorld~2dFinals--examples--2016~5fJ","task_revision_id":"1","upstream_id":"2016_J","short_description":"Spin Doctor","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"# Problem Description\\n\\nAs an employee of the world’s most respected political polling corporation, you must take complex, real-world issues and simplify them down to a few numbers. A big election is coming up and, at the request of Candidate X, you have just finished polling \\\\( n \\\\) people. You have gathered three pieces of information from each person, with the values for the \\\\( i \\\\)-th person recorded as:\\n\\n- \\\\( a_i \\\\) – the number of digits of \\\\(\\\\pi\\\\) they have memorized\\n- \\\\( b_i \\\\) – the number of hairs on their head\\n- \\\\( c_i \\\\) – whether they will vote for Candidate X\\n\\nUnfortunately, you are beginning to wonder if these are really the most relevant questions to ask. In fact, you cannot see any correlation between \\\\( a \\\\), \\\\( b \\\\), and \\\\( c \\\\) in the data. Of course, you cannot just contradict your customer – that is a good way to lose your job!\\n\\nPerhaps the answer is to find some weighting formula to make the results look meaningful. You will pick two real values \\\\( S \\\\) and \\\\( T \\\\), and sort the poll results \\\\((a_i, b_i, c_i)\\\\) by the measure \\\\( a_i \\\\cdot S + b_i \\\\cdot T \\\\). The sort will look best if the results having \\\\( c_i \\\\) true are clustered as close to each other as possible. More precisely, if \\\\( j \\\\) and \\\\( k \\\\) are the indices of the first and last results with \\\\( c_i \\\\) true, you want to minimize the cluster size which is \\\\( k - j + 1 \\\\). Note that some choices of \\\\( S \\\\) and \\\\( T \\\\) will result in ties among the \\\\((a_i, b_i, c_i)\\\\) triples. When this happens, you should assume the worst possible ordering occurs (that which maximizes the cluster size for this \\\\((S, T)\\\\) pair).\\n\\n## Input\\n\\nThe input starts with a line containing \\\\( n \\\\) \\\\((1 \\\\leq n \\\\leq 250,000)\\\\), which is the number of people polled. This is followed by one line for each person polled. Each of those lines contains integers \\\\( a_i \\\\) \\\\((0 \\\\leq a_i \\\\leq 2,000,000)\\\\), \\\\( b_i \\\\) \\\\((0 \\\\leq b_i \\\\leq 2,000,000)\\\\), and \\\\( c_i \\\\), where \\\\( c_i \\\\) is 1 if the person will vote for Candidate X and 0 otherwise. The input is guaranteed to contain at least one person who will vote for Candidate X.\\n\\n## Output\\n\\nDisplay the smallest possible cluster size over all possible \\\\((S, T)\\\\) pairs.\\n\\n## Sample Input 1\\n\\n```\\n6\\n0 10 0\\n10 0 1\\n12 8 1\\n5 5 0\\n11 2 1\\n11 3 0\\n```\\n\\n## Sample Output 1\\n\\n```\\n4\\n```\\n\\n## Sample Input 2\\n\\n```\\n10\\n6 1 1\\n0 2 0\\n2 1 1\\n6 1 1\\n8 2 0\\n4 4 0\\n4 0 0\\n2 3 1\\n6 1 0\\n6 3 1\\n```\\n\\n## Sample Output 2\\n\\n```\\n8\\n```\\n\\n## Sample Input 3\\n\\n```\\n5\\n5 7 0\\n3 4 0\\n5 7 0\\n5 7 1\\n9 4 0\\n```\\n\\n## Sample Output 3\\n\\n```\\n1\\n```\",\"question_title\":\"Spin Doctor\"}","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":[]}