P11921 [PA 2025] 看护 / Opieka

PA 2025 R3A.

有一段时间 $[0,l)$ 被等分成 $l$ 份 $[0,1),[1,2),\ldots,[l-1,l)$。 有 $n$ 个人轮流照顾婴儿。$\forall i\in [1,n], j\in [0,l)$，我们知道第 $i$ 个人在时间 $[j,j+1)$ 内是否空闲。如果一个人在一段时间内是空闲的，他可以选择照顾婴儿或睡觉。 在时间段 $[0,l)$ 内，**每个人最多可以入睡一次，醒来一次**。公平起见，每个人睡眠时长必须相同，设为 $t$（$t\ge 0$）。那么某个人可以在 $[a,a+t)$ 内睡觉，当且仅当他在这段时间内空闲，且 $a+t\le l$。 婴儿在每个时刻都必须有人照顾，换句话说，$\forall x\in [0,l)$，都必须至少有一个人在时刻 $x$ 清醒且空闲。在此前提下，合理安排每个人的睡眠时间，最大化 $t$ 的值。 可以证明，若存在一个合法的 $t$，则 $t$ 的最大值一定是一个有理数。只需要以既约分数的形式输出这个精确值即可。

第一行，两个正整数 $n,l$。 接下来 $i$ 行，第 $i$ 行一个长度为 $l$ 的字符串 $s_{i}$。 $\forall 1\le i\le n,\forall 0\le j\lt l$，$s_{i,j}=\texttt{X}$，表示第 $i$ 个人在时段 $[j,j+1)$ 忙碌；否则 $s_{i,j}=\texttt{.}$，表示第 $i$ 个人在时段 $[j,j+1)$ 空闲。

如果无法做到「婴儿在每个时刻都必须有人照顾」，输出一行一个 $-1$。 否则，输出一个既约分数 $x/y$（即 $\gcd(x,y)=1,y\gt 0$），表示合法的 $t$ 的最大值。特别地，若 $t$ 的最大值为 $0$，输出 $\texttt{0/1}$。

### 样例解释 - 样例 $1$ 解释：第 $1,2,3$ 个人分别在 $[0,4/3),[8/3,4),[4/3,8/3)$ 内睡觉。 - 样例 $2$ 解释：第 $2$ 个人没时间睡觉。 - 样例 $3$ 解释：在时刻 $x=\pi/2\approx 1.57$ 时，无人照顾婴儿。 ### 数据范围 - $1\le n\le 18$； - $1\le l \le 10^5$。