Lösningar till uppgifterna i
Kvalet till Programmeringsolympiaden 2006.

Lösningarna är skrivna i C och sparsamt kommenterade. Tillsammans med kommentarerna nedan hoppas jag ändå att de kan vara till hjälp.

Kom ihåg att alla sätt att lösa en uppgift är rätt utom de som är fel!
Skriv gärna om ni har frågor, kommentarer, tips om andra lösningar m.m. Kolla också gärna in träningssajten.
Pär Söderhjelm, par.soderhjelm@teokem.lu.se
Uppgifterna (PDF) 
Testdata (PDF)

Uppgift 1 - Fortsätt talföljden

Räkna ut skillnaden mellan de två första talen, d=k1-k2, samt skillnadens ändring, d.v.s. f=(k3-k2)-(k2-k1) som vi vet ska vara konstant under hela talföljden. Loopa sedan fram tio tal genom att i varje steg uppdatera skillnaden d genom att addera f.

Lösningsförslag

Uppgift 2 - Telefonipriser
För varje telebolag kan kostnaden som funktion av samtalstiden beskrivas med en rät linje, y=kx+m. Dessa linjer visas för testexemplet i diagrammet till höger. Svaret ser man lätt i figuren, följ bara den linje som ligger lägst hela tiden, d.v.s. först cyan, sen grön, röd och slutligen magenta. En lösning på uppgiften är sålunda att börja med bolaget med lägst fast avgift (som naturligtvis alltid är billigast för 0 minuter), beräkna skärningspunkten med de övriga bolagen, välja  skärningspunkten med lägst x-koordinat och sedan göra likadant med det bolaget. En annan lösning, som är enklare och kan användas eftersom vi har ett helt antal minuter, är att för varje minutantal räkna ut priset för alla bolag och spara vilket som är billigast. Sedan scannar man igenom minutantalen och kollar mellan vilka minutantal som "bolagsbyte" sker, där sätter man gränserna. Hur långt upp i samtalstid måste man räkna? Antingen stoppar man när det bolag med lägst minutkostnad blivit billigast eller så observerar man att skillnaden i fast kostnad är högst 1000 kronor och skillnaden i minutkostnad minst 1 öre, så efter 100000 minuter måste man vara i det sista intervallet.

Lösningsförslag

Uppgift 3 - Ramsan

Denna uppgift vållade inga problem för de flesta. Enklast är att spara statusen för varje barn (d.v.s. uträknad eller inte) i en vektor. När man räknar så hoppar man för varje ord i ramsan fram tills man hittar någon som inte är ute, men minst ett steg förstås. För att enkelt hantera att barnen står i ring kan man använda modulus (% i C, MOD i Pascal). s=(s+1)%n gör att s "går runt": 4, 5, 0, 1, 2 .... om s=6.

Lösningsförslag

Uppgift 4 - Minisudoku

Detta är en typisk backtracking-uppgift (vanligt förekommande på programmeringsolympiaden, läs t.ex. avsnittet om sökning på vår träningssajt).
Med det menas i det här fallet att man testar att fylla i en siffra i en tom ruta och försöker sedan lösa resten av sudokun. Om man inte hittar en lösning måste det ju betyda att siffran var fel så då suddar man ut siffran (eller i allmänhet tar ett steg tillbaka: backtrackar) och testar en annan siffra varefter man försöker lösa resten av sudokun igen. Men att försöka lösa resten av sudokun är ju precis samma problem som vi hade från början, bara med en ytterligare ruta ifylld. Därför passar sådana problem utomordentligt bra att lösa med en rekursiv funktion, d.v.s. en funktion som anropar sig själv. Denna kan t.ex. ta som parameter vilken ruta man håller på att fylla i, från 0 till 15 (lämpligtvis indikerar 16 att hela sudokun är ifylld). Om rutan är ifylld (enligt indata) ska den bara anropa sig själv med nästa ruta. Om den inte är ifylld testar man var och en av de fyra siffrorna och ser om den är OK med hänsyn till det som är ifyllt tidigare. I så fall sparas den siffran i rutan och funktionen anropar sig själv med nästa ruta. Efteråt (d.v.s. om man inte hittade någon lösning) måste man komma ihåg att radera den ifyllda siffran så att den inte blir "fastlåst". Överhuvudtaget måste man återställa saker och ting som de var innan siffran valdes, eftersom denna uppenbarligen var fel.

För att enkelt kolla om en siffra är OK så kan man använda sig av en 0/1-variabel för varje rad och siffra, d.v.s. den är 1 om siffran finns på raden och 0 om siffran inte finns. Således får du inte fylla i en siffra på raden om variabeln redan är 1. Motsvarande görs för kolumner och "kvartsrutor". Detta räcker för att garantera att sudokun blir korrekt.

Lösningsförslag - grundversion

Den enkla lösningen ovan fungerar bra eftersom det inte finns så många sätt att fylla i sudokun, man hinner i princip prova alla så det finns inget behov av att "skära bort" delar av sökträdet. Men antag nu att vi vill lösa den vanliga 9*9-rutors sudokun. Om du någon gång har löst en sådan sudoku för hand inser du lätt en nackdel med ovanstående algoritm, nämligen att den alltid fyller i rutorna i ordning, från den övre vänstra till den nedre högra. När du däremot löser den för hand väljer du omsorgsfullt vilken ruta som ska fyllas i härnäst, vilket gör att du, om du har tänkt rätt, aldrig behöver sudda ut den siffra du skrev. Att programmera hela denna tankeprocess är inte så lätt, men det intressanta är att om vi tillåter oss att backtracka behöver vi inte göra perfekta val hela tiden. På en sekund hinner vi kolla flera miljoner ifyllningar så det enda som krävs är att vi låter bli att göra de allra dummaste valen, eftersom dessa gör att vi kan fastna med en felaktig siffra och sedan förgäves försöka testa igenom alla ifyllningar av de övriga rutorna. En enkel optimering, som gör att programmet klarar alla vanliga tidnings-sudokus som jag har testat, är att för varje ruta kolla hur många siffror som passar där och sedan välja att fylla i den ruta som har minst antal alternativ. I förslaget nedan är därför parametern som beskriver vilken ruta som fylls i utbytt mot en funktion som returnerar just den ruta med minst antal alternativ. Annars är ingenting ändrat förutom att all explicit omnämning av 2 har bytts ut mot D så att man kan välja att sätta D till 3 för den vanliga sudokun eller till och med 4 (om man ändrar BASE till 'A' så att A-P används).

Lösningsförslag - bättre version, klarar större sudokus
Uppgift 5 - Regeringsbildning

Problemet kan delas upp i två delproblem:
1. Beräkna oenigheten för en given regering
2. Testa alla regeringar och av dem som har majoritet välja den med lägst oenighet.

Det första problemet blir mycket enklare om man inser att en regerings position alltid blir medianen av de ingående partiernas positioner (eller vilken som helst av de två "mittpositionerna" om antalet partier är jämnt). Detta kan lätt visas på följande sätt. Antag att regeringen intar medianpositionen p och det finns x partier med lägre position än p, y partier med högre position och således n-x-y partier med positionen p. Om regeringen nu istället antar en position p+1 kommer ändringen i oenighet att bli x + (n-x-y) - y = n-2y, eftersom de partier med position lägre eller lika med p kommer att få flytta sig ett steg längre medan partierna med högre position får flytta sig ett steg kortare. På motsvarande sätt blir ändringen i oenighet n-2x om positionen p-1 väljs. Men om p nu är medianen är vi garanterade att x<=n/2 och y<=n/2. Härav följer att båda dessa ändringar är större än eller lika med 0 och p är därmed en optimal position bland (p-1, p, p+1). Väljer vi en position längre ifrån medianen blir det bara ännu värre; allt färre partier vinner på ändringen och allt fler förlorar på den. Alltså är p en optimal lösning bland alla positioner.

Oenigheten för en given regering kan därför beräknas genom att sortera de ingående partiernas positioner och välja den mittersta, eller som i förslaget nedan genom att kolla hur många partier som ligger på varje position och sedan scanna igenom positionerna tills minst hälften av partierna har passerats. Då återstår endast problem 2, att testa alla regeringar. Detta är inget stort problem eftersom det högst kan finnas 2^10=1024 möjliga regeringar. Att generera alla regeringar kan göras med en rekursiv funktion innehållande en loop från 0 (partiet finns inte med) till 1 (partiet finns med). Ännu enklare är att tänka på varje regering som ett binärt tal där varje bit talar om huruvida ett parti finns med eller inte. I så fall behövs bara en loop från 0 till 2n-1 och sedan plockas varje bit ut med bitvisa operatorer: b & (1 << a) ger den a:te biten (från höger) i talet b.

Lösningsförslag
Uppgift 6 - Byggsatshus

Även detta problem blir lättare om man isolerar ett delproblem, nämligen att räkna ut på hur många sätt W(n,k) man kan placera k fönster på en sida med längden n. Om k=0 finns det förstås en möjlighet och om k>(n-1)/2 finns ingen möjlighet (här har vi tagit hänsyn till att fönstren inte får sitta längst ut i hörnen). För mellanliggande k kan man räkna ut antalet möjligheter genom en rekursionsformel. Det finns nämligen två alternativ, i en viss position kan man antingen sätta ett fönster eller inte. Om man sätter dit ett fönster minskar antalet kvarvarande fönster med 1 men samtidigt minskar den tillgänliga längden med 2 eftersom fönstren inte får sitta direkt bredvid varandra. Om man inte sätter dit ett fönster ändras förstås inte antalet kvarvarande fönster men å andra sidan minskar den tillgängliga längden bara med 1. Alltså har vi för mellanliggande k:

W(n,k) = W(n-2, k-1) + W(n-1, k)

Denna formel tillsammans med specialfallen ovan kan naturligtvis lätt implementeras med en rekursiv funktion. För att snabba upp programmet (vilket inte är nödvändigt här men är ett generellt trick som kan användas för svårare problem) kan man observera att denna funktion kommer att anropas många gånger med samma parametrar. Så varför inte spara värdet på W(n,k) i en tabell när vi har räknat ut det och i början av den rekursiva funktionen lägga in en if-sats som kollar om vi redan vet värdet på W(n,k) och i så fall bara ta det från tabellen istället för att beräkna det rekursivt.

Det återstår nu att lösa hela problemet. På varje hussida kan vi sätta godtyckligt många fönster (naturligtvis begränsat av det totala antalet på hela huset) och dessutom eventuellt en dörr. Det totala antalet möjliga hus får man sedan genom att summera över alla dessa valmöjligheter. För varje val måste vi räkna ut hur många sätt fönstren och dörrarna kan placeras på sidan men dessutom multiplicera med antalet möjligheter det finns att konstruera de återstående hussidorna när de totala antalen fönster och dörrar korrigerats för de val vi har gjort på den aktuella hussidan. Eftersom detta är i stort sett samma problem används lämpligtvis ytterligare en rekursiv funktion. Dörrhanteringen underlättas av att det ur W-funktionens synvinkel inte är någon skillnad mellan fönster och dörrar, så antalet sätt att placera k fönster och en dörr på en sida med längden n ges av (k+1)*W(n,k+1) eftersom vilken som helst av de k+1 "sakerna" kan vara dörren. Har man kommit på allt detta är det bara att hålla tungan rätt i mun när man skriver programmet så man inte tänker fel på en etta hit eller dit. 

Lösningsförslag