Tävlingsprogrammering/Uppgifter/Strumpmatchning

Strumpmatchning

Hos familjen Svensson är det barnen som fixar tvätten idag. Lilla David har fått den allra svåraste uppgiften: att para ihop strumporna. Skriv ett program som hjälper David att bestämma vilken strumpa som ska paras ihop med vilken.

Det finns totalt N strumpor (2 ≤ N ≤ 1000), och varje strumpa har en färg F_i. Två strumpor i och j kan paras ihop om skillnaden i färg strikt understiger ett givet tal D, d.v.s. $|$F_i - F_j$|$ < D.

Antalet strumpor kan vara udda, och strumporna kan ha vilken färg som helst (strumpor följer som bekant sina egna naturlagar och kan t.ex. försvinna spårlöst). Vidare så passar alla strumpor båda fötterna. Du ska räkna ut det maximala antalet strumppar som kan bildas, med ovan givna data.

Första raden i filen strumpor.dat innehåller två heltal, N och D, åtskilda med blanksteg. Sedan följer en rad med N heltal: F₁, F₂ o.s.v. till F_n. Talen F_i och D ligger mellan 1 och 1'000'000'000 (inklusive). Programmet ska skriva ut ett heltal: maximalt antal par som kan bildas.

Exempel 1

5 3
3 8 1 5 9

Svar

2

Förklaring: Här paras 3 ihop med 5 och 8 med 9.

Exempel 2

4 1
100 101 102 103

Svar

0

Förklaring: Perfektionisten tillåter inga färgskillnader men får då gå barfota.

Exempel 3

10 20
81 92 42 45 62 5 4 85 73 22

Svar

4

Lösning

Det gäller att inse att man kan gå igenom strumporna i färg-ordning (lägst först) och försöka para ihop en strumpa med närmast efterföljande. Och nej det kan inte vara smart att strunta i att skapa ett par. D.v.s. om vi har tre strumpor (1,2,3) är det meningslöst att strunta i att para ihop 1-2 bara för att kunna para ihop 2-3, i vilket fall blir ju en strumpa över.

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

public class Strumpmatchning
{
	//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 strumpor.dat.
		Scanner scan = new Scanner(new File("strumpor.dat"));

		final int N = scan.nextInt();
		final int D = scan.nextInt();

		//Läser in strumporna.
		int [] strumpa = new int [N];
		for(int i = 0; i<N; i++) strumpa[i] = scan.nextInt();

		//Sortera strumporna.
		Arrays.sort(strumpa);

		int max = 0;

		for(int i = 0; i<N-1; i++)
		if(Math.abs(strumpa[i]-strumpa[i+1])<D)
		{
			max++;
			i++; //Hoppa fram ett steg extra, så att inte en strumpa hamnar i två par.
		}

		//Skriver ut svaret.
		System.out.println(max);
	}
}

Cool lösning i Haskell.

-- Strumpor
module Main where
import IO
import Data.List

main = openFile "strumpor.dat" ReadMode >>= \ih ->
	fmap ((map read).words) (hGetContents ih) >>= \(_:d:t) ->
	putStrLn (show $ count d $ sort t) >>
	hClose ih

count :: Int -> [Int] -> Int
count d (a:b:t) = if abs (a-b) < d then count d t + 1 else count d (b:t)
count _ _ = 0