Work

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 worka.in 输出文件 worka.out

第三题:work

当前有nn<=12)个工作,和8个工人。现在每个工作需要占用一个工人的从[ab]这个区间的时间(一个工人自然不可能在同一个时间做2个不同的工作),且一个工作不一定是所有工人都能够完成的。现在给出每个工作的描述,问是否存在一种安排方案使得所有工作都能完成。

 

输入文件(worka.in

输出文件有多组数据。第一行一个数tot表示数据的组数,后面紧接tot组数据。

对于每一组数据的第一行有一个整数n,表示工作的数目。后面n行每行描述一个工作。

对于一个工作,abkh1h2……hk来描述,表示这个工作需要占用一个工人[ab]的时间,并且能够完成这个工作的工人只有k个,标号分别是h1h2……hk

 

输出文件(worka.out

对于每组输入数据,输出一行YES(如果可以安排一种方案使得工作完成)或者是NO(无法安排一种方案)

 

样例:

 

input

2

2

1 1 1 1

2 2 1 1

2

1 2 1 1

2 2 1 1

 

output

YES

NO