My Weblog

Blog about programming and math

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

December 11, 2012 - Posted by | Programming | , , , ,

3 Comments »

  1. 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 | Reply

    • @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 | Reply

  2. 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 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: