Tävlingsprogrammering/Uppgifter/Vindskydd

Vindskydd

Några snickare ska bygga ett hus. Snickarna bygger först en grund med längden L och bredden B och bygger sedan på inifrån, men för att hålla sig krya medan de arbetar så ska de sätta upp vindskydd. Vindskydden ska stå utmed grundens fyra kanter (d.v.s. där husets väggar sedan kommer) och de ska också ha en viss höjd H.

De fyra vindskyddsväggarna skapas genom att skära upp ett platt rektangulärt plaststycke med dimensionerna M × N i fyra mindre bitar. Vi tänker oss att orginalplasten ligger på en grid med ett hörn i origo. Du skär alltid en gång parallellt med x-axeln och en gång parallellt med y-axeln, och du kan endast skära vid heltalskoordinater. Din uppgift är att bestämma på hur många olika godkända sätt man kan skära upp plasten. För att en skärning ska vara godkänd måste bitarna kunna täcka varsin vägg. Det gör ingenting om bitarna är för stora, men de får inte vara för små.

FIGUR 1. Figuren visar ett av sätten att skära plasten i körningsexempel 1. Observera att alla andra sätt att skära plasten (t.ex. vid x=1 och y=1) skapar en likadan uppsättning bitar, men de ska ändå räknas som olika skärningar.

Programmet ska fråga efter fem heltal: husets längd, L, och bredd, B, (där L ≥ B), vindskyddens höjd H, samt plaststyckets dimensioner M och N. Samtliga indatavärden är mellan 1 och 20, inklusive. Programmet ska skriva ut antalet olika sätt att skära plasten på, med avseende på x- och y-koordinaterna.

Körningsexempel 1

L ? 2
B ? 1
H ? 1
M ? 3
N ? 3

Antal sätt: 4

Körningsexempel 2

L ? 4
B ? 2
H ? 2
M ? 10
N ? 5

Antal sätt: 14

Lösning

[Insert: Elegantare lösning.]

Uppgiften är egentligen inte särskilt svårt. Skär plasten på alla möjliga sätt och kolla om det går att täcka de fyra väggarna med bitarna. Är man lat och inte orkar tänka på hur man lättast utför den kollen, så skriver man en rekursiv funktion som testar alla sätt att täcka väggarna på tills ett godkänt sätt hittas.

Lösning i Haskell.

-- Vindskydd
module Main where
import Data.List

getInt :: IO Int
getInt = getLine >>= return.read

main =	putStr "L ? " >> getInt >>= \l ->
	putStr "B ? " >> getInt >>= \b ->
	putStr "H ? " >> getInt >>= \h ->
	putStr "M ? " >> getInt >>= \m ->
	putStr "N ? " >> getInt >>= \n ->
	let walls = [(l,h),(l,h),(b,h),(b,h)] in
	putStrLn.("\nAntal satt: " ++).show $
	sum [1 | x <- [0..m], y <- [0..n], isPossible (permutations [(x,y),(m-x,y),(x,n-y),(m-x,n-y)]) walls]
	
isPossible [] _ = False
isPossible x w = possible (head x) w || isPossible (tail x) w
	where
	possible [] [] = True
	possible ((a,b):t) ((w0,w1):s) = ((a>=w0 && b>=w1) || (b>=w0 && a>=w1)) && possible t s

Motsvarande lösning i Java.

import java.util.*;

public class Vindskydd
{
	//[i] = Anger om vi har använt plastbit nr i.
	static boolean [] used = new boolean [4];

	//[i][0] = Vägg i:s bredd. [i][1] = Vägg i:s höjd.
	static int [][] wall = new int [4][2];

	public static boolean possible(int n, int [][] w)
	{
		//Vi har lyckats täcka in alla väggar.
		if(n==4) return true;

		//Testar att täcka vägg n med alla de möjliga bitarna.
		for(int i = 0; i<4; i++)
		{
			//Vi kan inte använda en redan använd bit.
			if(used[i]) continue;

			//En bit (a,b) kan täcka en vägg (c,d) om (a>=c och b>=d) eller (b>=c och a>=d).
			if((w[i][0]>=wall[n][0] && w[i][1]>=wall[n][1]) || (w[i][1]>=wall[n][0] && w[i][0]>=wall[n][1]))
			{
				used[i] = true; //Markerar biten som använd.

				//Om vi kan från detta läge nå ett läge där alla väggar har täckts,
				//så har vi lyckats.
				if(possible(n+1, w)) return true;

				used[i] = false; //Avmarkerar biten.
			}
		}

		return false;
	}

	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("L ? ");
		int L = scan.nextInt();

		System.out.print("B ? ");
		int B = scan.nextInt();

		System.out.print("H ? ");
		int H = scan.nextInt();

		System.out.print("M ? ");
		int M = scan.nextInt();

		System.out.print("N ? ");
		int N = scan.nextInt();

		//Antal sätt.
		int svar = 0;

		//Väggarna som ska täckas.
		wall[0][0] = wall[1][0] = L;
		wall[0][1] = wall[1][1] = wall[2][1] = wall[3][1] = H;
		wall[2][0] = wall[3][0] = B;

		//Testar att skära på alla möjliga sätt.
		for(int x = 0; x<=M; x++)
		for(int y = 0; y<=N; y++)
		{
			//Dessa bitar har vi att jobba med.
			int [][] w = {{x,y}, {M-x,y}, {x,N-y}, {M-x,N-y}};

			//Kan vi täcka alla väggar med dessa bitar?
			if(possible(0,w)) svar++;

			Arrays.fill(used, false); //Avmarkerar använda bitar.
		}

		//Skriver ut svaret.
		System.out.println("\nAntal sätt: " + svar);
	}
}