DMOPC '14 Contest 1 P6 - Biology Homework

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

Today you have some grade 11 biology homework and finally decide to start working on it after procrastinating on the Internet for a few hours. One of your problems is as follows:

Assume that in a particular species of plants, coloured flowers are dominant over white ones and that they are self-fertilized in nature (they mate between themselves). Assume that one heterozygous (alleles are distinct) coloured-flower plant, Cc, suddenly appears on an island and that its offspring thrive and multiply there in great numbers.

Assume also that it is an annual plant and that thus there is no chance for members of one generation to cross with those of another and that white and colored plants are equal with respect to natural selection. What will be the proportions of the colours of the flowers after the fifth generation?

Recalling today's class, you remember that when a plant with genotype AB (consisting of two alleles) self-fertilizes, the offspring is produced by the following algorithm:

  • First, choose a random allele with uniform probability (A or B).
  • Second, choose a random allele again with uniform probability (A or B). The two chosen alleles need not be distinct.
  • Lastly, concatenate the alleles chosen together. You will get a genotype with the same length as the original gene (AA, AB, BB). After the alleles are concatenated, order does not matter, so we consider AB to be the same as BA.
  • Some genotypes appear with a greater probability than others. For every AA, there are two of AB and one of BB. Thus, we say that AA has a 1 in 4 chance of appearing.

You think to yourself that this problem is a bit on the easy side, so you spice it up a little. You generalize the above algorithm to work with up to K alleles (the gene has K forms). You always start with a plant that has K alleles in its genotype — one allele of each possible form, and you call this generation 0. You wish to know the probability of a random member of the N^{th} generation having a certain combination of allele.

Because you are also a programmer, you want to write a program to produce the answer for you.

Input Specification

The first line of input will have K (1 \le K \le 5), N (0 \le N \le 10^{18}).

Output Specification

For each combination, output the probability of getting that genotype if you selected a random member of the population in the N^{th} generation with an absolute or relative error no more than 10^{-9}. Output the probabilities in nondecreasing order.

Sample Input

2 2

Sample Output


Explanation for Sample Input

For the sake of simplicity, we will use numbers to represent the different forms of the gene (referred to as alleles).

Note: In the sample output, 12 has a probability of 0.25, 11 has a probability of 0.375, and 22 has a probability of 0.375.

The parent genotype is 12. Since the flower self-fertilizes, imagine 12 being combined with 12 to form an offspring.

The table below is called a Punnett Square, and is used to predict the genotypes of the next generation.

    1   2
1  11  12
2  12  22

So for each generation, we assume 4 offspring from each genotype are produced. Notice that the ratio of 11 to 12 to 22 is 1 : 2 : 1.

We have now reached the first generation. Since there are now 4 plants, 4 Punnett Squares will be required.

    1   1
1  11  11
1  11  11

    1   2
1  11  12
2  12  22

    1   2
1  11  12
2  12  22

    2   2
2  22  22
2  22  22

We have now reached the second generation and thus have 16 genotypes. Counting, there are six 11 genotypes, four 12 genotypes, and six 22 genotypes. Calculating the probability (expressed as a decimal) for each of these, we obtain the desired output.


  • -2
    kobortor  commented on April 9, 2016, 9:54 a.m.

    So apparently


    Does not mean you have a 50-50 probability of picking either A or B, but a 2/3 for A and 1/3 for B.

  • 14
    quantum  commented on Dec. 23, 2014, 8:30 p.m. edited