Kommentarer och lösningar till uppgifterna i
Kvalet till Programmeringsolympiaden 2002.

Kom ihåg att alla sätt att lösa en uppgift är rätt utom de som är fel.
Lösningarna är skrivna i C/C++ och följer tävlingsstandarden på så sätt att de är helt okommenterade och obegripliga. Om någon VB/Pascalprogrammerare vill dela med sig av sina lösningar mottages dessa tacksamt.

Uppgifterna (PDF)
Testdata (PDF)

Uppgift 1 - Euro

Eftersom avgiften utgår om man växlar in och ut på samma bank, blir det lite krångligt att titta på växlingarna separat. Det enklaste är istället att göra en dubbel-loop: för varje kombination av ut- och inväxlingsbank (max 5*5 st) beräknas den totala kostnaden för resan. Den minimala kostnaden och de banker som hör ihop med denna kostnad sparas under tiden.

Lösningsförslag

Uppgift 2 - Primfaktorer

Att gå igenom serien kan göras antingen i en loop eller rekursivt som i lösningen nedan. För att hitta primfaktorerna till ett tal N behövs ingen smart algoritm eftersom talen är så små. Exempelvis kan man testa alla tal K med början från 2 och kolla om N är jämnt delbart med K. I så fall är K en primfaktor eftersom det inte fanns något lägre tal som N var delbart med. När man hittat en primfaktor K så dividerar man N med K och fortsätter leta där man slutade. Man måste naturligtvis tänka på att samma faktor kan förekomma flera gånger.

Lösningsförslag

Uppgift 3 - Kedjebrev

Håll reda på antal personer c som har fått brev i senaste omgången, från början är c = m. I varje omgång kan man då förvänta sig att den person som står på tur att få pengar ska få c kronor, därför blir antalet avhoppare i den omgången skillnaden mellan c och det verkliga beloppet. Nu vet vi att antalet personer som fortfarande är med är lika med det verkliga beloppet och genom att multiplicera med m så får vi c för nästa omgång.

Lösningsförslag

Uppgift 4 - Tomter till husen

Här finns två (minst) olika metoder. Den mest effektiva är att för varje längd på tomten hitta den minimala och maximala bredden och sedan låta bredden anta alla värden däremellan och beräkna arean. Den minimala bredden erhålls genom att trycka ihop modulerna så mycket som möjligt, den maximala genom att dra en lång "utstickare". Det är lätt att kontrollera på papper att det inte finns någon "glesare" placering av modulerna eftersom de måste ha en kant gemensam. En sämre lösning (som ändå fungerar eftersom det maximala antalet moduler är så litet) är att generera alla möjliga husformer med "brute force". Detta kan göras rekursivt. Man börjar med två moduler och försöker sedan utöka med en modul i alla tänkbara riktningar. När man har satt dit denna försöker man sätta nästa i alla möjliga riktningar. Hela tiden håller man reda på maximalt/minimalt x och y så att man när den sista modulen sätts på plats lätt kan räkna ut arean.

För att undvika dubletter i båda dessa metoder är det enklast att ha en lista över areor (t.ex. 1 till 300 så får man med alla med god marginal). Från början är ingen av dessa areor markerad men så fort man hittar en husform markerar man dess area som möjlig i listan. Efteråt går man igenom listan och räknar hur många areor som har markerats.

Lösningsförslag

Uppgift 5 - Priser med mynt

Även här finns flera olika möjligheter. Först gäller det att inse att talen inte kan ha mer än 3 siffror (eftersom 4*12<1000/20). Därför finns det högst 3*12 mynt totalt. Ett enkelt sätt är då att testa alla möjliga kombinationer av antal femtioöringar/antal enkronor/antal extramynt (högst 19*37*37 stycken, jämnt antal femtioöringar) med hjälp av en trippel-loop. För varje kombination beräknar man myntens värde och därefter hur många mynt som skulle krävas för att skriva detta belopp. Om det antalet råkar överensstämma med det totala antalet mynt i kombinationen markerar man beloppet som möjligt på samma sätt som i uppgift 4. Efteråt är det bara att räkna antal markerade belopp.

Lösningsförslag

Uppgift 6 - Avstånd mellan tal

Detta är en typisk backtracking-uppgift (rekursiv). Man börjar att skjuta den första pilen där det finns ett r. Man markerar den ringen som upptagen, t.ex. genom att spara numret på pilen där istället för r:et. Sedan försöker man skjuta nästa pil på de återstående r:en i tur och ordning. När man hittat en ring som det är tillåtet att skjuta på markerar man denna och fortsätter skjuta nästa pil genom att låta funktionen anropa sig själv. Om man inte hittar något godkänt r, är det bara att låta funktionen avslutas för då fortsätter man att leta ringar för den föregående pilen. Man måste då naturligtvis göra den aktuella ringen ledig genom att sätta den till r igen. När man har lyckats skjuta lika många pilar som det finns ringar har man hittat en lösning, då är det bara att skriva ut ordningen och avsluta. För att se till att avståndet hela tiden växer, kan man ha en extra parameter till den rekursiva funktionen som beskriver det minsta tillåtna avståndet till nästa ring. Vid rekursionen sätter man denna parameter till avståndet mellan de senaste två ringarna.

Lösningsförslag