#2233. 波兰语

    ID: 2233 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1941来源:qoj.ac数据:公开样例二分答案

波兰语

波兰语

题目描述

标题: 波兰语 - Problem - QOJ.ac

Statistics

照顾新生儿并不是一件简单的任务,总得有人时刻守护在他身边。同时人们还有其他任务要做,更何况照顾者也想偶尔睡个觉……

现在一共有 n 个人共同照顾刚出生的小Bajtolinka。考虑一段时间区间 [0,L),这个区间被划分为 L 个单位长度的片段 [i,i+1)。对于每一个这样的片段,我们都清楚每个人是否在这段时间内有其他任务需要完成。如果某人在某个片段内没有其他任务,那么他可以选择睡觉或者照顾孩子。

在整个时间范围内,每个人最多只会睡觉一次(即只会躺下一次并醒来一次)。为了公平起见,我们希望制定一个照顾新生儿的计划,使得每个人睡觉的时长都完全相等,记为 T(其中 T≥0 为实数)。每个人的其他任务总会占满整个单位时间片段 [i,i+1),而睡觉则可以选择任意起点 a 开始的连续区间 [a,a+T),但须满足 a+T≤L。

请找到满足以下条件的最大的睡觉时长 T:

  • 对于区间内任意时刻 x∈[0,L),都至少有一人处于空闲状态(即不在睡觉也没有其他任务),从而能够照顾小Bajtolinka。

可以证明,如果存在最优解,则最大的睡觉时长 T 一定是一个有理数。你需要将这个有理数以最简分数的形式输出。

若无法制订出这样的计划,使得每时每刻都有至少一人照顾孩子,请输出 -1。

输入格式

第一行包含两个整数 n,L(1≤n≤18,1≤L≤100000),分别表示照顾小Bajtolinka的人数以及考虑的时间区间长度。

接下来 n 行,每行是一个长度为 L 的字符串,表示每个人的日程安排,其中第 i 个字符表示区间 [i−1,i) 的状态:

  • 字符 X 表示该人在该时间片段忙于其他任务。
  • 字符 . 表示该时间片段该人空闲,可以睡觉或照顾Bajtolinka。

输出格式

如果无法满足条件,输出一行 -1。

否则输出一行一个最简分数形式的数(设为 xy,其中 gcd(x,y)=1,且 y>0),表示在最优计划下每个人能够睡觉的最大可能时长。

样例

输入样例一:

3 4
....
.X..
..X.

对应输出

4/3

每个人睡觉的最佳长度为 43。例如,可以安排第一个人在 [0,4/3) 睡觉,第二个人在 [8/3,4) 睡觉,第三个人在 [4/3,8/3) 睡觉,每个时刻都有至少一人醒着照顾新生儿。

输入样例2:

1 3
.X.

对应输出:

-1

子任务

子任务一(4 分)

n≤5, L≤100

子任务二(5 分)

n≤6, L≤1000

子任务三(7 分)

n≤8, L≤104

子任务四(8 分)

n≤10, L≤3×104

子任务五(11 分)

n≤12, L≤5×104

子任务六(9 分)

n≤14, L≤6×104

子任务七(13 分)

n≤15, L≤7×104

子任务八(12 分)

n≤16, L≤8×104

子任务九(13 分)

n≤17, L≤9×104

子任务十(18 分)

没有额外的限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 6
..X.XX
.X..X.
X..X..
4/3

样例 2

3 2
..
XX
..
0/1