CCC '06 S1 - Maternity

View as PDF

Submit solution


Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

2006 Canadian Computing Competition, Stage 1

Alice and Bob are fruit flies. They are now the proud parents of a new baby girl fly. Unfortunately, due to a slight mix-up, the nurses in the maternity ward at the hospital aren't sure which baby fly is their daughter. Luckily they've hired you to help them out. Using full genetic profiles of the parents, can you figure out which baby fly is theirs?

Recall from biology that attributes (like eye colour, hair colour, etc) are inherited, or passed, from generation to generation. A single gene controls each such attribute. Alternative versions of each gene, called alleles, account for the variation in the attributes. For example, the gene for eye colour exists in two versions, one for brown eyes and one for blue eyes. For each attribute, a fruit fly has two alleles, one inherited from each parent.

If two alleles differ, then one, the dominant allele, will appear in the fruit fly's appearance. The other, or recessive allele, does not affect the fruit fly's appearance. Conventionally, the dominant allele is represented by an uppercase letter, and the recessive allele by a lowercase letter. For example, consider the gene for eye colour, B. Each fruit fly has two alleles, each is either that of brown eyes (B, dominant) or blue eyes (b, recessive). If the fruit fly has BB or Bb, she will have brown eyes; if the fruit fly has bb, she will have blue eyes.

When reproducing, each parent fruit fly passes exactly one allele for each gene to its child. We can draw a Punnett square to see all possible allele combinations for the child. For example, here is the Punnett square for possible offspring of Alice (Bb) and Bob (Bb):

Bob
B b
Alice B BB Bb
b Bb bb

Unfortunately, the full genetic profiles of the babies were not available (as they take weeks to process). All we have are the attributes of the baby – whether or not they have brown eyes, hair colour, etc. Can you use this information, with the full genetic profile of the parents, to determine which babies could not possibly be theirs?

Input Specification

Luckily for you, our fruit flies are simple and have exactly five genes, labelled A through E.

The input begins with two lines, describing the mother and father, respectively. Each line consists of five pairs of letters, one pair for each gene. Each pair describes the two alleles the parent has for a particular gene. These alleles are listed in order (from A through E).

Next is a line with the number X, X \le 10, the number of babies to check. Following are X lines describing the attributes of the baby. Each line consists of five letters in order (from A through E). An uppercase letter denotes the baby shows the attribute of the dominant allele, and a lowercase letter denotes the baby shows the attribute of the recessive allele. For example, if the baby has brown eyes, the letter B will be written; if the baby has blue eyes the letter b will be written.

Output Specification

For each baby test, output the line Possible baby., if the baby could possibly be their offspring, or Not their baby! if impossible.

Sample Input

AABbCcddEe
AaBBccddee
5
ABCdE
aBcdE
ABcdE
ABCde
ABcDe

Sample Output

Possible baby.
Not their baby!
Possible baby.
Possible baby.
Not their baby!

Explanation

Baby 2 could not be their child. The baby has attribute a, which is recessive; therefore the baby must have alleles aa. The first parent has AA, and could not have given her baby an a. Baby 5 could not be their child. The baby has attribute D, but both parents have alleles dd and could not have given their baby a D. All other babies could possibly be their children.

CCC problem statements in large part from the PEG OJ


Comments


  • 0
    Cameron  commented on May 15, 2018, 9:45 p.m.

    Why is using gets() so bad? In my program, I originally used gets, then got the answer wrong. When I saw the error, I replaced gets with cin, and got everything right. Why can't I use gets in my programs?


  • 0
    zaz_wa_zandi13  commented on Dec. 21, 2017, 12:10 a.m.

    In the example they are all possible but the last? Right...?


    • 0
      ZippIE  commented on Dec. 21, 2017, 8:50 a.m.

      In the second case, the baby had a lowercase 'a', which is only possible if both parents have a lowercase. However, in this case, only one of the parents have a lowercase.


  • 0
    AlanL  commented on Oct. 29, 2017, 7:38 p.m.

    I don't understand why my second case is wrong.


  • 0
    Itachi  commented on April 16, 2016, 7:21 p.m.
    Typo

    Next is a line with the number X, X ? 10

    Is that a < sign, >, sign, &leq; sign, or &geq; sign? I'm confused.


    • 0
      cheesecake  commented on April 16, 2016, 7:53 p.m.

      Fixed.


  • 1
    bobhob314  commented on Dec. 21, 2014, 6:00 p.m.
    SNOWBLIND

    Y!!! NOW IT ONLY 5 PTS x( I CRI EVERTIEM


    • 0
      bobhob314  commented on Dec. 21, 2014, 6:52 p.m.
      Error in Sample Input

      There are two spaces at the end of every baby attributes. Please fix this for my progeny.

      My gramercies,

      bob


      • 0
        BMP  commented on Dec. 22, 2014, 1:37 a.m.

        u forgot the hob


      • 0
        FatalEagle  commented on Dec. 21, 2014, 7:01 p.m.

        It is done.


  • 5
    snowblind  commented on Dec. 1, 2014, 9:27 p.m.
    point

    if i can solve it i dont think its worth 10 points


    • 0
      Dordor1218  commented on April 1, 2018, 9:42 a.m.

      YYYYYYYYYYYYYYYYY!!!!!!!!!!


    • 3
      FatalEagle  commented on Dec. 2, 2014, 2:45 p.m.

      It has been fixed.


    • 0
      BMP  commented on Dec. 1, 2014, 10:26 p.m.

      lmfao