# What approach can be used to solve this? [closed]

The problem can be found here.

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.

This is a SPOJ problem. I am not able find an approach to solve this problem. Also can anyone tell me how to analyze this problem mathematically?

-
There are lots of questions in this problem? It seems like there are question marks everywhere? I've never heard of SPOJ? –  rschwieb Oct 19 '12 at 15:04
@user1724072: I don't feel sorry for downvoting you then. –  Henning Makholm Oct 19 '12 at 15:13
It's not "ignorant" for someone on a math site to never have heard of a computer programming problem website. Rudeness isn't tolerated here. No one is "biased", we just don't appreciate the attitude. And what isn't mathematical about the linear programming answer in the linked question? You're almost definitely not going to get a formula if that's what you're looking for. –  Robert Mastragostino Oct 19 '12 at 15:31
Also, isn't this a problem from a contest of some sort? In that case, asking here feeling like cheating, at least to me... –  fgp Oct 19 '12 at 17:20
@user1724072: If you wish to get answers, being rude and not explaining what SPOJ is probably not the best approach. Did you mean this? –  robjohn Oct 19 '12 at 17:57

## closed as not a real question by Arkamis, rschwieb, DonAntonio, Noah Snyder, Erick WongOct 20 '12 at 5:47

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

It is a valuable hint for all programming contest competitors that they should step into fresh air every now and then. :)

I suggest you compute the maximum survival time $T$ for all $(H,A,x)$ with $H\le 25$ and $A\le 10$ and first effective place $x$ by means of dynamic programming.

For starting positions with $H>25$ and $A>10$ observe that you can make arbitrary sequences of two-unit steps air+water (with $H:-2$, $A:-8$) or air+fire (with $H:-17$, $A:+7$) or fire+water (with $H:-25$, $A:-5$) and that these can be made fit to any required first effective place at the destination status. The positions with $H\le 25$, $A>10$ or $H>25$, $A\le10$ remain problematic: You may be too close to $0$ to choose theorder of a two step combination freely, hence you may need to use a subobtimal effective place at the destination.

As the effect of two time units on $H$ is a decrease of $2$ or more, we see that the survival time is $T(H,A)\le H+1$. Also, we see that two time units decrease $H+A$ by $10$ or more, hence the survival time is $T(H,A)\le \frac{H+A}5+1$. Together with the proposition below we therefore find $$\min\left\{H,\frac{H+A}5-3\right\}\le T(A,H)\le 1+\min\left\{H,\frac{H+A}5\right\}$$ for all $A>0$, $H>0$.

Proposition: Let $T_a(H,A)$ be the maximum survival time, given we start with $H$ health and $A$ armour and the first place is air. Then $$\tag1 T_a(H,T)\ge\min\left\{H,\frac{H+A}5-3\right\}$$ if $A>0$. (Of course, $T_a(H,A)=0$ if $A\le 0$.)

Proof: By induction on $H+A$.

Case (i): $4H\ge 60+A$. We can spend one time unit in air followed by one time unit in fire and find $T_a(H,A)\ge 2+T_a(H-17,A+7)$. By induction hypothesis, the latter is $\ge2+\min\left\{H-17,\frac{H+A-10}5-3\right\}=\min\left\{H-15,\frac{H+A}5-3\right\}$. Because $4H\ge 60+A$, we find $$(H-15)-\left(\frac{H+A}5-3\right)=\frac{4H-A-60}5\ge 0,$$ i.e. $T_a(H,A)\ge \min\left\{H-15,\frac{H+A}5-3\right\}=\frac{H+A}5-3\ge \min\left\{H,\frac{H+A}5-3\right\}$.

Case (ii): $H\le 2$. If $H\le 0$ then $T_a(H,A)\ge 0\ge H$. And if $H>0$ then we can spend one time unit in air followed by one time unit anywhere else, i.e. $T_a(H,A)\ge 2\ge H$. At any rate, $(1)$ follows from $H\ge\min\left\{H,\frac{H+A}5-3\right\}$.

Case (iii): $12\le 4H<60+A$ and $A>8$. We can spend one time unit in air followed by one time unit in water and find $T_a(H,A)\ge 2+T_a(H-2,A-8)$. We can apply the induction hypothesis, obtain $$T_a(H,A)\ge 2+\min\left\{H-2,\frac{H+A-10}5-3\right\}=\min\left\{H,\frac{H+A}5-3\right\}$$ and are done.

Case (iv): $12\le 4H<60+A$ and $A\le8$. Then $H< \frac{68}4$, i.e. $H\le17$. As before, we have $T_a(H,A)\ge 2$. Hence it is sufficient to show $\frac{H+A}5-3\le 2$. But this follows from $H+A\le 17+8=25$.

Thes completes the proof of the proposition.$_\blacksquare$

-