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");
    }

  }

Project Euler 357

Project Euler 357 is easy one. I was trying to solve problem 356 and finally ended up with solving easy problem. Nothing new just sieve of eratosthenes and couple of constraints.
Edit: Finally wrote a Haskell solution. See more discussion on Haskell-Cafe. Compile this code with ghc –make -O2 filename.hs

import Control.Monad.ST 
import Data.Array.ST 
import Data.Array.Unboxed 
import Control.Monad 
import Data.List


prime :: Int -> UArray Int Bool 
prime n = runSTUArray $ do 
    arr <- newArray ( 2 , n ) True :: ST s ( STUArray s Int Bool ) 
    forM_ ( takeWhile ( \x -> x*x <= n ) [ 2 .. n ] ) $ \i -> do 
        ai <- readArray arr i 
        when ( ai  ) $ forM_ [ i^2 , i^2 + i .. n ] $ \j -> do 
            writeArray arr j False 

    return arr 

pList :: UArray Int Bool 
pList = prime $  10 ^ 8 

divPrime :: Int -> Bool 
divPrime n = all ( \d -> if mod n d == 0 then pList ! ( d + div  n  d ) else True )  $  [ 1 .. truncate . sqrt . fromIntegral  $ n ] 



main = putStrLn . show . sum  $ ( [ if and [ pList ! i , divPrime . pred $ i ] then ( fromIntegral . pred $ i ) else 0 | i <- [ 2 .. 10 ^ 8 ] ] :: [ Integer ] ) 

#include<cstdio>
#include<iostream>
#include<vector>
#define Lim 100000001
using namespace std;

bool prime [Lim];
vector<int> v ;

void isPrime ()
     {
		for( int i = 2 ; i * i <= Lim ; i++) 
		 if ( !prime [i]) for ( int j = i * i ; j <= Lim ; j += i ) prime [j] = 1 ; 

		for( int i = 2 ; i <= Lim ; i++) if ( ! prime[i] ) v.push_back( i ) ;
		//cout<<v.size()<<endl;
		//for(int i=0;i<10;i++) cout<<v[i]<<" ";cout<<endl;

     }


int main()
	{
		isPrime();
		int n = v.size();
		long long sum = 0;
		for(int i = 0 ; i < n ; i ++) 
		 {
			int k = v[i]-1;
			bool f = 0;
			for(int i = 1 ; i*i<= k ; i++) 
				if ( k % i == 0 && prime[ i + ( k / i ) ] )  { f=1 ; break ; }
			
			if ( !f ) sum += k;
		 }
		cout<<sum<<endl;
	}

SPOJ 8456. PRIMITIVEROOTS

SPOJ 8456. PRIMITIVEROOTS is related to number theory. Product of primitive roots of p ( prime number ) mod p is equal to 1.The product of all primitive roots of prime p 3 is ( mod p ). History of the theory of numbers By Leonard Eugene Dickson on page 183.This problem is not allowed in Haskell. Accepted C++ code.

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

bool p[10010];

void prime()
	{
		for(int i=2 ; i*i <=10000 ; i++ ) 
		 if(!p[i])
		 for(int j = i*i ; j <=10000 ; j += i ) p[j]=1;
		//for(int i=2; i <= 20 ; i++) if(!p[i]) cout<<i<<" ";cout<<endl;
	}

int main()
	{
		prime();
		int n , t , x=1 ;
		for( scanf("%d",&t) ; t>0 ; t--) 
		{
			scanf("%d",&n);
			if( n == 3 ) printf("%d:2\n", x++);
			else if ( !p[n] ) printf("%d:1\n",x++);
			else printf("%d:NOTPRIME\n",x++);
			/*if( t != 1 ) printf("\n");*/
		}

	}

SPOJ 9126. Time to live

SPOJ 9126. Time to live is almost similar to 1437. Longest path in a tree. Find the diameter of tree and maximal needed TTL for network will be radius of tree. Accepted c++ code.

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

vector<int> V[100100];
int vis[100100],dist[100100],k;
void dfs(int v,int n)
  {

            vis[v]=1;
            dist[v]=n;
            for(int u=0;u<V[v].size();u++)
             if(!vis[V[v][u]])
               dfs(V[v][u],n+1);

 }

int main()
  {
          int n,t1,t2 , t;
          for(scanf("%d",&t) ;t > 0 ; t-- )
            {
		 scanf("%d",&n);
                 for(int i=0;i<n;i++)
                  V[i].clear(),vis[i]=0;

                 for(int i=0;i<n-1;i++)
                  {
                         scanf("%d%d",&t1,&t2);
                         V[t1].push_back(t2);
                         V[t2].push_back(t1);
                  }
		 
		 //if(n==2) { cout<<"1\n";continue;}

                 dist[0]=0;
                 dfs(0,0);
                 /* for(int i=0;i<n;i++)
                  cout<<dist[i]<<" ";
                  cout<<endl;*/

                 int node=0;
                 for(int i=0;i<n;i++)
                  if(dist[i]>dist[node])
                    node=i;

                 memset(vis,0,sizeof(vis));
                // cout<<"node"<<node<<endl;

                 dfs(node,0);

                 /*for(int i=0;i<n;i++)
                  cout<<dist[i]<<" ";
                  cout<<endl;*/

                 sort(dist,dist+n);
		 int d = dist[n-1];
		 if( d & 1 ) cout<< ( d>>1 ) + 1 <<endl;
		 else cout<< ( d>>1 ) <<endl;
                 //cout<<dist[n-1]<<endl;

            }
 }

SPOJ 9122. Diary

SPOJ 9122. Diary is just simulation problem. Only thing we need to consider is ” If the decryption is not possible because there are multiple distances conforming to the rules above, print NOT POSSIBLE instead”. Count all the occurrence of alphabets and find out which one is maximum. If there are more than one alphabets , clearly its impossible to decrypt otherwise assign it ‘E’ and calculate distance and decrypt the string. Accepted c++ code.

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int cnt[30];

int main()
	{
		int t ;
		string s , final ;
		for( scanf("%d\n",&t) ; t > 0 ; t-- )
		{
			memset( cnt , 0 , sizeof cnt );
			getline( cin , s ); 
			int len = s.length();
			for(int i = 0; i < len ; i++) if ( s[i] >= ' ' ) cnt[s[i]-'A']++ ;
		
			//cout<<s<<endl;
			//for(int i=0;i<26;i++) cout<<cnt[i]<<" ";cout<<endl;	
			//find out most occuring word and this is E
			//what if i have more than two words have same occurance 
			
			int mx = -1 , ind = -1  ;
			for(int i = 0 ; i < 26 ; i++ ) if ( cnt[i] > mx ) mx = cnt[i] , ind = i ; 
			
			int c = 0 ; 
			for(int i = 0 ; i < 26 ; i++) if (cnt[i]==mx ) c++;
			if ( c>1 ) { cout<<"NOT POSSIBLE\n" ; continue ;} 
			
			int dist =  ( ind - 4 + 26 ) % 26 ;			
			final = "";
			for(int i = 0 ; i < len ; i++) 
				if (s[i] !=' ') final += ( char ) (  'A' + ( ( s[i] - 'A' - dist + 26 ) % 26 ) ) ; 
				else final += ' ' ;
			
			cout<<dist<<" "<<final<<endl;

		}
	}