# uva 565 Pizza Anyone?

You are responsible for ordering a large pizza for you and your friends. Each of them has told you what he wants on a pizza and what he does not; of course they all understand that since there is only going to be one pizza, no one is likely to have all their requirements satisfied. Can you order a pizza that will satisfy at least one request from all your friends?

The pizza parlor you are calling offers the following pizza toppings; you can include or omit any of them in a pizza:

 Input Code Topping A Anchovies B Black Olives C Canadian Bacon D Diced Garlic E Extra Cheese F Fresh Broccoli G Green Peppers H Ham I Italian Sausage J Jalapeno Peppers K Kielbasa L Lean Ground Beef M Mushrooms N Nonfat Feta Cheese O Onions P Pepperoni

Your friends provide you with a line of text that describes their pizza preferences. For example, the line

+O-H+P;


reveals that someone will accept a pizza with onion, or without ham, or with pepperoni, and the line

-E-I-D+A+J;


indicates that someone else will accept a pizza that omits extra cheese, or Italian sausage, or diced garlic, or that includes anchovies or jalapenos.

## Input

The input consists of a series of pizza constraints.

A pizza constraint is a list of 1 to 12 topping constraint lists each on a line by itself followed by a period on a line by itself.

A topping constraint list is a series of topping requests terminated by a single semicolon.

An topping request is a sign character (+/-) and then an uppercase letter from A to P.

## Output

For each pizza constraint, provide a description of a pizza that satisfies it. A description is the string Toppings: " in columns 1 through 10 and then a series of letters, in alphabetical order, listing the toppings on the pizza. So, a pizza with onion, anchovies, fresh broccoli and Canadian bacon would be described by:

Toppings: ACFO


If no combination toppings can be found which satisfies at least one request of every person, your program should print the string

No pizza can satisfy these requests.


on a line by itself starting in column 1.

## Sample Input

+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;
.


## Sample Output

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
#include <algorithm>
#define LL 16//ABCDEFGHIJKLMNOP
using namespace std;
char instr[50+5]={'\0'};
int prefre[26+5]={0};//-1 is without  1  is  with  0 is not refer to this
int prefres[20+5][26+5]={0};//input the prefres
int prefrescnt=0;//maze 's count
char minstr[26+5]={'\0'};//output this or cmp for this
char prestr[26+5]={'\0'};//preference string but not must be minstr
int flag=0;//whether find the case satisfy all people at least one constraint
/*switch the string to the prefres int array*/
int switchpre(char str[],int ind)
{
int i=0;
while(str[i]!=';')
{
if(isupper(str[i]))
{
if(str[i-1]=='+')
prefres[ind][str[i]-'A']=1;
else
prefres[ind][str[i]-'A']=-1;
}
i++;
}
return(0);
}
/*switch the array to string*/
int switchstr(char str[],int pre[])
{
int i=0,k=0;
str[0]='\0';
for(i=0;i<=LL-1;i++)
{
if(pre[i]==1)
{
str[k]=i+'A';
k++;
}
}
str[k]='\0';
return(0);
}
/*DFS the people constraint*/
int DFS(int cur)
{
if(flag)	return(0);
if(cur==prefrescnt)
{
switchstr(prestr,prefre);
memcpy(minstr,prestr,sizeof(prestr));
flag=1;
return(0);
}
else
{
int i=0;
for(i=0;i<=LL-1;i++)//pick a 1 or -1 add to the prefre array
{
if(prefres[cur][i]!=0)
{
if(prefre[i]==0)
{
prefre[i]=prefres[cur][i];
DFS(cur+1);
if(flag)	return(0);
prefre[i]=0;
}
else if(prefre[i]==prefres[cur][i])//this privilege is higher than prefre[i]==0
{
DFS(cur+1);
if(flag)	return(0);
}
}
}
}
return(0);
}
/*for test*/
int test()
{
return(0);
}
/*main process*/
int MainProc()
{
while(scanf("%s",instr)!=EOF)
{
//init
memset(prefre,0,sizeof(prefre));
memset(prefres,0,sizeof(prefres));
memset(minstr,'Z',sizeof(minstr));
memset(prestr,'\0',sizeof(prestr));
prefrescnt=0;
switchpre(instr,prefrescnt);
prefrescnt++;
while(scanf("%s",instr)!=EOF&&instr[0]!='.')
{
switchpre(instr,prefrescnt);
prefrescnt++;
}
flag=0;
DFS(0);//the depth is people constraint
if(flag)
{
printf("Toppings: %s\n",minstr );
}
else
{
printf("No pizza can satisfy these requests.\n");
}
}
return(0);
}
int main(int argc, char const *argv[])
{
/* code */
MainProc();
return 0;
}


07-20 1537

07-13 608

08-30 1569

10-26 623

09-05 422

08-02 1053

08-07 229

08-06 1158

08-06 992

05-28 2175
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.3653225302696228, "perplexity": 7986.429861977292}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-30/segments/1531676594018.55/warc/CC-MAIN-20180722213610-20180722233610-00468.warc.gz"}