Tävlingsprogrammering/Uppgifter/Plattformar

Plattformar

Fil:Kommer-snart.png

En bana håller på att designas till ett nytt tvådimensionellt plattformsspel. En plattform motsvaras av en horisontell linje, och placeringar för alla plattformar har redan bestämts. Till skillnad från de flesta andra plattformsspel så kan dessa plattformar inte hänga fritt i luften, utan måste stadgas upp av pelare. Varje plattform måste ha två pelare, en på vardera sida, som sträcker sig ända ner till marken, eller tills den slår i en plattform under sig (se figur ovan). Pelarna börjar en halv längdenhet in från plattformens ändpunkter. Skriv ett program som beräknar summan av längden på alla pelare. Du kan anta att en plattform har försumbar tjocklek.

Indata

Första raden i filen pelare.dat innehåller heltalet N (1 ≤ N ≤ 100), antalet plattformar. Därefter följer N rader innehållande tre heltal, Y , X1 och X2, som anger en plattforms koordinater. Alla koordinater är mellan 0 och 10000. Dessutom gäller att X1 + 1 < X2, dvs längden på varje plattform kommer vara minst 2. Inga plattformar kommer att överlappa varandra.

Utdata

Skriv ut summan av pelarnas längder.

Exempel

Svar

Lösning

Rent spontant kan man ju känna att man vill rita upp något rutnät och rita ut plattformarna och sedan göra lite enkla kollar, men det går ju inte när koordinaterna ligger mellan 0 och 10,000 (Det går visst... Det behövs visserligen 200 MB men det är inget problem på dagens datorer... Beror kanske på hur man implementerar detta rutnät, men en 10000x10000 boolean-matris går i alla fall inte i Java där standardgränsen för Heapen är 64/128 MB. Fast egentligen behövs 200 miljoner bitar, så om man lagrar det i t.ex. ett std::bitset behövs bara 25 MB). En enkel lösning kan däremot vara att sortera alla plattformar efter höjd och sedan kolla om plattformens respektive pelare skär den plattform som ligger före vår plattform i arrayen (dvs har en lägre höjd). Så vi kollar skärning med alla plattformar med lägre höjd och om vi hittar en skärning, så kan vi vara säkra på att vi har funnit den "närmaste" skärningen; och om det är så att vi når index -1, ja då betyder det att pelaren skär ingen annan plattform, dvs träffar marken.

Hur ska man då kolla om en pelare träffar en annan plattform? Ja det skiljer sig lite mellan den vänstra och högra pelaren, men vi förklarar hur det går till för den vänstra här. Jo den vänstra pelaren för en plattform p1 skär en annan plattform p2 om och endast om p2.x1<=p1.x1 och p2.x2>p1.x1. Observera att p2.x2 måste vara strängt större än p1.x1 eftersom pelaren börjar en halv längdenhet in på plattformen.

Här nedan följer en lösning i Java.

import java.util.*;
import java.io.*;

public class Plattformar
{
	//Orka fånga exceptions. Vi är lata och säkra på vår sak.
	public static void main(String [] klein) throws FileNotFoundException
	{
		//Vi ska läsa av filen pelare.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\pelare.dat"));

		//Antalet plattformar.
		int N = scan.nextInt();

		//Array för att lagra alla plattformar.
		Plattform [] platt = new Plattform [N];

		//Läser in alla plattformar.
		for(int i = 0; i<N; i++)
		{
			platt[i] = new Plattform(scan.nextInt(), scan.nextInt(), scan.nextInt());
		}

		//Sorterar plattformarna i stigande ordning efter höjd.
		Arrays.sort(platt);

		//Summan av pelarnas längd.
		int sum = 0;

		//Går igenom alla plattformar.
		for(int i = 0; i<N; i++)
		{
			//Kollar om den vänstra pelaren skär någon av plattformarna
			//under denna plattform.
			for(int j = i-1; j>=-1; j--)
			{
				//Har vi nått index -1 så skär pelaren marken.
				if(j<0)
				{
					//Ökar summan med pelarens längd (vilket är plattformens höjd)
					//och avbryter.
					sum += platt[i].y;
					break;
				}

				//Kollar om pelaren skär denna plattform.
				if(platt[j].x2>platt[i].x1 && platt[j].x1<=platt[i].x1)
				{
					//Ökar summan med pelarens längd (vilket är differensen mellan de
					//två plattformarnas höjd) och avbryter.
					sum += (platt[i].y-platt[j].y);
					break;
				}
			}

			//Gör samma sak för den högra pelaren.
			//Det enda som är annorlunda är if-satsen för när man kollar skärning.
			for(int j = i-1; j>=-1; j--)
			{
				if(j<0)
				{
					sum += platt[i].y;
					break;
				}

				if(platt[j].x1<platt[i].x2 && platt[j].x2>=platt[i].x2)
				{
					sum += (platt[i].y-platt[j].y);
					break;
				}
			}

			//(Ja vi skulle kunna ha behandlat vänstra och högra pelaren i samma for-loop
			//och på så sätt gjort programmet typ dubbelt så snabbt, men det är bara jobbigt
			//och behövs inte på något sätt.)
		}

		//Skriver ut svaret.
		System.out.println("Total längd: " + sum);
	}

	//Klass som beskriver en plattform. Vi implementerar Comparable, så att vi kan använda
	//Javas Arrays.sort() för att sortera plattformarna.
	private static class Plattform implements Comparable<Plattform>
	{
		//Plattformens koordinater.
		int y, x1, x2;

		//Konstruktor för plattformen.
		public Plattform(int y, int x1, int x2)
		{
			this.y = y;
			this.x1 = x1;
			this.x2 = x2;
		}

		//Jämför denna plattform med en annan efter höjd. Är höjden (y-koordinaten) för denna plattform
		//mindre än höjden för den givna plattformen, så anses denna plattform vara mindre. Tvärtom gäller
		//för det motsatta scenariot och lika om höjderna är lika.
		// (Det är denna metod som Arrays.sort() anropar när den ska sortera plattformarna.)
		public int compareTo(Plattform p)
		{
			if(y<p.y) return -1;
			else if(y>p.y) return 1;
			else return 0;
		}
	}
}

Lösning i Haskell.

-- Plattformar
module Main where
import IO
import Data.Maybe
import Data.List

type Plattform = (Int,(Int,Int))

main = do {
	ih <- openFile "pelare.dat" ReadMode;
		
	content <- hGetContents ih;
	
	rader <- return $ lines content;
	plattformar <- return $ (getPlatt $ tail rader);
	
	putStrLn $ show $ calc $ reverse $ sort plattformar;
	
	hClose(ih)
}

getPlatt :: [String] -> [Plattform]
getPlatt [] = []
getPlatt (h:t) = (a,(b,c)):(getPlatt t)
	where
	(a:b:c:[]) = map read $ words h
	
calc :: [Plattform] -> Int
calc [h] = (fst h)*2
calc ((y,(x1,x2)):t) = (y-h1) + (y-h2) + (calc t)
	where
	p1 = find (\(_,(a,b)) -> (a<=x1 && b>x1)) t
	p2 = find (\(_,(a,b)) -> (a<x2 && b>=x2)) t
	h1 = if (isNothing p1) then 0 else (fst $ fromJust p1)
	h2 = if (isNothing p2) then 0 else (fst $ fromJust p2)