{"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":"5bdbe880-f4fd-5442-ae94-9142a41028bc","task_key":"ICPC~2dWorld~2dFinals--examples--2021~5fJ","task_revision_id":"1","upstream_id":"2021_J","short_description":"Splitstream","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem Statement\\n\\nA splitstream system is an acyclic network of nodes that processes finite sequences of numbers. There are two types of nodes:\\n\\n- **Split Node**: Takes a sequence of numbers as input and distributes them alternatingly to its two outputs. The first number goes to output 1, the second to output 2, the third to output 1, the fourth to output 2, and so on.\\n\\n- **Merge Node**: Takes two sequences of numbers as input and merges them alternatingly to form its single output. The output contains the first number from input 1, then the first from input 2, then the second from input 1, then the second from input 2, and so on. If one input sequence is shorter than the other, the remaining numbers from the longer sequence are transmitted without merging after the shorter sequence is exhausted.\\n\\nThe overall network has one input, which is the sequence of positive integers \\\\(1, 2, 3, \\\\ldots, m\\\\). Any output of any node can be queried. A query will seek to identify the \\\\(k\\\\)-th number in the sequence of numbers for a given output and a given \\\\(k\\\\). Your task is to implement such queries efficiently.\\n\\n## Input\\n\\nThe first line of input contains three integers \\\\(m\\\\), \\\\(n\\\\), and \\\\(q\\\\), where \\\\(m\\\\) \\\\((1 \\\\leq m \\\\leq 10^9)\\\\) is the length of the input sequence, \\\\(n\\\\) \\\\((1 \\\\leq n \\\\leq 10^4)\\\\) is the number of nodes, and \\\\(q\\\\) \\\\((1 \\\\leq q \\\\leq 10^3)\\\\) is the number of queries.\\n\\nThe next \\\\(n\\\\) lines describe the network, one node per line. A split node has the format `S x y z`, where \\\\(x\\\\), \\\\(y\\\\), and \\\\(z\\\\) identify its input, first output, and second output, respectively. A merge node has the format `M x y z`, where \\\\(x\\\\), \\\\(y\\\\), and \\\\(z\\\\) identify its first input, second input, and output, respectively. Identifiers \\\\(x\\\\), \\\\(y\\\\), and \\\\(z\\\\) are distinct positive integers. The overall input is identified by 1, and the remaining input/output identifiers form a consecutive sequence beginning at 2. Every input identifier except 1 appears as exactly one output. Every output identifier appears as the input of at most one node.\\n\\nEach of the next \\\\(q\\\\) lines describes a query. Each query consists of two integers \\\\(x\\\\) and \\\\(k\\\\), where \\\\(x\\\\) \\\\((2 \\\\leq x \\\\leq 10^5)\\\\) is a valid output identifier and \\\\(k\\\\) \\\\((1 \\\\leq k \\\\leq 10^9)\\\\) is the index of the desired number in that sequence. Indexing in a sequence starts with 1.\\n\\n## Output\\n\\nFor each query \\\\(x\\\\) and \\\\(k\\\\), output one line with the \\\\(k\\\\)-th number in the output sequence identified by \\\\(x\\\\), or `none` if there is no element with that index number.\\n\\n## Sample Input 1\\n\\n```\\n200 2 2\\nS 1 2 3\\nM 3 2 4\\n4 99\\n4 100\\n```\\n\\n## Sample Output 1\\n\\n```\\n100\\n99\\n```\\n\\n## Sample Input 2\\n\\n```\\n100 3 6\\nS 1 4 2\\nS 2 3 5\\nM 3 4 6\\n6 48\\n6 49\\n6 50\\n6 51\\n6 52\\n5 25\\n```\\n\\n## Sample Output 2\\n\\n```\\n47\\n98\\n49\\n51\\n53\\n100\\n```\\n\\n## Sample Input 3\\n\\n```\\n2 3 3\\nS 1 2 3\\nS 3 4 5\\nM 5 2 6\\n3 1\\n5 1\\n6 2\\n```\\n\\n## Sample Output 3\\n\\n```\\n2\\nnone\\nnone\\n```\",\"question_title\":\"Splitstream\"}","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":[]}