P1601. 有人要披萨吗？

题目描述

你负责为自己和朋友订购一个大披萨。每个朋友都告诉你他们想要和不想要的配料，但由于只能点一个披萨，没人能保证所有要求都被满足。你能订购一个至少满足每个朋友至少一个要求的披萨吗？

披萨店提供以下配料（每个配料可选择包含或不包含）：

朋友的偏好由一行文本描述。例如：

• +O-H+P; 表示该朋友接受包含洋葱，或不包含火腿，或包含意大利辣香肠。
• -E-I-D+A+J; 表示该朋友接受不包含额外芝士、意式香肠、蒜末，或包含凤尾鱼、墨西哥辣椒。

输入格式

输入由一系列披萨约束条件组成。每组约束条件包含1到12个配料约束列表，每个列表占一行，以单独一行的.结束。

配料约束列表由若干配料请求组成，以分号;结尾。
配料请求由符号（+表示包含，-表示不包含）和大写字母（A-P）组成。

输出格式

对每组约束条件，输出满足条件的披萨配料描述：

• 若存在解，输出Toppings: 后跟按字母序排列的配料代码（如ACFO）。
• 若无解，输出No pizza can satisfy these requests.。

每组输出独占一行。

输入示例 1

+A+B+C+D-E-F-G-H;  
-A-B+C+D-E-F+G+H;  
-A+B-C+D-E+F-G+H;  
.  
+A+B+C+D;  
+E+F+F+H;  
+A+B-G;  
+O+J-F;  
+H+I+C;  
+P;  
+O+M+L;  
+M-L+P;  
.  
+A+B+C+D;  
+E+F+F+H;  
+A+B-G;  
+P-O;  
+O+J-F;  
+H+I+C;  
+P;  
+O;  
+O+M+L;  
-O-P;  
+M-L+P;  
.  

输出示例 1

Toppings:  
Toppings: CELP  
No pizza can satisfy these requests.  

来源

South Central USA 1997