Tävlingsprogrammering/Uppgifter/Hoppleken: Skillnad mellan sidversioner

Nuvarande version från 16 april 2020 kl. 16.31

Lösning

Den här uppgiften föll utanför mönstret för PO-uppgifter genom att den kräver visst matematikbevis-tänkande men sedan är mycket lättare än den verkar. Dessutom innehåller den mer information än man egentligen behöver (det spelar ingen roll att de hoppar slumpmässigt). Vi har fått många kommentarer om att det därför var en dålig programmeringsuppgift. Men faktum är att denna typ av uppgift är ganska vanlig på de internationella tävlingarna, och vi ville ta med en sådan i kvalet för att visa att det ibland är bättre att tänka mer och koda mindre.

Nyckeln är att inse att, givet en utgångsposition, slutpositionen är entydigt bestämd, alltså oberoende av hur barnen hoppar (inte undra på att Britta i Norrgården tyckte det var fånigt). För att inse detta kan det underlätta att färga rutorna, varannan vit och varannan svart. Leken slutar alltså när det är en vit och en svart ruta kvar. I varje hoppomgång byter varje barn från en svart till en vit ruta eller tvärtom, så man kan dela upp barnen i två grupper, med B_v respektive B_s barn, beroende på deras färg på utgångsrutan. Barn från olika grupper kommer aldrig att hamna på samma ruta och grupperna kan därför hanteras separat. Vidare vet vi att barnen försvinner i par (när de krockar) och dessutom att det endast kan finnas 0 eller 1 barn i varje grupp kvar på slutet, eftersom det bara finns en ruta av varje färg. Om antalet barn i en grupp är udda måste alltså ett av dem bli kvar på slutet medan om antalet är jämnt måste alla försvinna. Sålunda finns det totalt (B_v mod 2) + (B_s mod 2) vinnare i leken.

Här kan man fortsätta och göra en helt matematisk lösning, men vi har faktiskt råd att generera alla utgångsställningar (max 184756 stycken) och helt enkelt räkna ut B_v och B_s för varje ställning. Genereringen av ställningar kan t.ex. göras med en rekursiv funktion som, för ett givet antal utplacerade barn, testar att sätta nästa barn på någon av de kvarvarande rutorna och sedan rekurserar (se lösningen nedan).

#include <stdio.h>

int N,B,nconf,sum;

void MLX(int nr, int now, int odd, int even) {
  int p;
  if(nr==B) {
    nconf++;
    sum+=(odd%2)+(even%2);
  }
  else 
   for(p=now;p+(B-nr)<=N;p++) 
      MLX(nr+1,p+1,odd+(p%2),even+((p+1)%2));
}
    
int main() {
  printf("Antal rutor ? ");
  scanf("%d", &N);
  printf("Antal barn ? ");
  scanf("%d", &B);
  nconf=sum=0;
  MLX(0,0,0,0);
  printf("Svar: %f\n", (double)sum/(double)nconf);
  return 0;
}

Är man snäppet coolare än alla andra på skolan, så kör man Haskell.

-- Hoppleken
module Main where
import IO

main = do {
	putStr "Antalet rutor ? ";
	rutor <- getLine;
	n <- return $ read rutor;
	
	putStr "Antalet barn ? ";
	barn <- getLine;
	b <- return $ read barn;
	
	putStrLn $ "Svar: " ++ (show $ (fromIntegral $ jump n b 0 0 0) / (fromIntegral $ product [n-b+1..n] `div` product [1..b]))
}

jump n b od ev i = if b==0 then mod od 2 + mod ev 2 else sum $ map (\x -> jump n (b-1) (od + mod x 2) (ev + mod (x+1) 2) (x+1)) [i..n-b]

Matematisk Lösning

Vill man lösa uppgiften matematiskt kan man göra såhär. Dela upp rutorna i vita och svarta. Låt de vita rutorna vara de med jämnt index (0,2,4..) och de svarta rutorna de med udda index (1,3,5..). Antalet barn kvar i slutändan är som tidigare nämnt "antalet barn i de vita rutorna" mod 2 + "antalet barn i de svarta rutorna" mod 2.

Givet att vi har B barn, V vita rutor och S svarta rutor. Då är frågan, på hur många sätt kan jag placera 0 barn i de vita rutorna och B barn i de svarta rutorna, samt 1 barn i de vita rutorna och B-1 barn i de svarta rutorna, etc. Svaret fås genom Binomialkoefficienten vilken kan besvara frågor som "på hur många sätt kan jag välja k element bland n".

Antalet sätt jag kan placera 3 barn i de vita rutorna (förutsatt att V≥3) och B-3 barn i de svarta rutorna (förutsatt att S≥B-3) på blir således:

$(\binom{V}{3}) \cdot (\binom{S}{B - 3})$

Och antalet barn som kommer att bli kvar med denna uppsättning är 3 mod 2 + (B-3) mod 2. Således blir antalet barn som kommer att bli kvar totalt givet uppställningen 3 barn i vita rutor och B-3 barn i svarta rutor:

$(\binom{V}{3}) \cdot (\binom{S}{B - 3}) \cdot (3 mod 2 + (B - 3) mod 2)$

Detta kan givetvis göras analogt för varje antal K barn i vita där K≤V och B-K≤S. Vi får således följande formel för det totala antalet barn som kommer att bli kvar:

$\sum_{k = B - m i n (S, B)}^{m i n (V, B)} (\binom{V}{k}) \cdot (\binom{S}{B - k}) \cdot (k mod 2 + (B - k) mod 2)$

B - min(S,B) är det minsta antalet barn vi kan placera i de vita rutorna, medan min(V,B) är det största antalet barn vi kan placera i de vita rutorna.

Svaret blir då ovanstående summa delat på antalet sätt man kan placera B barn på N rutor, d.v.s:

$\frac{\sum_{k = B - m i n (S, B)}^{m i n (V, B)} (\binom{V}{k}) \cdot (\binom{S}{B - k}) \cdot (k mod 2 + (B - k) mod 2)}{(\binom{N}{B})}$

(Någon kan nu anmärka på att vi i vårt resonemang inte tagit hänsyn till att barnen faktiskt är unika och har olika namn. Vårt resonemang tar inte hänsyn till om det är Bosse eller Olle som står på ruta 1, utan bara att det är ett barn som faktiskt står där. Men faktum är att det inte spelar någon roll, eftersom det kommer att påverka antalet ställningar man kan börja på och antalet barn som blir kvar med samma faktor (vilken är $B!$ ), och kvoten blir således densamma.)

En lösning i Haskell kan se ut såhär.

-- Hoppleken
module Main where
import Control.Monad

main = putStr "Antalet rutor ? " >>
	fmap read getLine >>= \n ->
	
	putStr "Antalet barn ? " >>
	fmap read getLine >>= \b ->
	
	let v = div n 2 + mod n 2 in
	let s = div n 2 in
	let nr = sum [bin v k * bin s (b-k) * (mod k 2 + mod (b-k) 2) | k <- [b - min s b..min v b]] in
	
	putStrLn.("Svar: " ++).show $ fromIntegral nr / (fromIntegral $ bin n b)

bin n k = product [n-k+1..n] `div` product [1..k]

Tävlingsprogrammering/Uppgifter/Hoppleken: Skillnad mellan sidversioner

Nuvarande version från 16 april 2020 kl. 16.31

Lösning

Matematisk Lösning

Navigeringsmeny

Sök