#102. 「Widget Factory」 小部件厂

「Widget Factory」 小部件厂

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

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

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

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

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

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

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

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

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

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

输入格式

输入包含多组测试用例。

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

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

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

一周的日子由字符串“MON”,“TUE”,“WED”,“THU”,“FRI”,“SAT”和“SUN”来表示。

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

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

4 WED SUN
13 18 1 13

每名工人一周工作7天。

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

输出格式

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

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

如果无解,则输出“Inconsistent data.”。

数据范围

1n,m3001 \le n,m \le 300,
1k100001 \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.

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解