So today there was a practice round of TCS’s coding contest and this was the toughest question. I tried to use DP to solve this but I am unable to divide it into subproblems (is it solvable by DP?) I just need a little hint on how to solve it!
Problem : IsotopeScientist recently found a new element X, which can have different isotopes upto an atomic value of 199. Speciality 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.
So,
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. Everyday they get several atoms of X from supplier in a particular sequence. Since this element highly radioactive they cant 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 Eg:
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 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.
Constraints:
0 < ai < 199
1 < n < 1000
OUTPUT:
For Valid Input, print
E, where E is Integer stating maximum energy that can be produced
For Invalid Input,print
INVALID INPUT