21855번 - DNA 점수출처다국어분류

It is known that the human DNA is represented by an integer number. On a microscopical level, the DNA consists of numerous genes. Considering the binary representation of the corresponding number of the DNA, we notice the following rule: digit 1 on the i^th position indicates the presence of the i^th gene, whereas digit 0 indicates its absence (i is a positive integer). Moreover, it was observed that any two distinct adults can give birth to a child whose DNA only contains the i^th gene if and only if the DNAs of both of the adults contain that gene.

Generate an array of 2000 non-negative integers representing the DNAs of a group of adults so that the total number of children with distinct DNAs that can be born from adults belonging to this group is as big as possible. (as big as possible doesn’t mean optimum). The scoring will respect the table below.

• This problem is “output-only”.
• The demanded array must contain non-negative integers from the range [0, 2²⁰ -1].
• All children must come from different adults, meaning that any 2 children must have at least one different parent.
• The two parents of a child must be distinct.

Considering that the adults have the following DNAs: 1, 5, 3, 6, 9, 12, the distinct DNAs of the children will be 1, 0, 4, 2, 8.