Friday, September 16, 2011

SRM325

Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3

Tutorials:


Division One - Level Three:

Solution

Source Code:


Division One - Level Two:

Solution

Source Code:


Division One - Level One:

Solution

Source Code:


Sivision Two - Level Three:

Solution

Source Code:


Division Two - Level Two:

Solution

Dynamic Programming.
RGB stores the cost value for each color of every element, while dp[i][j] stores the cost by using first i elements, with using jth (which is smaller than 3) color for ith (which is smaller than N) element.

Source Code:

//Fri Sep 16 16:33:59 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class RGBStreet
{
        public int[][] RGB;
       
        public int[][] dp;
       
        public int estimateCost(String[] houses)
        {
                int N = houses.length;
                RGB = new int[N][3];
                dp = new int[N][3];   //R:0; G:1; B:2;
               
                for(int i=0; i<N; i++){
                        String[] temp = houses[i].split(" ");
                        for(int j=0; j<3; j++)
                                RGB[i][j] = Integer.parseInt(temp[j]);
                       
                        dp[i][0] = Integer.MAX_VALUE;
                        dp[i][1] = Integer.MAX_VALUE;
                        dp[i][2] = Integer.MAX_VALUE;
                }
               
                dp[0][0] = RGB[0][0]; dp[0][1] = RGB[0][1]; dp[0][2] = RGB[0][2];
               
                for(int i=1; i<N; i++){
                        for(int j=0; j<3; j++){
                                for(int k=0; k<3; k++){
                                        if(j!=k){                                         
                                                dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + RGB[i][j]);
                                        }
                                }
                        }
                }
                return Math.min(dp[N-1][0], Math.min(dp[N-1][1], dp[N-1][2]));
        }
       
       
}
//Powered by [KawigiEdit] 2.0!


Division Two - Level One:

Solution

Straight-Forward.

Source Code:

//Fri Sep 16 16:43:08 CDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class SalaryCalculator
{
        public double calcHours(int P1, int P2, int salary)
        {
                if(P1 * 200 >= salary) return 1.0 * salary / P1;
                return 200.0 + (1.0 * salary - P1 * 200) / P2;
        }
      
      
}
//Powered by [KawigiEdit] 2.0!

No comments :