Tiling a grid with dominoes

From Progteam

Revision as of 06:02, 22 May 2008 by Kerry (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by mlc413.
Checkmark.jpg This problem has been solved by kerry.
Checkmark.jpg This problem has been solved by hjfreyer.


Tiling a Grid With Dominoes
Problem Number 0000
Sorter: Mlc413
Source: GNYR ICPC 2007
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=0000



This is problem H from the GNYR programming contest at Kean University. This problem is not yet on the Peking site See problem specs here [[1]]

The trick to this problem is realizing that tiling an area of length 4xN can be reduced to a 4xM area, with M<N. The way you do this is by making a function that returns the number of ways you can tile an area based on two factors:

  1. The length of the area you're tiling
  2. The relief of the area you're tiling

By relief, I mean what is "sticking out" at the end of the length. Draw out the n=3 case. You'll notice it can be reduced to the n=2 case in multiple ways, depending on what "relief" you choose for n=2. It's mostly a visual thing, so draw it out, think about it, and check out the code.


Kerry and Melanie's Solution


import java.util.*;

public class Main{
	
	public static Scanner in;
	
	public static void main(String[] args){
		in=new Scanner(System.in);
		
		doStuff();
	}
	
	public static void doStuff(){
		int N=in.nextInt();
		
		for(int i=0;i<N;i++){
			System.out.print((i+1) + " ");
			solve(in.nextInt());
		}
	}
	
	public static void solve(int W){
		//System.out.println(W);
		System.out.println(value(W));
	}
	
	public static int value (int w){
		int num = 0;
		if (w == 1) num = 1;
		else if (w == 2) num = 5;
		else if (w == 3) num = 11;
		else{
    		num += value(w-1) + value(w-2);//these are the clean cut cases DONE
    		if(w %2 == 0)
				{
					num += 2*eVal(w-2) + eVal2(w-2); 
				}
				else{
					num += 2*oVal(w-2) + oVal2(w-2); 
				}
		}
				return num;
    
		}
		
		public static int eVal(int n)
	{
			int ans = 1;
			for(int j = n; j > 0; j--)
			{
				ans += value(j);
			}
			
			return ans;
		}
	
		public static int eVal2(int n)
		{
			int ans = 1;
			for(int j = n; j > 0; j-=2)
			{
				ans += value(j);
			}
			
			return ans;
			
		}
	
	public static int oVal(int n)
	{
		int ans = 1;
		for(int j = n; j > 0; j--)
		{
			ans += value(j);
		}
		
		return ans;
		}
	
		public static int oVal2(int n)
		{
			int ans = 0;
			for(int j = n; j > 0; j-=2)
			{
				ans += value(j);
			}
			
			return ans;
			
		}
	
	
}


Hunter's Solution

This code is a lot longer than it has to be. I chose to enumerate every possible case for clarity (any my own sanity)'s sake, rather than making it really tight. The majority of the code is just one big if statement.

import java.util.*;

public class Main{
    public static Scanner in;
    public static void main(String[] args){
	in = new Scanner(System.in);
	doStuff();
	
	//	System.out.println(numWays(7));
    }
 
    public static void doStuff(){
	int N = in.nextInt();
	for(int i = 1; i <=N; i++){
	    int len=in.nextInt();
	    num_matrix=new int[len+1][6];
	    
	    for(int k=0;k<len+1;k++){
		for(int j=0;j<6;j++)
		    num_matrix[k][j]=-1;
	    }

	    System.out.printf("%d %d\n",i,numWays(len));
	
	}
    }

    public static int numWays(int len){
	return numWays(len,0);
    }

    
    public static int[][] num_matrix=null;
    public static int numWays(int len,int relief){
	if(num_matrix[len][relief]==-1)
	    num_matrix[len][relief]=numWaysCalc(len,relief);
	return num_matrix[len][relief];
   
    }
    public static int numWaysCalc(int len,int relief){
		
	if(len==1){
	    switch(relief){
	    case 0:
	    case 1:
	    case 2:
	    case 4:
	    case 5:
		return 1;
	    case 3:
		return 0;
	    }
	}

	int total=0;
	switch(relief){

	    // We have case 0
	case 0:
	    // Leaving case 0
	    total+=numWays(len-1,0);
	    
	    // Leaving case 1
	    total+= numWays(len-1,1);
	    // Leaving case 2
	    total+= numWays(len-1,2);
	    // Leaving case 3
	    total+= numWays(len-1,3);
	    // Leaving case 4
	    total+= numWays(len-1,4);
	    // Leaving case 5
	    total+=numWays(len-1,5);
	    return total;
	
	    // We have case 1
	case 1:
	    // Leaving case 0
	    total+=numWays(len-1,0);
	    
	    // Leaving case 1
	    total+= 0;
	    // Leaving case 2
	    total+= 0;
	    // Leaving case 3
	    total+= numWays(len-1,3);
	    // Leaving case 4
	    total+= 0;
	    // Leaving case 5
	    total+=0;
	    return total;
	
	    // We have case 2
	case 2:
	    // Leaving case 0
	    total+=numWays(len-1,0);
	    
	    // Leaving case 1
	    total+=0;
	    // Leaving case 2
	    total+= numWays(len-1,2);
	    // Leaving case 3
	    total+= 0;
	    // Leaving case 4
	    total+= 0;
	    // Leaving case 5
	    total+=0;
	    return total;
	
	    // We have case 3
	case 3:
	    // Leaving case 0
	    total+=0;
	    
	    // Leaving case 1
	    total+= 0;
	    // Leaving case 2
	    total+= 0;
	    // Leaving case 3
	    total+= 0;
	    // Leaving case 4
	    total+= numWays(len-1,4);
	    // Leaving case 5
	    total+=0;
	    return total;
	
	    // We have case 4
	case 4:
	    // Leaving case 0
	    total+=numWays(len-1,0);
	    
	    // Leaving case 1
	    total+= 0;
	    // Leaving case 2
	    total+= 0;
	    // Leaving case 3
	    total+= numWays(len-1,3);
	    // Leaving case 4
	    total+= 0;
	    // Leaving case 5
	    total+=0;
	    return total;
	
	    // We have case 0
	case 5:
	    // Leaving case 0
	    total+=numWays(len-1,0);
	    
	    // Leaving case 1
	    total+= 0;
	    // Leaving case 2
	    total+= 0;
	    // Leaving case 3
	    total+= 0;
	    // Leaving case 4
	    total+= 0;
	    // Leaving case 5
	    total+=0;
	    return total;
	    
	    
	}
	
	throw new AssertionError();

    }
}
Personal tools