|Online Judge||Problem Set||Authors||Online Contests||User|
You have been reading Harry Potter series for some time. Since the final book will not be out in the store until 2007, and you are curious about what could happen in the final book of the series, you have decided to do some guessing by yourself. After rereading the series for some days, you have divided every piece of information you currently have into three categories:
Note that extracts and assumptions may have many different exclusive explanations leading to other theories and/or assumptions.
Because of personal preferences, you want to see some scenes in the next book come true much more than the others, thus you have assigned different values to different theories, each being an exponent of 2, less or equal to 2(number of theories − 1). You want to know what the maximal possible value of theories that can be argued as believable at the same time is; furthermore, since the less guesswork you do, the more reliable your theories are, you are interested in the minimum number of explanations you must make to make all those theories acceptable. Can you accomplish this seemingly impossible task?
The input consists of several cases, each followed by a blank line.
Each test case starts with three integers N, M and K (1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 1 ≤ K ≤ 100), the number of extracts from the book, the number of assumptions and the number of theories, respectively.
The following part describes extracts and assumptions. Extracts are always described before assumptions. Each description starts with one string S, the name of the extract/assumption, and an integer T in the next line, the number of different explanations you have come up with; T lines follow, on each line there is a string X, the explanation which leads to another assumption/theory.
The next part of test case consists of K descriptions of theories. Each description starts with one string S, the name of the theory, followed by one integer P, the value which you have assigned to this theory.
Two successive descriptions are separated by a line with one single character ‘
N = 0, M = 0, K = 0 indicates the end of input file and should not be processed by your program.
For every test case, output the maximum value followed by the minimum number of explanations you have to make in the format as indicated in the sample output. Print all the plausible theories (with the maximum total value) on the following lines. Separate the result of two successive inputs with one blank line.
2 3 1 Extract1 2 Assumption1 Assumption2 - Extract2 2 Assumption2 Assumption3 - Assumption1 2 Assumption2 Theory1 - Assumption2 0 - Assumption3 1 Theory1 - Theory1 1 0 0 0
Case 1: 1 4 Theory1
In order to make
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator