Abhay - 1 year ago 67

C++ Question

Here's a problem from HackerRank (rated Medium):

When Daenerys, got her new phone there were no games in it. So she went to the play store and downloaded one of the top rated game called Princess and Angels.

In the game princess starts with 0 total strength. there are N angels before princess and her castle. And each i th angel give Ai strength. but some of the angels are actually evil wearing angel clothes and they give negative strength trying to fight with Princess. The game can be won if Daenerys can get through all the N angels without dying. Princess will die if her total strength ever gets less than 0. fortunately Princess has a special power. she can fight with an angel and reverse it's strength atmost once. if she use that power on i th angel with x strength, She can apply this power and make it to -x.

Daenerys can foresee the strengths of N angels. when passing through each angel, the strength is added to total strength. Princess can also reverse the strength of that angel before adding, but only once.

Given N Strengths of angels, can u help Daenerys figure out the best possible result she can have?.

print "She did it!" (without the quotes ) if she can win the game. Otherwise print the maximum position up to which she could reach (i.e. the position at which she died due to the negative total strength).

Input Format

First line of input contains T , number of testcases.

Each testcase have two lines, N in the first line and N space separated integers in the next line.

Constraints

1<=T<=1000

1<=N<=100000

-1000<=strength<=1000

Output Format

For each test case, print a single line denoting the answer to the problem.

And this is my attempt at the solution:

`#include <iostream>`

using namespace std;

int main() {

int strength, power, n, t, count = 1, i, pos;

cin>>t;

while(count <= t)

{

strength = 0;

power = 1;

cin>>n;

int a[n];

for(i = 0; i < n; i++)

cin>>a[i];

for(i = 0; i < n; i++)

{

if((strength + a[i]) < 0 && power == 1)

{

strength -= a[i];

power = 0;

}

else if((strength + a[i] < 0) && power == 0)

{

if(strength >= 0)

{

pos = i + 1;

strength += a[i];

break;

}

}

else if((strength + a[i]) >= 0)

strength += a[i];

}

if(strength >= 0)

cout<<"She did it!"<<endl;

else if(strength < 0)

cout<<pos<<endl;

count++;

}

return 0;

}

Answer Source

I think:

Imagine the following input:

```
5
6 -5 -2 -2 -2
```

Your algorithm will encounter the `6`

and add it, so strength becomes `6`

.

Next we encounter the `-5`

. Since this will not kill us we accept that loss. Strength becomes `1`

.

Next we come to the `-2`

. This will kill us (takes us to `-1`

) so we flip it using the power. Our strength becomes `3`

.

The following two `-2`

s will therefor kill us.

However if you had used the power on the `-5`

bringing the total strength to `11`

at that point, you would have got to the end, so in this case your answer is incorrect.