Tävlingsprogrammering/Uppgifter/Trubaduren

Trubaduren

I en by på landet sjunger byborna varje kväll visor vid brasan. En viktig bybo är trubaduren. De kvällar trubaduren är närvarande sjunger han en ny visa som ingen annan bybo hört förut. Inga andra visor sjungs dessa kvällar, och alla bybor som då är närvarande lär sig trubadurens nya visa. De kvällar trubaduren inte är närvarande så sjunger byborna utan honom, och utbyter alla visor de kan med varandra.

Givet vilka bybor som är närvarade vid ett visst antal kvällar, skriv ut en lista på de bybor som efter dessa kvällar känner till samtliga visor som sjungits under den perioden.

Indata

Första raden i filen trubadur.dat innehåller heltalet N (1 ≤ N ≤ 100), antalet personer i byn, inklusive trubaduren. Byborna numreras från 1 till N, där bybo nummer 1 är trubaduren. Andra raden innehåller heltalet M (1 ≤ M ≤ 50), antalet kvällar det sjungs visor i byn. Därefter följer M rader som beskriver vilka bybor som närvarat de olika kvällarna. Varje sådan rad börjar med ett tal K som anger antalet bybor som var närvarande den kvällen. Därefter följer K tal som anger vilka dessa bybor var. Ingen bybo kommer nämnas mer än en gång per rad, och trubaduren kommer att närvara åtminstone en kväll.

Utdata

Skriv ut de bybor, inklusive trubaduren, som kan alla olika visor som sjungits efter de M kvällarna. Skriv ut byborna sorterade i nummerordning och separerade med blanksteg.

Exempel

Svar

1 2 4

Förklaring: Trubaduren är närvarande två kvällar, så det finns totalt två olika visor. Bybo 2 får lära sig den andra visan den tredje kvällen då trubaduren framför den och får lära sig den första visan via bybo 3 den andra kvällen. Bybo 4 får lära sig den ena visan kväll 2 och den andra kväll 4. Notera att bybo 5 aldrig får lära sig visan som sjöngs den första kvällen eftersom den inte sjöngs den tredje kvällen då trubaduren var närvarande.

Extra exempel

Svar

1 3 5

Lösning

Det finns egentligen inga större svårigheter i denna uppgift, det är bara att simulera ett förlopp ordentligt. Vad som däremot är lätt hänt på sådana här uppgifter är att man börjar fundera över det sätt som kräver minst arbete av en själv (för vem bryr sig om datorn i sådana här lätta uppgifter).

Här nedan följer en lösning i Java. Observera raden @SuppressWarnings("unchecked"), vilken gör att man slipper få ett varningsmeddelande från kompilatorn för den tveksamma raden HashSet <Integer> [] citizen = new HashSet [N+1];. Att blanda typbestämd kollektion med kollektion av rå typ på detta sätt är ett fulhax för att kringgå att man egentligen inte får skapa arrayer av kollektioner med typbestämt innehåll i Java. Dock uppnår vi den funktionalitet vi vill ha med detta sätt och varningen som kompilatorn ger har vi som sagt tagit bort.

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

public class Trubaduren
{
	//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 trubadur.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\trubadur.dat"));

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

		//Array med hashtabeller för att spara alla låtar en viss bybo kan.
		@SuppressWarnings("unchecked")
		HashSet <Integer> [] citizen = new HashSet [N+1];

		//Skapar alla bybor.
		for(int i = 1; i<=N; i++) citizen[i] = new HashSet <Integer> ();

		//Antalet nätter.
		int M = scan.nextInt();

		//Hur många olika sånger det finns.
		int songs = 0;

		//Går igenom varje natt.
		for(int i = 0; i<M; i++)
		{
			//Antalet personer vid elden.
			int K = scan.nextInt();

			//Byborna vid elden.
			int [] eld = new int [K];

			//Om trubaduren sitter vid brasan.
			boolean trubadur = false;

			//Läser in personera kring elden.
			for(int j = 0; j<K; j++)
			{
				//Kollar på köpet om trubaduren är en av dem.
				if((eld[j] = scan.nextInt()) == 1) trubadur = true;
			}

			//Om trubaduren sitter kring brasan...
			if(trubadur)
			{
				//...så lär han alla bybor kring brasan den nya låten.
				for(int j = 0; j<K; j++)
				{
					citizen[eld[j]].add(songs);
				}

				//En ny låt har skapats.
				songs++;
			}
			else
			{
				//Annars lär varje bybo vid brasan alla bybor vid brasan alla
				//låtar han kan. (Går igenom varje bybo vid elden.)
				for(int j = 0; j<K; j++)
				{
					//Går igenom alla låtar denna bybo kan.
					for(int song : citizen[eld[j]])
					{
						//Lär ut denna låt till varje bybo kring elden.
						for(int bybo : eld)
						{
							citizen[bybo].add(song);
						}
					}
				}
			}
		}

		//Skriver ut svaret.
		System.out.print("Bybor som kan alla låtar: ");

		//Skriver ut alla bybor som kan alla låtar.
		for(int i = 1; i<=N; i++)
		{
			if(citizen[i].size()==songs) System.out.print(i + " ");
		}

		System.out.println();
	}
}

Kan man Haskell, kan man också roa sig med att försöka komma på en så fyndig lösning som möjligt (då problemet är så tråkigt).

-- Trubaduren
module Main where
import IO
import Data.List (take, words, lines, elem)
import Data.Set (Set, insert, empty, unions)

type Bybo = (Int, Set Int)
bybor = (1, empty):(map (\(a,b) -> (a+1,b) ) bybor)

main = do {
	ih <- openFile "trubadur.dat" ReadMode;
		
	content <- hGetContents ih;
	rader <- return $ lines content;
	
	putStrLn $ trubadur 0 (map ((map read).(tail.words)) (tail $ tail rader)) (take (read $ head rader) bybor);
	
	hClose(ih)
}

fix = tail.(map (\x -> if (x==',' || x=='[' || x==']') then ' ' else x))

trubadur :: Int -> [[Int]] -> [Bybo] -> String
trubadur _ [] bybor = fix.show $ map (\(c,_) -> c) [(a,b) | (a,b) <- bybor, b == (snd $ head bybor)]
trubadur n (h:t) bybor = if (elem 1 h) then (trubadur (n+1) t (map learn bybor)) else (trubadur n t sing)
	where
	learn (a,b) = if (elem a h) then (a, insert n b) else (a, b)
	sing = map (teach (unions [b | (a,b) <- bybor, elem a h])) bybor
	teach c (a,b) = if (elem a h) then (a,c) else (a,b)