What is the correct approach to solve SPOJ DIEHARD?

Question

I was trying to solve a practice question on SPOJ https://www.spoj.pl/problems/DIEHARD/ . However both my greedy approach resulted in Wrong Answer and recursion was too slow for the worst case.Can anyone tell how to approach this problem? I am looking for someone to point me in the right direction.

The game is simple. You initially have ‘H’ amount of health and ‘A’ amount of armor. At any instant you can live in any of the three places - fire, water and air. After every unit time, you have to change your place of living. For example if you are currently living at fire, you can either step into water or air.

• If you step into air, your health increases by 3 and your armor increases by 2
• If you step into water, your health decreases by 5 and your armor decreases by 10
  If you step into fire, your health decreases by 20 and your armor increases by 5

If your health or armor becomes <=0, you will die instantly

Find the maximum time you can survive.

Input:

The first line consists of an integer t, the number of test cases. For each test case there will be two positive integers representing the initial health H and initial armor A.

Output:

For each test case find the maximum time you can survive.

Answer 1

Okay, Firstly try solving it by greedy approach. It is obvious that air is the best choice possible as it increases both armor and health but you can go to air alternately only. So every odd(i.e 1,3,5...) move will be to air. Now we have to decide what to do with even moves?

So we have two choices Fire or water? We have to be reasonable and choose such a move that keeps both H and A above 0. Now jumping in fire costs health -20 even though it increases armor by 5, but hey wait, what is the use of increased armor if you don't get your health >0 . So if H>5 and A>10 choose water.

Now what if we are short of armor but have enough health? In that case we have no choice but to jump to fire.

So now we have a greedy approach:

So, if we have sufficient H and A, we'll go to water. Else, if H is sufficient enough and A is not sufficient, go to fire. Else, it's over!

Here is the ideone link of implementation: http://ideone.com/rkobNK

#include<stdio.h>
int main(){
    long long int x,i,a,b,t,h,arm;
    scanf("%lld",&x);
    for(i=0;i<x;i++){
        scanf("%lld %lld",&a,&b);
        if(a==0||b==0)
         printf("0\n");
        else{
            t=1;
            h=a+3;
            arm=b+2;
            while(1){
                if(h>5&&arm>10){
                    h=h-2;
                    arm=arm-8;
                    t=t+2;
                }else if(h>20&&arm<=10){
                    h=h-17;
                    arm=arm+7;
                    t=t+2;
                }else {
                    printf("%lld\n",t);
                    break;
                }
            }
     }
    }
    return 0;
} 

Answer 2

Here is another way to do it analytically:

a = number of times visiting air state
F = number of times visiting fire state
W = number of times visiting water state

M = a + F + W  // total moves

// positive
a >= 0
F >= 0
W >= 0

// because of the restriction of moving between states...
a <= F + W + 1
F <= W + a + 1
W <= a + F + 1

// the effect of armor and health...
H < -3a + 5H + 20F
A < -2a + 10W - 5F

Maximize M. You can do this by binary searching for M, or you can use linear programming.

Binary search loop:

int ok = 0;
int impossible = 1000000000;
while (impossible - ok > 1)
{
    int candidate = ok + (impossible-ok) / 2;

    if (check(candidate))
        ok = candidate;
    else
        impossible = candidate;
}
return ok;

In either case use basic high school algebra to simplify the inequalities/equation.