(This assignment is based on a problem used in the ACM Programming Contest, Mid-Atlantic Region, in 2005.)

Dr. Montgomery Moreau has been observing a population of Northern Madagascar Pie-bald Shrews in the wild for many years. He has made careful observations of all the shrews in the area, noting their distinctive physical characteristics and naming each one.

He has made a list of significant physical characteristics (e.g., brown fur, red eyes, white feet, prominent incisor teeth, etc.) and taken note of which if these appear to be dominant (if either parent has this characteristic, their children will have it) or recessive (the children have this characteristic only if both parents have it).

Unfortunately, his funding from the International Zoological Institute expired and he was forced to leave the area for several months until he could obtain a new grant. During that time a new generation was born and began to mature. Upon returning, Dr. Moreau hopes to resume his work, starting by determining the likely parentage of the each member of the new generation.

This program should help him to match children up with their possible parents.

Input

The program reads all input from standard in (cin).

The first line of input will containing a sequence of 1 to 80 consecutive D and R characters describing a list of physical characteristics, indicating whether each is dominant or recessive.

After this line will follow several lines, each describing a single adult shrew. Each shrew is described by a name of 1-32 non-blank characters terminated by a blank space, then a single M or F character indicating the gender of the animal, another blank space, then a list of consecutive 0 or 1 characters, describing the animal. A 1 indicates that the animal possesses that physical characteristic, a 0 indicates that it does not. The list of adults is terminated by a line containing only the string ***.

This is followed by one or more lines describing juvenile animals. These contain a name and description, each formatted identically to those for the adults, separated by a blank space. The list of juveniles is terminated by a line containing only the string ***.

Output

For each juvenile animal, print a single line consisting of the animals name, the string by , then a (possibly empty) list of all possible parents for that animal. A set of parents should be printed as the name of the mother, a hyphen, then the name of the father. If the animal has multiple pairs of possible parents, these pairs should be printed in alphabetic (lexicographic) order first by the mothers name, then by the fathers name among pairs where the mother is the same. Each pair should be printed separated by the string or .

Example 1 Given the input:

RDDR Speedy M 0101 Jumper F 0101 Slowpoke M 1101 Terror F 1100 Shadow F 1001 *** Frisky 0101 Sleepy 1101 *** The output should be and it is: Frisky by Jumper-Slowpoke or Jumper-Speedy or Shadow-Speedy Sleepy by Shadow-Slowpoke

Example 2 Given the input:

DRRD Speedy M 0101 Jumper F 0101 Slowpoke M 1101 Terror F 1100 Shadow F 1001 *** Frisky 0101 Sleepy 1101 ***

The output should be: Frisky by Jumper-Speedy Sleepy by Jumper-Slowpoke or Terror-Slowpoke or Terror-Speedy

But it is: Frisky by Jumper-Speedy Sleepy by Jumper-Slowpoke or Terror-Slowpoke Problem Find and fix the error in the code using cerr to debug.

Shrew.cpp #include #include #include #include

using namespace std;

struct Shrew { string name; string genes;

bool couldBeDescendedFrom (Shrew& mother, Shrew& father, string dominance); };

bool Shrew::couldBeDescendedFrom (Shrew& mother, Shrew& father, string dominance) { for (int i = 0; i < dominance.length(); ++i) { if (dominance[i] == 'D') { if (genes[i] == '1') { if ((mother.genes[i] = '0') && (father.genes[i] == '0')) { return false; } } else { if ((mother.genes[i] == '1') || (father.genes[i] == '1')) { return false; } } } else { if (genes[i] == '1') { if ((mother.genes[i] == '0') || (father.genes[i] == '0')) { return false; } } else { if ((mother.genes[i] == '1') && (father.genes[i] == '1')) { return false; } } } }

return true; }

void sort (vector& v) { for (int i = 1; i < v.size(); ++i) { string temp = v[i]; int p = i - 1;

while (p >= 0 && v[p] > temp) { v[p+1] = v[p]; --p; } v[p+1] = temp; } }

int main (int argc, char** argv) { string dominance; cin >> dominance; string nm;

vector females; vector males;

while (cin >> nm && nm != "***") { Shrew shrew; shrew.name = nm; char gender; cin >> gender >> shrew.genes;

if (gender == 'M') { males.push_back(shrew); } else { females.push_back(shrew); } }

while (cin >> nm && nm != "***") { Shrew juvenile; juvenile.name = nm; cin >> juvenile.genes;

bool firstPair = true; cout << juvenile.name << " by ";

vector pairs; for (int f = 0; f < females.size(); ++f) { for (int m = 0; m < males.size(); ++m) { if (juvenile.couldBeDescendedFrom(females[f], males[m], dominance)) { pairs.push_back (females[f].name + "-" + males[m].name); } } }

sort (pairs);

for (int i = 0; i < pairs.size(); ++i) { if (i > 0) { cout << " or "; } cout << pairs[i]; } cout << endl; }

return 0; }