Game In Space

Hard
0/120
Average time to solve is 40m
profile
Contributed by
8 upvotes
Asked in company
Facebook

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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

Sample Input 1 :

1
5 8

Sample Output 1 :

3

Explanation for sample output 1:

Ninja has initial health ‘H’ = 5 and initial armour ‘A’ = 8.
So our first move will be to Mars. Health will increase by 3 and armour will increase by 2, resulting in ‘H’ = 8 and  ‘A’ = 10.
The second move will be to Venus resulting in ‘H’ = 4 (8-4) and ‘A’ = 2 (10-8).
The third move will be to Mars resulting in ‘H’ = 7 (4+3) and ‘A’ = 4 (2+2).
Now, we can either move to Venus or Saturn. Moving to Venus makes ‘A’ = -4 (4-8) and ends the game. Moving to Saturn makes ‘H’ = -3 (7-10) and ends the game. Therefore, we can not make any move.
So the sequence is Mars ->Venus -> Mars and the maximum survival time is 3 units.

Sample Input 2 :

2
8 4
3 3

Sample Output 2 :

3
1

Explanation for sample output 2:

(I) For the first test case:
Ninja has initial health ‘H’ = 7 and initial armour ‘A’ = 4.
So our first move will be to Mars and health will increase by 3 and armour will increase by 2, resulting in ‘H’ = 11 and  ‘A’ = 6.
The second move will be to Saturn resulting in ‘H’ = 1 (11-10) and ‘A’ = 11 (5+6).
The third move will be to Mars resulting in ‘H’ = 4 (1+3) and ‘A’ = 13 (11+2).
Now we can not make any move.
So the sequence is Mars -> Saturn -> Mars and the maximum survival time is 3 units.

(II) For the second test case:
Ninja has initial health ‘H’ = 3 and initial armour ‘A’ = 3.
So our first move will be to Mars and health will increase by 3 and armour will increase by 2, resulting in ‘H’ = 6 and  ‘A’ = 5.
Now we can not make any move.
The maximum survival time is 1 unit as Ninja has visited only Mars.
Hint

Can we find a way to calculate all possible ways and choose the one with maximum time?

Approaches (3)
Recursive

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.
  • Return the value returned by SOLVE.
Time Complexity

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.

Space Complexity

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)).

Code Solution
(100% EXP penalty)
Game In Space
Full screen
Console