#P2667. Barber's problem

Barber's problem

题目描述
汤姆是一个小镇的理发师。他拥有一家小商店、几个学徒,并因其高质量的服务而赢得了良好的声誉。然而,随着他的客户越来越多,他遇到了一些问题。

让我们先看一下理发的过程。顾客可以换衣服理发洗完头发后,开始理发;之后再洗一次头发擦干头发,把衣服换回去,然后付钱。在 Tom 的商店里,他自己做所有理发、干活和现金工作,把换衣服和洗头的工作留给他的学徒。假设每个作需要 1 个单位的时间,如图 1 所示。 通常,Tom 会对整个过程进行管道化处理,以便他可以同时为多个客户提供服务。以下是两个客户的简单案例: 但是,当三个客户走到一起时,简单的管道将满足问题: 在时间 5 和时间 7 时,客户 13 都需要 Tom。太可惜了,汤姆只能在 1 个单位的时间内做一件事,但他怎么能让他的客户湿着头发等他呢?

当然,这对汤姆来说没什么大不了的。他只是在他的程序中添加了一些 wait 单元,如图 4 所示: 没有人会抱怨理发和吹干后休息一下,现在所有三位顾客都得到了及时的服务(图 5)。 但是,对于更复杂的情况,汤姆应该怎么做呢?

现在 TomTom 需要你的帮助。假设 TomTom 能够知道客户何时到来,您将判断是否可以在程序中添加一些等待单位以满足:

  1. 让所有顾客一来就得到服务(顾客不耐烦,不能及时服务就走)。
  2. 消除管道中的碰撞(碰撞意味着 Tom 必须同时服务两个以上的客户,但可以同时服务许多客户换衣服或洗头,因为学徒足够)。

您需要记住的其他一些注意事项:

  1. 您添加的等待单位必须是有限的
  2. 等待单元可以是相邻的
  3. 每个客户的程序都应该相同。没有人比其他人乐意等待更长的时间。
  4. 您只能将等待单位添加到程序中,而不能交换或删除任何现有步骤。必须保留原始顺序:Change-Wash-Cut-Wash-Dry-Change-Pay

输入
输入中有多个测试用例。

以下几行描述了测试用例。一个 casecase 的每一行都以以下格式给出:

(n1,n2,...,nk)0<ni<=20,0<k<=20(n1, n2, ..., nk) 0 < ni <= 20, 0 < k <= 20

它给出了客户来的时间。nin_i 表示每个 SequentialCustomerSequential Customer 的间隔时间。括号表示客户会定期来。

例如,假设第一个客户在时间 1 到达,如果客户到达时间 1、3、5、7、9、11、13、... 表示形式为 (2)。表示 (1,3,7) 表示客户将在时间 1、2、5、12、13、16、23、24、27、34...

图 5 所示的示例对应于表示 (1),当然,在 4、5、6、7 等时间会有更多的客户来......

包含 (0) 的行结束输入。


输出
您的任务是决定是否有解决方案将 FINITE 等待单位添加到理发程序中,以消除管道中的冲突,并使所有客户都能在他来后立即得到服务。如果可以解决,则打印 Yes,否则打印 No,分别在一行中。

例如,对于输入 (1),您可以添加 2 个等待单位,如上图 5 所示,以解决 33 个客户的情况,但是当越来越多的客户来时,除了添加越来越多的等待单位外,您无法满足所有人。没有尽头。所以答案是 No。对于输入 (2,3,7),您可以在过程中添加 4 个等待单位 以满足管道,如图 6 所示。所以答案是 Yes


输入数据 1

(1)
(2,3,7)
(0)

输出数据 1

No
Yes

来源
北京 2005 预选赛