Tävlingsprogrammering/Uppgifter/Strumpmatchning

Mall:Proguppgift

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