小部件生产时间

题目描述

小部件工厂生产几种不同类型的小部件。

每个小部件都是精心制作而成。制作小部件所需的时间取决于其类型：简单小部件仅需要 3 天，但最复杂的小部件可能需要多达 9 天。

工厂现状

工厂目前处于完全混乱的状态：最近，工厂被一位新主人收购，新主人解雇了几乎所有员工。

新员工对制作小部件毫无经验，没有人清楚制作每个不同类型的小部件分别需要多少天。

当客户订购小部件，工厂却无法告诉客户生产所需商品需要多少天时显得十分尴尬。

可用信息

幸运的是，这里有记录记载了每个工人开始制作的日期，完成制作的日期以及制作的小部件型号。

但是问题是记录没有明确记载工人开始和完成工作的确切日期，只记录了该天是星期几。

信息价值

例如，如果一个人在星期二开始制作一个 41 型小部件，并在周五完成，那么我们就知道了制作一个 41 型小部件需要 4 天时间（因为最多不超过 9 天，所以不可能是 11 天或更多）。

任务

您的任务是从这些记录中（如果可能）找出制作不同类型的小部件所需的天数。

输入格式

输入包含多组测试用例。

每个测试用例：

1. 第一行包含两个整数 $n$ 和 $m$，分别代表小部件的型号总数以及记录总数
2. 接下来是对 $m$ 个记录的描述
   • 每个记录占两行
   • 第一行描述该名工人制作的小部件总数 $k$ 以及他开始制作和完成制作具体是星期几
   • 一周的日子由字符串 MON, TUE, WED, THU, FRI, SAT 和 SUN 来表示
   • 第二行包含用空格分隔的 $k$ 个整数，表示该工人具体制作了哪些类型的部件

注意： 每名工人一周工作 7 天。

当输入用例 $n=m=0$ 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一行结果：

1. 如果有唯一解：结果包含 $n$ 个用空格隔开的整数，表示制作每个小部件所需的天数
2. 如果有多种可能结果：输出 Multiple solutions.
3. 如果无解：输出 Inconsistent data.

数据范围

• $1 \le n, m \le 300$
• $1 \le k \le 10000$

输入样例

2 3
2 MON THU
1 2
3 MON FRI
1 1 2
3 MON SUN
1 2 2
10 2
1 MON TUE 
3
1 MON WED
3
0 0

输出样例

8 3
Inconsistent data.

样例解释

第一个测试用例

输入：

• $n=2$：2种小部件型号
• $m=3$：3条记录

记录1：

• 制作2个小部件
• 开始：MON（星期一），结束：THU（星期四）
• 制作的小部件：型号1，型号2

记录2：

• 制作3个小部件
• 开始：MON（星期一），结束：FRI（星期五）
• 制作的小部件：型号1，型号1，型号2

记录3：

• 制作3个小部件
• 开始：MON（星期一），结束：SUN（星期日）
• 制作的小部件：型号1，型号2，型号2

求解：

设型号1的生产时间为 $x_1$ 天，型号2的生产时间为 $x_2$ 天。

根据记录1：星期一 → 星期四，共4天（星期四-星期一=3天差，但可能跨周）

• 实际天数为：$d_1 = \text{(THU序号)} - \text{(MON序号)} \mod 7$
• 星期序号：MON=1, TUE=2, WED=3, THU=4, FRI=5, SAT=6, SUN=0 或 7
• THU(4) - MON(1) = 3，如果结果是负数就加7
• 所以 $d_1 = (4-1) \mod 7 = 3$，但需要加7的倍数：可能为3, 10, 17, ... 天
• 因为每个小部件最多9天，所以工人制作总天数在3到9×k之间
• 记录1制作2个小部件，总天数可能是3, 10, 17, ...
• 但每个小部件3-9天，2个小部件最少6天最多18天，所以只能是10天（3+7）或17天（3+14），但17>18不可能
• 所以记录1总天数为10天

方程：$x_1 + x_2 \equiv 10 \pmod{7}$，且 $6 \le x_1+x_2 \le 18$，所以 $x_1+x_2 = 10$

类似分析其他记录...

最终解得：$x_1 = 8, x_2 = 3$

输出： 8 3

第二个测试用例

输入：

• $n=10$：10种型号
• $m=2$：2条记录

记录1：

• 制作1个小部件
• 开始：MON，结束：TUE
• 制作型号3

记录2：

• 制作1个小部件
• 开始：MON，结束：WED
• 制作型号3

分析： 设型号3的生产时间为 $x_3$ 天。

记录1：MON→TUE，时间差为1天（可能加7的倍数）

• 单个小部件：$x_3 \equiv 1 \pmod{7}$，且 $3 \le x_3 \le 9$
• 所以 $x_3$ 可能是1, 8, 15, ...，结合3-9天的限制，$x_3 = 8$

记录2：MON→WED，时间差为2天（可能加7的倍数）

• 单个小部件：$x_3 \equiv 2 \pmod{7}$，且 $3 \le x_3 \le 9$
• 所以 $x_3$ 可能是2, 9, 16, ...，结合3-9天的限制，$x_3 = 9$

矛盾：记录1要求 $x_3=8$，记录2要求 $x_3=9$，无解。

输出： Inconsistent data.

问题建模

星期转换

将星期转换为数字：

• MON = 0, TUE = 1, WED = 2, THU = 3, FRI = 4, SAT = 5, SUN = 6

两个日期 $d_s$（开始）和 $d_e$（结束）之间的天数差（模7意义下）为：

$$\Delta = (d_e - d_s + 7) \mod 7$$

实际总天数 $T$ 满足：

$$T \equiv \Delta \pmod{7}, \quad 且 \quad k \cdot 3 \le T \le k \cdot 9$$

其中 $k$ 是该工人制作的小部件总数。

线性同余方程组

设 $x_i$ 表示型号 $i$ 的生产天数（$3 \le x_i \le 9$）。

对于每条记录 $j$：

• 制作的小部件型号集合：$S_j$
• 该记录总生产天数 $T_j$ 满足：$\sum_{i \in S_j} x_i \equiv \Delta_j \pmod{7}$
• 且 $3|S_j| \le T_j \le 9|S_j|$

由于 $T_j$ 必须在 $[3|S_j|, 9|S_j|]$ 范围内，且 $T_j \equiv \Delta_j \pmod{7}$，所以 $T_j$ 是确定的（如果不唯一则可能有多解）。

高斯消元

我们得到模7的线性方程组：

$$\sum_{i=1}^n a_{ji} x_i \equiv b_j \pmod{7}$$

其中 $a_{ji}$ 是型号 $i$ 在记录 $j$ 中出现的次数，$b_j = \Delta_j \mod 7$。

由于 $x_i \in \{3,4,5,6,7,8,9\}$，可以先解模7方程，然后调整到正确范围。

算法步骤

1. 建立方程组：对于每条记录，计算 $\Delta$，建立模7方程
2. 高斯消元：在模7域上解线性方程组
3. 解的判断：
   • 无解：输出 Inconsistent data.
   • 有解：计算秩 $r$ 和自由变元个数 $f$
   • 如果 $f > 0$：可能有多解，需要进一步判断是否在范围内有唯一解
4. 范围验证：对于每个解，检查是否满足 $3 \le x_i \le 9$
5. 输出结果：
   • 如果无满足范围的解：Inconsistent data.
   • 如果有多个满足范围的解：Multiple solutions.
   • 如果有唯一满足范围的解：输出各 $x_i$

注意事项

1. 模7运算：因为7是质数，所以模7域上的线性方程组可以使用高斯消元
2. 范围限制：$x_i$ 必须为3到9的整数
3. 模7方程的解可能对应多个实际值（相差7的倍数）
4. 需要检查所有可能的实际值是否在3-9范围内

时间复杂度

• 高斯消元：$O(n^3)$，$n \le 300$，可以接受
• 范围检查：对于自由变元需要枚举可能的值

模7运算细节

由于7是质数，模7域上的运算：

• 加法、减法、乘法：模7
• 除法：乘以逆元（因为7是质数，非零数都有逆元）

逆元表：

• 1⁻¹ = 1
• 2⁻¹ = 4（因为2×4=8≡1 mod 7）
• 3⁻¹ = 5（3×5=15≡1 mod 7）
• 4⁻¹ = 2
• 5⁻¹ = 3
• 6⁻¹ = 6（6×6=36≡1 mod 7）

时空限制

• 时间限制：1秒
• 空间限制：64MB