Practice 10 - Southwestern Europe Regional Contest 2009, Warmup - E
A colony of alien bacteria has recently been discovered close to a crater in New Mexico. Dr. Poucher is in charge of the scientific team at the ICPC BioLab committed to the study of the alien DNA structure. We briefly sketch their discoveries here.
Alien DNA molecules have the structure of a circular sequence. Each sequence is composed of nucleotides. There are 26 different types of nucleotides, and each of them can occur in two faces. It is very important to remark that in any given alien DNA molecule, every nucleotide either does not appear at all or appears exactly twice (hence, the length of a DNA molecule is an even integer between 2 and 52). In case a nucleotide occurs twice, each occurrence can be of either type independently. Alien bacteria have two types of extremities, which in the technical biological jargon are referred to as arms and legs. A major discovery of Dr. Poucher's team is a method to determine the exact number of arms and legs of a bacterium by examining its DNA structure.
Here we represent each nucleotide as a letter of the alphabet. We refer to the different nucleotides as a, A, ... , z, Z, where the lowercase and uppercase forms of a letter represent the two possible faces a nucleotide may appear with; we shall also use a/A, b/B, ... , z/Z to refer to a nucleotide in either face.
To determine the number of extremities, Dr. Poucher starts by initializing two counters of arms and legs to zero, and then proceeds to perform a number of surgeries, transforming a DNA sequence into another one. After each transformation, you may need to increase some of the counters, depending on the type of surgery applied. When the empty sequence of nucleotides (which will be denoted by ø) has been reached, the number of extremities of the original molecule has been found. The possible surgeries are:
the previous surgeries to reduce the size of the DNA molecule and finish the calculation.
However, alien bacteria do not present both arms and legs at the same time. This is due to the fact that, in their early development, a leg, in the presence of one or more arms, becomes two arms. Because of the above, the end result is either a number of arms or a number of legs, but not both at the same time. In order to avoid expensive surgical procedures, Dr. Poucher has hired you to write a program that computes the number of arms and legs a bacterium will develop, given its DNA sequence. It is guaranteed that the result is determined uniquely by the original string, regardless of the particular sequence of surgeries applied.
Each test case consists of a string of even length between 2 and 52, inclusive, representing the DNA structure of an alien bacterium. All characters are letters. There will be one case per line in the input. The last line contains the word "END" and must not be processed.
The output for each test case should have exactly one line, containing the number of arms or legs the bacterium will have, followed by the word "arms" or "legs" respectively (if the number is 1, the words should be in singular). In case there will be neither arms nor legs, the program should print the word "none".
rkrk abcdeABCDE shcoOCfFHS END
1 arm 2 legs none
Source: Southwestern Europe Regional Contest 2009