#3813. 小部件厂

    ID: 3813 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>线性代数高斯消元数学知识同余算法竞赛进阶指南

小部件厂

题目描述

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

每个小部件都是精心制作而成。

制作小部件所需的时间取决于其类型:简单小部件仅需要 3 天,但最复杂的小部件可能需要多达 9 天。

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

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

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

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

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

尽管如此,这些信息也是有些帮助的:例如,如果一个人在星期二开始制作一个 41 型小部件,并在周五完成,那么我们就知道了制作一个 41 型小部件需要 4 天时间(因为最多不超过 9 天,所以不可能是 11 天或更多)。

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

输入格式

输入包含多组测试用例。

每个测试用例的第一行包含两个整数 n 和 m,分别代表小部件的型号总数以及记录总数。

接下来是对 m 个记录的描述。

每个记录占两行,第一行描述该名工人制作的小部件总数 k 以及他开始制作和完成制作具体是星期几。

一周的日子由字符串 MONTUEWEDTHUFRISATSUN 来表示。

第二行包含用空格分隔的 k 个整数,表示该工人具体制作了哪些类型的部件。

如下面的例子中,这名工人星期三开始工作,星期日结束工作,期间先后完成制作了型号 13,型号 18,型号 1,型号 13 四个小部件。

4 WED SUN 
13 18 1 13 

每名工人一周工作 7 天。

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

输出格式

每个测试用例输出一行结果,结果包含 n 个用空格隔开的整数,表示制作每个小部件所需的天数。

如果测试用例有多种可能结果,则输出 Multiple solutions.

如果无解,则输出 Inconsistent data.

样例

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.

数据范围

1n,m300,1k100001≤n,m≤300, 1≤k≤10000

来源

  • POJ2947
  • ICPC CERC 2005
  • 算法竞赛进阶指南