DNA computing

Time Limit: 3000 ms

Memory Limit: 65536 ms

Description

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 ,and in the encoding set Z of DNA strands whose length is L, ,and ,search the subset W of Z which satisfies (any subset of Z can be treat as a code set): (1) ,the total number of A、C in is L/2; (2) ,the hamming distance (the Hamming distance between two strings of equal length is the number of positions for which the corresponding symbols are different)between and 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 are two subset satisfying the two conditions. If is a subset of ,then is better than . otherwise, we firstly order the elements of them independently based on lexicographic. then, we get the first element from and the first element from . We consider to be better than if is in front of in lexicographic. on the contrary, we think is better than if is behind . On the other hand, if is the same as , we then get the second element from and the second element from , if they are also the same ,we will get the next pairs until we can evaluate them. For examples : (1) is better than because is a subset of . (2) Firstly ,we order them, so Then is better than because is in front of . Now , we will give you the length L and the distance D, can you find the best code set.

Input

There are several cases. Each case contains two integers, L (0

Output

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.

Sample Input

2 2

Sample Output

4
AG
CT
GA
TC

Hint

Source

3rd Central South China Programming Contest

提交代码