{"problem":{"name":"D. Calculated risk","description":{"content":"We have a dice with $k$ sides that is rolled over and over again. You have to pay $£ 1$ for each time the dice is rolled. The prize is paid if at some you get a streak of $n$ consecutive ones (the dic","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10241D"},"statements":[{"statement_type":"Markdown","content":"We have a dice with $k$ sides that is rolled over and over again. You have to pay $£ 1$ for each time the dice is rolled. The prize is paid if at some you get a streak of $n$ consecutive ones (the dice shows 1). What is the mininum prize you should ask for in order to make profit from such game?\n\n_In other words what is the expected number of turns before streak of $n$ is hit._\n\nFor example let's say that the results of a regular $6$-sided dice are: $1, 3, 1, 1, 1$.\n\nFor $n = 3$ you receive the prize after paying $£ 5$ for those $5$ turns.\n\nInput is two numbers $3 <= k <= 20$ and $1 <= n <= 5$. \n\nPrint out the expected number of times you have to roll the dice to get a streak of $n$ ones. You can assume that the answer will be no bigger than $10^9$. We expect the accuracy of $10^(-4)$.\n\n## Input\n\nInput is two numbers $3 <= k <= 20$ and $1 <= n <= 5$. \n\n## Output\n\nPrint out the expected number of times you have to roll the dice to get a streak of $n$ ones. You can assume that the answer will be no bigger than $10^9$. We expect the accuracy of $10^(-4)$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ n = |V| $ nodes and $ m = |E| $ edges.  \nLet $ a: V \\to \\mathbb{Z} $ be a function assigning to each node $ i \\in V $ a value $ a_i \\in [0, 2^{20}) $.  \n\n**Constraints**  \n1. $ 1 \\le n, m \\le 3 \\times 10^5 $  \n2. $ 0 \\le a_i < 2^{20} $ for all $ i \\in V $  \n3. $ E $ contains no self-loops; multiple edges are allowed.  \n\n**Objective**  \nDetermine whether there exists a subset $ S \\subseteq V $ and a value $ x \\in [0, 2^{20}) $ such that, after updating $ a_i \\leftarrow a_i \\oplus x $ for all $ i \\in S $, the resulting values $ a'_i $ satisfy:  \n$$\n\\forall (u,v) \\in E, \\quad a'_u \\ne a'_v\n$$  \nIf such $ S $ and $ x $ exist, output:  \n- First line: $ |S| $ and $ x $  \n- Second line: the elements of $ S $  \n\nOtherwise, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10241D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}