{"problem":{"name":"E. Enter to the best problem of this contest!","description":{"content":"_*This is an interactive problem*. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout) or cout.flush(), in Java — System.ou","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10270E"},"statements":[{"statement_type":"Markdown","content":"_*This is an interactive problem*. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout) or cout.flush(), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush()._\n\nOsman is lost again :(\n\nHe was trying to come up with the best problem of this contest so he didn't notice that he was entering a maze. Oh, poor Osman! \n\nOsman is lost in a really symmetrical maze: The maze looks like a perfect binary tree of depth $n$ $(1 <= n <= 29)$ and, luckily, we have a map of the maze. Each node of the binary tree is named by a number and, for each node $k$, the two children of this node (if any) are named by $2 k$ and $2 k + 1$. For instance, when the depth of the binary tree is $4$, then the maze looks like this:\n\nYour task is to find Osman. He is unable to move in one of the nodes of the tree. You have a device where you can make queries, each query is a single integer $k$ from $1$ to $2^n -1$. Flush the output stream after printing each query. The device will provide you with the distance from $k$ to the node where Osman is. You can do at most $29$ queries to the device before it explodes (or maybe it doesn't, but you don't want to know, do you?). \n\nOnce you find Osman, print \"! $x$\" (without quotes), where $x$ is the node where Osman is, and terminate your program normally immediately after flushing the output stream.\n\nHelp Osman exit the maze! Or not, I don't care. \n\nUse standard input to read the responses to the queries.\n\nThe first line contains an integer $n$ ($1 <= n <= 29$) — The depth of the tree.\n\nFollowing lines will contain responses to your queries — The distance between the node where Osman is and the node that you sent. The $i$-th line is the response to your $i$-th query.\n\nThe testing system will allow you to read the response on the query only after your program print the query for the system and perform the _flush_ operation.\n\nTo make the queries your program must use standard output.\n\nYour program must print the queries — A query consist of an integer number $x_i$ ($1 <= x_i <= 2^n -1$). Print one query per line (do not forget \"_end of line_\" after each $x_i$). After printing each line your program must perform operation _flush_.\n\nIn case your program find the node $x$ where Osman is, print string \"! $x$\" (without quotes), where $x$ is the answer, and terminate your program. An accepted solution should make at most 29 queries, printing the answer does not count as a query.\n\n## Input\n\nUse standard input to read the responses to the queries.The first line contains an integer $n$ ($1 <= n <= 29$) — The depth of the tree.Following lines will contain responses to your queries — The distance between the node where Osman is and the node that you sent. The $i$-th line is the response to your $i$-th query.The testing system will allow you to read the response on the query only after your program print the query for the system and perform the _flush_ operation.\n\n## Output\n\nTo make the queries your program must use standard output.Your program must print the queries — A query consist of an integer number $x_i$ ($1 <= x_i <= 2^n -1$). Print one query per line (do not forget \"_end of line_\" after each $x_i$). After printing each line your program must perform operation _flush_.In case your program find the node $x$ where Osman is, print string \"! $x$\" (without quotes), where $x$ is the answer, and terminate your program. An accepted solution should make at most 29 queries, printing the answer does not count as a query.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of cities.  \nFor each $ i \\in \\{1, \\dots, N\\} $:  \n- $ (x_i, y_i) \\in \\mathbb{R}^2 $ is the 2D coordinate of city $ i $.  \n- $ p_i \\in \\mathbb{Z} $ is the population (in thousands) of Zoom users in city $ i $.  \n\n**Constraints**  \n1. $ 1 \\leq N < 1000 $  \n2. $ -1000 \\leq x_i, y_i \\leq 1000 $  \n3. $ 1 \\leq p_i < 1000 $  \n\n**Objective**  \nCompute the weighted average location $ (x_a, y_a) $, where weights are user populations:  \n$$\nx_a = \\frac{\\sum_{i=1}^{N} p_i x_i}{\\sum_{i=1}^{N} p_i}, \\quad y_a = \\frac{\\sum_{i=1}^{N} p_i y_i}{\\sum_{i=1}^{N} p_i}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10270E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}