## ram188490

BAN USER- 0of 0 votes

AnswersThe amount of Magical Aura is calculated in terms of "Mana Points".

- ram188490 in India

On entering the forest he sees 'n' number of portals in front of him numbered from '0' to 'n-1' arranged in a straight line.

Each portal has a value written over it. He sees that the first and the last portals are damaged and cannot be activated (remain unactivated).

He can perform the following operations repeatedly to gain Magical Aura :

1. He can activate a portal 'x' (obviously not the first and the last one).

2. Let 'l' be the nearest unactivated portal to the left of 'x' and 'r' be the nearest unactivated portal to the right of 'x'.

3. On activating the portal 'x' he gains Mana points equal to the product of value of written over 'l' and the value written over 'r'.

4. A portal once activated cannot be activated again.

He stops when the above process cannot be continued anymore.

Note that 'nearest' is with respect to the portal currently being activated.

Now Sherlock is thinking what is the maximum amount of Magical Aura (Mana points) he can gain in this process.

Help him find this.

Input :

First line contains no of testcases 't'.

Next 't' testcases follow, first line of each is an integer 'n', representing number of portals inside the forest.

Next line contains 'n' space seperated integers which are the values written over the corresponding n portals.

Ouptut :

Output 'n' lines each having one integer denoting the maximum amount of Mana points he can gain for that particular testcase.

Constraints :

1 <= t <= 500

3 <= n <= 80

1 <= Value written over each portal <= 1000

Sample Input :

1

4

1 2 3 4

Sample Output :

12

Explanation :

We have only 2 choices :

1. Activate portal numbered 1 first, and portal numbered 2 next. The total Mana points are 1 * 3 + 1 * 4 = 7.

2. Activate portal numbered 2 first, and portal numbered 1 next. The total Mana points are 2 * 4 + 1 * 4 = 12.

So the answer is 12.| Report Duplicate | Flag | PURGE

Amazon Software Analyst Algorithm - 0of 0 votes

AnswersSherlock wants to recollect all the clues in his clue box. The clue box is very heavy and cannot be moved. Sherlock doesnt like much burden at once and therefore he will not carry more than two clues at any time. Thus after picking at most two clues, he will need to put them back in his clue box.

- ram188490 in India

Also, if he has taken a clue, he cannot put it anywhere except his Clue box (clues are too important for him to do so).

You are given the coordinates of the "Clue box" and the coordinates of the "clues" in cartesian

coordinate system. Sherlock covers the distance between any two points in the time

equal to the square of the euclidean distance between the points. Also, Sherlock is initially at the same position as his clue box.

Now being a brilliant programmer, you want to help Sherlock. Help him find the minimum time in which he can gather all the clues in his clue box.

Input :

First line contains t, the number of test cases.

First line of each test case contains two space separated integers Xb and Yb, the position of Sherlock's clue box.

Second line of each test case contains N, the number of clues.

This is followed by N lines each containing two space separated integers Xi, Yi which is the position of the ith clue.

Output :

For each test case, output in one line the minimum time required by Sherlock to gather all his clues.

Constraints :

1 <= T <= 100

1 <= N <= 24

-100 <= Xi, Yi <= 100

Sample Input :

2

-3 4

1

2 2

1 1

3

4 3

3 4

0 0

Sample Output :

58

32| Report Duplicate | Flag | PURGE

Software Trainee Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

no nothing is given about sorted array...it may be in any order

- ram188490 September 29, 2013Consider test case

2 100 19 20 10 9 100

Output 15200