Old pals P93727
Some pals from the good old days at the university plan to meet again and have a party. To decide how the party will be, they have written a list of categories (for food, music, etc), each one with several possibilities. All the categories are mutually independent, that is, what is chosen for a category does not affect what can be chosen for another one.
Consider the first example in the sample input. Depending on the cooker, they can have as main dish either fast food or vegetarian food. Depending on who chooses the music, it can be classic, alternative or heavy. One of the friends has two specialties: making milk shakes and baking croissants, but he has only time for one of them. Finally, they can even enjoy a sauna or a swimming pool, depending on whose house the party takes place.
[r]
They are too fastidious, but they finally agree to require two conditions, and to go to the party if at least one of them is satisfied. Following the example, Mr. Morito likes milk shakes and saunas, Mr. Vinyes prefers alternative music and croissants, Mr. Masdeu likes heavy music and vegetarian food, while Mr. Maltines enjoys fast food and saunas. One possible solution is eating vegetarian food and croissants in a house with sauna, listening to any kind of music (or to no music at all).
Let us formalize the problem. There is a list of categories and a list of friends. Every category has several possibilities. Every friend asks for two different conditions chosen among the possibilities of the categories. Your task is to decide if there is a way to pick (at most) one possibility per category so that at least one condition per friend is satisfied.
Input
Input begins with the number of cases. Every case has two parts: the first for the categories, the second for the conditions. The categories’ part begins with a number c ≥ 1 followed by c lines, each one with at least two possibilities (strings). The conditions’ part begins with a number 1 ≤ f ≤ 1000 followed by f lines, each one with three strings: the surname’s friend and two different conditions present in the categories part.
Every string has at most 20 letters and underscores. The strings in the categories’ part of the same case are all different. For each case, the total number of possibilities of all the categories is at most 200.
Output
For every case, print the case number, followed by the right answer “yes” or “no”.
Input
3 4 fast_food vegetarian_food classic_music alternative_music heavy_music milk_shakes croissants sauna swimming_pool 4 Morito milk_shakes sauna Vinyes alternative_music croissants Masdeu heavy_music vegetarian_food Maltines fast_food sauna 2 aa bb cc xx yy zz 3 f aa xx g bb yy h cc zz 1 a b c d e 1 Lonesome b d
Output
Case #1: yes Case #2: no Case #3: yes
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++