#P10557. [ICPC2024 Xi'an I] Dumb Robot

    ID: 10003 Type: RemoteJudge 3000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>2024Special JudgeO2优化ICPC

[ICPC2024 Xi'an I] Dumb Robot

题目描述

You have a dumb robot, and you are going to let it play games with nn robots.

There is a matrix AA with three rows and three columns in the game. We call the number of row ii and column jj of this matrix Ai,jA_{i,j}. The game goes like this:

Two players each choose an integer from [1,3][1,3] at the same time. We call the number your robot chooses ii, and the number the other robot chooses jj. The score is Ai,jA_{i,j}. In game ii, your robot will play this game with the ii -th robot. The ii -th robot has a probability of choosing 11 as pi,1p_{i,1}, a probability of choosing 22 as pi,2p_{i,2}, and a probability of choosing 33 as pi,3p_{i,3}.

Your 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 11 with probability q1q_1, 22 with probability q2q_2, and 33 with probability q3q_3, and you don't know the value of q1,q2,q3q_1,q_2,q_3.

We all know that q1+q2+q3=1q_1+q_2+q_3=1. If q1,q2,q3q_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.

输入格式

The first line contains one integer nn(1n1041\le n\le10^4).

Each of the next 33 lines contains 33 integers, the jj -th integer in the ii -th of these lines is Ai,jA_{i,j}(20Ai,j20-20\le A_{i,j}\le20).

Each of the next nn lines contains 33 real numbers, the jj -th number in the ii -th of these lines is pi,jp_{i,j}. It is guaranteed that pi,1+pi,2+pi,3=1p_{i,1}+p_{i,2}+p_{i,3}=1 and 0pi,j0\le p_{i,j}.

输出格式

Output the answer to the problem. It is guaranteed that the answer will never be 00.

Your answer is considered correct if its absolute or relative error does not exceed 10210^{-2}. Formally, let your answer be aa, and the jury's answer be bb. Your answer is accepted if and only if abmax(1,b)102\frac{|a-b|}{max(1,|b|)} \leq 10^{-2}.

1
1 1 1
 -1 2 1
0 -3 2
0.1 0.6 0.3
0.748252
8
1 3 -2
0 0 2
-2 2 1
0.1 0.3 0.6
0 0 1
0.5 0.2 0.3
0 0 1
1 0 0
0 0 1 
0.33 0.33 0.34
0.16 0.16 0.68
0.111111

提示

In example 11, for example, (q1=1,q2=0,q3=0)(q_1=1,q_2=0,q_3=0) is ok. In this case, Your robot will always choose 11, so no matter what number will robot 11 choose, the score will always be 11, which is enough to reach your goal.