The PokeMart company rents various machines each of which has varying performances over time, from
unsatisfactory (where it produces large losses by destroying material) to outstanding (when it
is very useful and produces large profit). In each time unit, a machine has one of the following
'o': Outstanding, makes a profit of 100 in the time unit;
'e': Extraordinary, makes a profit of 10pounds in the time unit;
'g': Good, makes a profit of 1pounds in the time unit;
'a': Average, makes no profit and makes no loss;
'b': Bad, makes a loss of 1pounds in the time unit;
'i': Insufficient, makes a loss of 10pounds in the time unit;
'u': Unsatisfactory, makes a loss of 100pounds in the time unit.
The company supplies a potential customer with data about the performance of each machine
over time. For example, the data 'aabbg' for the first machine and 'ggg' for the second machine
would say that the first machine can run over 5 time units with two times average, two times
bad and one times good performance while the second machine can run over three time units
with good performance on each of them. The task is to identify the maximal profit achievable
in any contiguous time interval.
In order to help customers with the decision whether to rent one of the machines for some
time intervals, write a computer program which reads input as specified below and finds the
largest possible profit which can be obtained by renting the machine for a contiguous time
The output corresponding to an input of form 'abbg' should be 1 as only in the last time
unit some profit can be made. The output corresponding to 'ggbgg' should be 3 as it is profitable
to absorb the loss in the middle and to rent the machine over the full runtime, leading to an
overall profit of SGD 3. Consider a more complicated example 'gbggbuoeg' The maximum
profit is SGD 111, achieved during the interval 'eg' If the machine never perform better or
equal to average, a 0 should be returned for the performance.
In general, the task is to make sure that the output is the maximal possible value taken on a
interval. In the case of the input 'ggue' the possible intervals correspond to 'g'(1), 'gg'(2),
'ggu'(-98), 'ggue'(-88), 'gu'(-99), 'gue'(-89), 'u'(-100), 'ue'(-90) and 'e'(10). Among
these, the number 10 is the largest value and should be returned. Recall that the return value is
0 if every interval is evaluated with a negative number.
Note that the input is given for several machines, the data of each of them separated by a
comma and a period signaling the end of the data for the last machine. The algorithm must
provide for each of these machines the best possible value.
Your program must read from the standard input the following data. The data of various machines
are separated by a comma and the data for the last machine is followed by a period;
linebreaks and blanks can be ignored. The performance of the machine per time unit is indicated
with the letters 'u', 'i', 'b', 'a', 'g', 'e', 'o' as explained above.
ggggg ggaaa aaggg ggggg
ggggg gaaag gaaag aagaa
ggggg ggggg ggggg ggggg.
Your program must write to the standard output a sequence of numbers, one per each line where
the first number refers to the best performance of the first machine in a corresponding interval,
the second number refers to the second machine and so on. There are as many outputs as there
are commas and periods in the input.