DNA computing

Time Limit:  3 s      Memory Limit:   64 MB
Submission:1     AC:0     Score:99.98


DNA computing is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computer technologies. DNA computing, or, more generally, molecular computing, is a fast developing interdisciplinary area. Research and development in this area concerns theory, experiments and applications of DNA computing. DNA computing is fundamentally similar to parallel computing in that it takes advantage of the many different molecules of DNA to try many different possibilities at once. So, many NP problem can be solved through DNA computing , such as Hamiltonian path problem, SAT problems, and so on.

The core reaction of DNA computing is the specific hybridization, which may results in incorrect or undesirable computations. Therefore, so far much works have focused on designing the DNA sequences to make the molecular computation more reliable.

The DNA encoding problem can be described as follows: the encoding alphabet of  DNA sequence is the set of nucleic acid bases Σ={A, C, G, T},and in the encoding set Z of DNA strands whose length is L, Z=Σ1={<b1b2...bL>|bi∈Σ, i=1,2,...,L}, and |Z|=4L, search the subset W of Z which satisfies (any subset of Z can be treat as a code set):

(1) ∀xi∈W, the total number of AC in xi is L/2;

(2) ∀xi, xj∈W, the hamming distance the Hamming distance between two strings of equal length is the number of positions for which the corresponding symbols are differentbetween xi and xj is at least D.

In order to simplify the encoding problem, we don’t want you to find such a subset with the biggest size, we only want you to find the best subset satisfying the two conditions. The strategy to compare two subset is as follows:

Suppose W1, W2 are two subset satisfying the two conditions. If Wi(i=1, 2) is a subset of W(j=2,1), then Wj (j=2,1) is better than Wi (i=1,2). Otherwise,  we firstly order the elements of them independently based on lexicographic. then, we get the first element x1 from W1 and the first element y1 from W2. We consider W1 to be better than W2 if x1 is in front of y1 in lexicographic.  on the contrary, we think W2 is better than W1 if x1 is behind y1. On the other hand, if x1 is the same as y1, we then get the second element x2 from W1 and the second element y2 from W2 , if they are also the same ,we will get the next pairs until we can evaluate them.

For examples :

(1) W1 = { A, C, G, T}, W2 = {A, T}

W1 is better than W2 because W2 is a subset of W1.

(2) W1={AC, CT, AT}, W2={AG, AC}

Firstly ,we order them, so W1={AC, AT, CT}, W2={AC, AG} 

Then W2 is better than W1 because AG is in front of AT.

Now , we will give you the length L and the distance D, can you find the best code set.


There are several cases. Each case contains two integers, L (0<L25) and D (0DL) .


For each case, output several lines, the first line is the size of the code set, then print all the elements of the code set in lexicographic. A element per line.


2 2


3rd Central South China Programming Contest