HapMap - MarisaOJ: Marisa Online Judge

HapMap

Time limit: 2000 ms
Memory limit: 256 MB
Building the human HapMap can assist in diagnosing diseases and developing new treatments. In HapMap construction, **Haplotype** and **Genotype** are two fundamental biological concepts, simplified as follows: 1. A **Haplotype** $H = (h_1, \ldots, h_n)$ is a sequence of length $n$, where each $h_i$ can only be $0$ or $1$. 2. A **Genotype** $G = (g_1, \ldots, g_n)$ is a sequence of length $n$ created by matching two Haplotypes $H = (h_1, \ldots, h_n)$ and $H' = (h'_1, \ldots, h'_n)$ using the following rules: - $g_i = 0$ if $h_i = h'_i = 0$; - $g_i = 1$ if $h_i = h'_i = 1$; - $g_i = 2$ if $h_i \neq h'_i$. Thus, each pair of Haplotypes $H$ and $H'$ generates a unique Genotype $G$, but a Genotype $G$ can be created from multiple Haplotype pairs. A person’s genetic information is determined by a pair of Haplotypes. For research purposes, scientists need to decode Haplotypes from Genotypes. Since this decoding is not unique, scientists aim to find the smallest set of Haplotypes such that each Genotype is derived from two Haplotypes in this set. **Objective**: Given the Genotype information $G_1, \ldots, G_k$ of $k$ people, find $k$ pairs of Haplotypes $(H_1, H'_1), \ldots, (H_k, H'_k)$ corresponding to the $k$ people such that the set $\{H_1, \ldots, H_k, H'_1, \ldots, H'_k\}$ has the smallest possible size. ### Input - The first line contains two integers $k$ and $n$ ($k \leq 100; n \leq 200$); - The next $k$ lines each contain a string of length $n$, representing the Genotype $G_t$ of the $t$-th person. ### Output - Print a positive integer $p$, the size of the set of Haplotypes found. - The next $p$ lines, each containing a string representing a Haplotype. ### Example Input: ``` 2 4 1212 1110 ``` Output: ``` 2 1110 1011 ``` ### Scoring There are 10 tests, each worth 10.0 points. Let $p$ be the number of Haplotypes you found and $r$ be the benchmark result. If $p > 2k$, you will score 0 points. Otherwise, you will score $10.0 \times \min\\{1, \left(\frac{r}{p}\right)^3\\}$. ### Subtasks - **Subtask 1 (50 points)**: $k \leq 10$. - **Subtask 2 (50 points)**: No additional constraints.