#2233. 波兰语
波兰语
波兰语
题目描述
标题: 波兰语 - Problem - QOJ.ac
照顾新生儿并不是一件简单的任务,总得有人时刻守护在他身边。同时人们还有其他任务要做,更何况照顾者也想偶尔睡个觉……
现在一共有 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