{"problem":{"name":"[ICPC 2024 Xi'an I] Dumb Robot","description":{"content":"You have a dumb robot, and you are going to let it play games with $n$ robots. There is a matrix $A$ with three rows and three columns in the game. We call the number of row $i$ and column $j$ of thi","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10557"},"statements":[{"statement_type":"Markdown","content":"You have a dumb robot, and you are going to let it play games with $n$ robots.\n\nThere is a matrix $A$ with three rows and three columns in the game. We call the number of row $i$ and column $j$ of this matrix $A_{i,j}$. The game goes like this:\n\nTwo players each choose an integer from $[1,3]$ at the same time. We call the number your robot chooses $i$, and the number the other robot chooses $j$.\nThe score is $A_{i,j}$.\nIn game $i$, your robot will play this game with the $i$ -th robot. The $i$ -th robot has a probability of choosing $1$ as $p_{i,1}$, a probability of choosing $2$ as $p_{i,2}$, and a probability of choosing $3$ as $p_{i,3}$.\n\nYour goal is to make the expected value of the score not negative in each game. But your robot is very dumb, so it will choose $1$ with probability $q_1$, $2$ with probability $q_2$, and $3$ with probability $q_3$, and you don't know the value of $q_1,q_2,q_3$.\n\nWe all know that $q_1+q_2+q_3=1$. If $q_1,q_2,q_3$ are chosen uniformly at random from a set of all possible cases, please calculate the probability that you will reach your goal.\n\n## Input\n\nThe first line contains one integer $n$($1\\le n\\le10^4$).\n\nEach of the next $3$ lines contains $3$ integers, the $j$ -th integer in the $i$ -th of these lines is $A_{i,j}$($-20\\le A_{i,j}\\le20$).\n\nEach of the next $n$ lines contains $3$ real numbers, the $j$ -th number in the $i$ -th of these lines is $p_{i,j}$. It is guaranteed that $p_{i,1}+p_{i,2}+p_{i,3}=1$ and $0\\le p_{i,j}$.\n\n## Output\n\nOutput the answer to the problem. It is guaranteed that the answer will never be $0$.\n\nYour answer is considered correct if its absolute or relative error does not exceed $10^{-2}$. Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\\frac{|a-b|}{max(1,|b|)} \\leq 10^{-2}$.\n\n[samples]\n\n## Note\n\nIn example $1$, for example, $(q_1=1,q_2=0,q_3=0)$ is ok. In this case, Your robot will always choose $1$, so no matter what number will robot $1$ choose, the score will always be $1$, which is enough to reach your goal.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10557","tags":["2024","Special Judge","O2优化","ICPC","西安"],"sample_group":[["1\n1 1 1\n -1 2 1\n0 -3 2\n0.1 0.6 0.3","0.748252"],["8\n1 3 -2\n0 0 2\n-2 2 1\n0.1 0.3 0.6\n0 0 1\n0.5 0.2 0.3\n0 0 1\n1 0 0\n0 0 1 \n0.33 0.33 0.34\n0.16 0.16 0.68","0.111111"]],"created_at":"2026-03-03 11:09:25"}}