시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 147 | 77 | 69 | 55.645% |
MOLOCO, a global company with an unbeatable global reach, is developing a new survey platform to increase user engagement.
There are $N$ people who want to vote on an issue. Each person is either in support of the issue or against the issue.
There are $M$ not necessarily disjoint sets of people $S_1, S_2, \cdots, S_M$. For these $M$ sets and a constant $p$ ($0 \le p \le 1$), the propositions below are established.
If $p = 0$, no information can be obtained from this proposition. $p = 1$ shows that everyone is in support of the issue. That is, as $p$ grows, it becomes easier to ascertain who is in support of the issue.
Thus, if a proposition is established for a sufficiently large $p$, we can know that everyone is in support of the issue. Find the maximum value of $p$ such that you can not be certain everyone is in support.
The first line contains two integers $N$ and $M$, where $N$ denotes the number of people and $M$ denotes the number of sets.
The next $M$ lines describe the information of each of the $M$ sets.
The $i$-th line starts with an integer $|S_i|$, denoting the number of elements in the set $S_i$, followed by $|S_i|$ distinct integers $S_{i,j}$, denoting the elements in the set $S_i$.
Output the maximum value of $p$ such that you cannot be certain everyone is in support of the issue.
Your answer will be considered correct if it has an absolute or relative error less than $10^{-6}$.
This subtask has additional constraints:
This subtask has an additional constraint:
This subtask has no additional constraints.
3 3 1 1 1 2 1 3
0
4 2 2 1 2 2 3 4
0.5
10 7 4 8 6 10 5 4 9 5 6 1 4 4 8 1 10 4 1 5 9 3 4 6 10 5 1 4 8 3 1 10 6 5 7 6 8 1 2
0.833333333
In example 2, the proposition can be established for $p=0.5,$ if people 1, 3 are for and people 2, 4 are against.
However, if the proposition is established for $p>0.5, $ it is a contradiction to the proposition if there exists a person against an issue.