Wednesday 4 March 2015

A Case Study

Problem :
Scientist recently found a new element X, which can have different isotopes up to an atomic value of 199.
Specialty of element X is that when two atoms fuse they produce energy multiple of their atomic value and forms an atom with atomic value of their multiple modulus 199.
For Example :
If atom1 with value 56 and atom2 with value 61 fuse.
They produce energy of 3416 KJ (56 * 61)
Resulting atom will have atomic value (56*61) mod 199 = 33
Scientists created a nuclear reactor to create energy by this method.
Every day they get several atoms of  X from supplier in a particular sequence. Since this element highly radioactive they can’t risk by changing
its sequence. So each atom can fuse only with another atom nearby.
Nevertheless scientists can choose order of fusion thereby maximizing total energy produced.
Now, for given sequence of atomic values, output maximum energy that can be produced.
For Example :
If sequence of atoms are 56,61 & 2
Then they can produce 3416KJ by fusing 56&61 which results in an atom of value 33.
Then they can fuse 33 and 2 to get energy of 66KJ. So total energy generated is 3482.
But if they cleverly choose to fuse atoms 61 & 2 first then they generate 122 KJ with a resulting atom of value 122.
Then if they fuse 122 and 56, they can generate 6832 KJ. So the total energy is 6954.
Hence Maximum energy that can be generated from this sequence is 6954.

INPUT FORMAT :
Input starts with a number specifying number of inputs(n) followed by n space separated integers
specifying atomic values of n atoms.
Line 1  N,where N is the number of atoms in the  sequence to be fused.
Line 2  a1 a2 a3 .... an . where ai -> Atomic value of i th atom. and two atoms are space delimited.

Constraints:
   0 < ai < 199
   1 < n < 1000

OUTPUT FORMAT:
In Line 1  For Valid Input,print E,where E is Integer stating maximum energy that can be produced
For Invalid Input,print INVALID INPUT .


SAMPLE INPUTS AND OUTPUTS :

Sr.no            Input                Output
1                  3
                    15 75 60           8925

2                  J                        INVALID INPUT

3                  3
                    15 0 6               INVALID INPUT

4                  3
                    5 5 199             INVALID INPUT

5                  4
                    15 75 60 45      18515



                                                   :ANALYSIS:
Here, we will be given a sequence of integers (check with constraints provided, if input doesn't satisfy the constraints , exit by prompting INVALID INPUT ) . We should not change the  sequence .
We have to find a pair of elements (adjacent elements only) which maximizes the produced atom's atomic value ((first element's atomic value* second element's atomic value )%199) from the given sequence . Fuse them ( update total energy(multiplication of atomic values of two atoms) and replace those two atoms with new atom produced from them (its atomic value will be (first element's atomic value* second element's atomic value )%199 ) . Do this until we have only one atom in the sequence (In this case we don't have another atom to fuse with and this condition violates one of the constraints provided ) .
                If you observe, our data-structure is shrinking  during execution. Hence, using linked list will be a good idea .

Here is the   PROGRAM IN C .
      Let me know if you have any different approach .