## SPOJ DIE HARD

DIEHARD I tried to find out greedy solution but could not come up so trying every possibility and memoization of each state. See more about dynamic programming. The basic idea is that you have to always go to air to increase your chance for survival because its increase the health and armor. We start in air with health increased by 3 and armor increased by 2. After that we have to find out which one, going to water or fire gives maximum survival. A simple Haskell recursive solution which works for small values. We start from funsolve_Air after that we chose the maxiumum value of two functions respectively for water and fire.

funsolve_WF :: Int -> Int -> Int -> Int funsolve_WF h a cnt | h <= 0 || a <= 0 = cnt | otherwise = funsolve_Air h a ( cnt + 1 ) funsolve_Air :: Int -> Int -> Int -> Int funsolve_Air h a cnt = max ( funsolve_WF ( h + 3 - 5 ) ( a + 2 - 10 ) cnt' ) ( funsolve_WF ( h + 3 - 20 ) ( a + 2 + 5 ) cnt' ) where cnt' = cnt + 1 *Main> funsolve_Air 20 8 0 5 *Main> funsolve_Air 2 10 0 1 *Main> funsolve_Air 4 4 0 1

Accepted source code in C++.

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int memo[1100][1100] ; int recurse( int h , int a , int cnt , bool flag ) { if ( h <= 0 || a <= 0 ) return cnt ; if ( memo[h][a] ) return memo[h][a] ; if ( flag ) memo[h][a] = max ( memo[h][a] , recurse ( h + 3 , a + 2 , cnt + 1 , !flag ) ) ; else memo[h][a] = max ( memo[h][a] , max ( recurse ( h - 5 , a - 10 , cnt + 1 , !flag ) , recurse ( h - 20 , a + 5 , cnt + 1 , !flag ) ) ) ; return memo[h][a]; } int main() { int n , a , b ; scanf( "%d", &n ); for(int i = 0 ; i < n ; i++) { memset ( memo , 0 , sizeof memo ) ; scanf("%d%d", &a , &b ); printf("%d\n" , recurse( a , b , -1 , 1 )); if( i != ( n - 1 ) ) printf("\n"); } }

Advertisements

um can you tell me whats wrong with my code ? :

#include

int main(){

int t,n=0,H,A;

scanf(“%d”,&t);

for(int i=0;i0&&A>0){

H=H+3;

A=A+2;

n+=1;

if(HA){

H=H-20 ;

A=A+5;

n+=1;

}

}

printf(“%d\n”,n-1);

}

return 0;

}

Comment by someone | April 19, 2013 |

@Someone

I am not sure about working greedy solution. Try to generate all the possibilities and check for solution.

Comment by tiwari_mukesh | April 19, 2013 |

Hi. You do not have to use “max ( memo[h][a],”. I don’t know why, but your memo matrix is too short, cause h and a can be much more than 1100, just use “printf” on the function and you will see. if(h>1100 || a>1100)printf(“%d %d\n”,h,a); Altought it can be more than 1100 i do not know how to estimate a good value, do you have any idea? PS: SPOJ accepted 1100 and did not inform segmentation fault.

Comment by Roni | February 8, 2015 |