{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"Input is two numbers $3 <= k <= 20$ and $1 <= n <= 5$. "},{"iden":"output","content":"Print 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)$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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 $.","simple_statement":"You are given a graph with n nodes and m edges. Each node has a number. You can pick any subset of nodes and XOR all their numbers with the same value x. Can you make sure that for every edge, the two connected nodes have different numbers? If yes, output the subset and x; if no, output -1.","has_page_source":false}