#### Ninja is in space with his super spaceship having unlimited fuel. Ninja initially has a health level ‘H’ and his spaceship has an armour ‘A’. He decides to play a game, where at any instant he can be only on one of the 3 planets: VENUS, MARS or SATURN. At every unit of time, he has to change his location and you can assume he can change his location instantly. Each planet has different effects on health and armour which are :

```
Venus: Decreases health by 4, decreases armour by 8.
Mars: Increases health by 3, increases armour by 2.
Saturn: Decreases health by 10, increases armour by 5.
```

#### Now the game will end if either ‘H’ <= 0 or ‘A’ <= 0.

#### Your task is to find the maximum time Ninja can survive.

#### Note :

```
You can choose any of the 3 planets during your first move.
```

##### Input format :

```
The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow.
The first line of every test case contains 2 single space-separated integers representing initial health and initial armour respectively.
```

##### Output format :

```
For every test case, print a single integer representing the maximum time Ninja can survive.
The output of each test case is printed in a separate line.
```

#### Note :

```
You don’t have to print anything, it has already been taken care of. Just implement the given function.
```

###### Constraints :

```
1 <= T <= 10
1 <= H, A <= 10^3
Where ‘T’ denotes the number of test cases, ‘H’ is the initial health and ‘A’ is the initial armour.
Time Limit: 1sec
```

The idea is simple, we will check all the possible ways of choosing planets with the help of recursion and find out which combination gives maximum time.

Along with this, we will prefer to move Mars whenever possible as it is always beneficial to make a move to Mars.

- So we will make a recursive function named
**SOLVE**which will receive 3 parameters ‘H’, ‘A’ and ‘MOVE_MARS’. - Initialize a bool variable ‘MOVE_MARS’ = 0 ,where ‘MOVE_MARS’ == 0 indicates we can move to Mars .
- Base Case :
- When ‘A’ <= 0 or ‘H’ <= 0 then we will return -1 as we can’t move to any other planet now and we have already added 1 in time for this move.

- Check the value of the ‘MOVE_MARS’:
- If it is equal to 0, it means we are moving to Mars.
- Then increase ‘H’ by 3, ‘A’ by 2 and set ‘MOVE_MARS’ = 1. We then make a recursive call.
- Return 1 + the result received in above call.

- If the ‘MOVE_MARS’ is equal to 1, it means we have to move either to Saturn or Venus.
- Make two calls, one to Venus and other to Saturn by changing variables according to their effect and setting ‘MOVE_MARS’ = 0.
- Return 1+ the results received in the above call.

- If it is equal to 0, it means we are moving to Mars.
- Return the value returned by
**SOLVE**.

**Space Complexity:**O(n)

**Explanation:**

**O(min(H, A)** where ‘H’ is the initial health and ‘A’ is the initial armour.

The maximum depth of recursion stack space can be O(min(H, A)).

**Time Complexity:**O(2^n)

**Explanation:**

**O(2^min(H, A))** where ‘H’ is the initial health and ‘A’ is the initial armour.

As in each recursive call, we are making further at most 2 recursive calls till the value of ‘A’ or ‘H‘ is greater than 0.

Our last approach was very simple and easy, but its time complexity was of exponential order. We can improve our solution by taking care of the overlapping subproblems. Thus, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization

- So we will make a recursive function named
**SOLVE**which will receive 3 parameters ‘H’, ‘A’ and ‘MOVE_MARS’. - We will initialize a 2-D array, say ‘MEMO[2000][2000]’ with -1. Where MEMO[i][j] equal to -1 means the current state is not explored. Otherwise, it will store the maximum time Ninja can survive with health = ’i’ and armour = ’j’.
- Initialize a bool variable ‘MOVE_MARS’ = 0 ,where ‘MOVE_MARS’ == 0 indicates we can move to Mars .
- Base Case :
- When ‘A’ <= 0 or ‘H’ <= 0 then we will return -1 as we can’t move to any other planet now and we have already added 1 in time for this move.

- We will check the value of ‘MEMO[H][A]’ :
- If it is not equal to -1, then we can say we have already explored the result for the current state, so return ‘MEMO[H][A]’.

- Check the value of the ‘MOVE_MARS’:
- If it is equal to 0, it means we are moving to Mars.
- Then increase ‘H’ by 3, ‘A’ by 2 and set ‘MOVE_MARS’ = 1. We then make a recursive call.
- Set ‘MEMO[H][A]’ = 1+result received in above call and return ‘MEMO[H][A]’.

- If the ‘MOVE_MARS’ is equal to 1, it means we have to move either to Saturn or Venus.
- Make two calls, one to Venus and other to Saturn by changing variables according to their effect and setting ‘MOVE_MARS’ = 0.
- Set ‘MEMO[H][A]’ = 1+maximum of results received in above call and return ‘MEMO[H][A]’.

- If it is equal to 0, it means we are moving to Mars.
- Return ‘MEMO[H][A]’.

**Space Complexity:**O(1)

**Explanation:**

**O(1).**

We are using a 2-D array of size 2000*2000 in each case as the maximum value of H+A can be 2000.

**Time Complexity:**Other

**Explanation:**

**O(min(H, A))**, where ‘H’ is the initial health and ‘A’ is initial armour.

We make at most 2 recursive calls till the value of ‘A’ or ‘H‘ is greater than 0 and are storing the already calculated results in ‘memo’. Hence the overall time complexity will be O(min(H, A)).

**Java (SE 1.8)**

```
/*
```

Time Complexity: O(min(H, A))

Space Complexity: O(1)

Where H is the initial health and A is initial armour.

*/

import java.util.Arrays;

public class Solution {

static int solve(int h, int a, int moveMars, int[][] memo) {

// Base Case

if (h <= 0 || a <= 0) {

return -1;

}

// If we have already explored the current state

if (memo[h][a] != -1) {

return memo[h][a];

}

// Recursive calls

if (moveMars == 0) {

// Moving to Mars

return memo[h][a] = 1 + solve(h + 3, a + 2, 1, memo);

} else {

// Moving to Venus

int venus = 1 + solve(h - 4, a - 8, 0, memo);

// Moving to saturn

int saturn = 1 + solve(h - 10, a + 5, 0, memo);

// Return the maximum of Venus and Saturn

return memo[h][a] = Math.max(venus, saturn);

}

}

public static Integer gameSpace(Integer h, Integer a) {

int[][] memo = new int[2000][2000];

for (int i = 0; i < 2000; i++) {

Arrays.fill(memo[i], -1);

}

int ans = solve(h, a, 0, memo);

return ans;

}

}

**Python (3.5)**

```
'''
```

Time Complexity: O(min(H, A))

Space Complexity: O(1)

Where H is the initial health and A is initial armour.

'''

def solve(h, a, moveMars, memo):

# Base Case

if (h <= 0 or a <= 0):

return -1

# If we have already explored the current state

if (memo[h][a] != -1):

return memo[h][a]

# Recursive calls

if (moveMars == 0):

# Moving to Mars

memo[h][a] = 1 + solve(h + 3, a + 2, 1, memo)

return memo[h][a]

else:

# Moving to Venus

venus = 1 + solve(h - 4, a - 8, 0, memo);

# Moving to saturn

saturn = 1 + solve(h - 10, a + 5, 0, memo);

# Return the maximum of Venus and Saturn

memo[h][a] = max(venus, saturn)

return memo[h][a]

def gameSpace(h, a):

# Intializing the memo table

memo = [[-1 for j in range(2000)] for i in range(2000)]

solve(h, a, 0, memo)

return memo[h][a]

**C++ (g++ 5.4)**

```
/*
```

Time Complexity: O(min(H, A))

Space Complexity: O(1)

Where H is the initial health and A is initial armour.

*/

int solve(int h, int a, bool moveMars, vector>& memo) {

// Base Case

if (h <= 0 || a <= 0) {

return -1;

}

// If we have already explored the current state

if (memo[h][a] != -1) {

return memo[h][a];

}

// Recursive calls

if (moveMars == 0) {

// Moving to Mars

return memo[h][a] = 1 + solve(h + 3, a + 2, 1, memo);

} else {

// Moving to Venus

int venus = 1 + solve(h - 4, a - 8, 0, memo);

// Moving to saturn

int saturn = 1 + solve(h - 10, a + 5, 0, memo);

// Return the maximum of Venus and Saturn

return memo[h][a] = max(venus, saturn);

}

}

int gameSpace(int h, int a) {

// Intializing the memo table

vector> memo = vector> (2000, vector (2000, -1));

solve(h, a, 0, memo);

return memo[h][a];

}

In the earlier approach, we tried to find all the possible solutions and select the one with maximum survival time, but we really do not need to find all the possible solutions. Instead, we will use some greedy approach. We can see that it is always beneficial to go to Mars so for every odd second, we will go to Mars. Now for even seconds, we are left with Venus and Saturn. So we will choose Venus if possible else we will choose Saturn, as Venus decreases health less than Saturn.

- Initialize an integer variable ‘TURN’ = 0.
- Run an infinite while loop:
- If ‘TURN’ is even (we can go to Mars) then do:
- Increase ‘H’ by 3 and ‘A’ by 2.
- Increase ‘TURN’ by 1.

- If ‘TURN’ is odd, it means we have to choose between Saturn or Venus. So, do:
- If ‘H’ > 4 and ‘A’ > 8 (we can go to Venus):
- Decrease ‘H’ by 4 and ‘A’ by 8.
- Increase ‘TURN’ by 1.

- Else if ‘H’ > 10 (we can go to Saturn):
- Decrease ‘H’ by 10 and increase ‘A’ by 5.
- Increase ‘TURN’ by 1.

- If none of the above two conditions is met :
- We can not make a move, so break the loop.

- If ‘H’ > 4 and ‘A’ > 8 (we can go to Venus):

- If ‘TURN’ is even (we can go to Mars) then do:
- Return ‘TURN’.

**Space Complexity:**O(1)

**Explanation:**

**O(1).**

As we are using constant extra memory.

**Time Complexity:**O(n)

**Explanation:**

**O(min(H, A))**, where ‘H’ is the initial health and ‘A’ is the initial armour.

As we will keep on iterating till either of ‘A’ or ‘H’ is greater than 0.

**Java (SE 1.8)**

```
/*
```

Time Complexity: O(min(H, A))

Space Complexity: O(1)

Where H is the intial health and A is the initial armour.

*/

public class Solution {

public static Integer gameSpace(Integer h, Integer a) {

int turn = 0;

// Running a loop while h > 0 and a > 0

while (h > 0 && a > 0) {

// We can move to Mars

if (turn % 2 == 0) {

h += 3;

a += 2;

}

// We can not move to Mars

else {

// If we can move to Venus, we will go to Venus

if (h > 4 && a > 8) {

h -= 4;

a -= 8;

}

// If we can go to Saturn

else if (h > 10) {

h -= 10;

a += 5;

}

// If we can not make a move

else {

break;

}

}

// Increase turn by 1

turn++;

}

return turn;

}

}

**Python (3.5)**

```
'''
```

Time Complexity: O(min(H, A))

Space Complexity: O(1)

Where H is the intial health and A is the initial armour.

'''

def gameSpace(h, a):

turn = 0

# Running a loop while h > 0 and a > 0

while (h and a):

# We can move to Mars

if (turn % 2 == 0):

h += 3

a += 2

# We can not move to Mars

else:

# If we can move to Venus, we will go to Venus

if (h > 4 and a > 8):

h -= 4

a -= 8

# If we can go to Saturn

elif (h > 10):

h -= 10

a += 5

# If we can not make a move

else:

break

# Increase turn by 1

turn += 1

return turn

**C++ (g++ 5.4)**

```
/*
```

Time Complexity: O(min(H, A))

Space Complexity: O(1)

Where H is the intial health and A is the initial armour.

*/

int gameSpace(int h, int a) {

int turn = 0;

// Running a loop while h > 0 and a > 0

while (h and a) {

// We can move to Mars

if (turn % 2 == 0) {

h += 3;

a += 2;

}

// We can not move to Mars

else {

// If we can move to Venus, we will go to Venus

if (h > 4 and a > 8) {

h -= 4;

a -= 8;

}

// If we can go to Saturn

else if (h > 10) {

h -= 10;

a += 5;

}

// If we can not make a move

else {

break;

}

}

// Increase turn by 1

turn++;

}

return turn;

}