Kommentarer till uppgifterna i kvalet 2001

Kom ihåg: Alla sätt att lösa en uppgift är rätt utom de som är fel.

1. Plankan

Den enklaste lösningen är en kort rekursiv algoritm. Man försöker i tur och ordning lägga till en bräda på 1m, 2m resp. 3m varefter man kör samma funktion igen för återstoden av brädan. När man fyllt precis hela plankan ökar man en räknare. Det finns många optimeringsmöjligheter (t.ex. med hjälp av dynamisk programmering) men ingen som är nödvändig för att klara den givna maxlängden.

2. Vågen

Här gäller det att hitta mönstret i hur vikterna fördelar sig. Om man börjar med 1-kilosvikten måste ett av följande villkor gälla:

När detta är gjort är ju viktskillnaden mellan skålarna delbar med 3. Om man utför divisionen kan man sedan behandla 3-kilosvikten precis som om den vägde 1 kg. Proceduren fortsätter tills inga fler vikter behövs.

3. Siffersumma

För varje startvärde man vill undersöka låter man helt enkelt serien ha sin gång. De enstaka siffrorna beräknas i Pascal och C lämpligen med hjälp av div och mod respektive / och %. Antingen kommer man så småningom fram till 1, eller också kommer man in i en loop och då kan man exempelvis avbryta efter 1000 iterationer eftersom man då är säker på att man är inne i en loop.

4. Halsbandet

Om man letar efter en färg i taget (för att till sist ta den bästa lösningen av de tre färgerna), så går uppgiften helt enkelt ut på att man ska hitta de två längsta oavbrutna sekvenserna. Då kan man nämligen alltid ta bort pärlorna där emellan och få sin optimala lösning. Det finns dock två svårigheter. För det första ska man, om det finns flera möjligheter med samma antal pärlor i rad, hitta den som minimerar avståndet mellan sekvenserna. För det andra kan man behöva gå över skarven vilket gör att det blir svårt att definiera avståndet mellan två sekvenser.

Därför skulle jag föreslå en tråkig men enkel algoritm, som utnyttjar datorns snabbhet. Notera att de möjligheter till bortplockning man kan göra är max 80 * 80  (80 möjligheter för början och 80 för slutet av bortplockningen). Låt programmet gå igenom alla dessa (med hjälp av två enkla for-loopar) och testa sedan för varje färg hur många pärlor som ligger i följd. Ett bra sätt att få med skarven är att lägga två halsband i följd och sedan se till att man plockar bort på ett sådant sätt att de kvarvarande ligger i följd. Antalet jämförelser blir maximalt 80 * 80 * 3 * 80 = 1,5 miljoner, vilket en dator klarar av ganska snabbt.

5. Planket

Här gäller det att kunna jobba med räta linjens ekvation, det finns flera sätt att lösa problemet. Egentligen handlar det om att för varje par av barn hitta skärningspunkten mellan en linje som går genom barnen och en linje som går genom plankets ändpunkter. (En linje är oändligt lång till motsats från en sträcka). Om denna skärningspunkt ligger både mellan plankets ändpunkter och mellan barnen så kan barnen inte se varandra.

Skärningspunkten ligger inte mellan barnen - de ser varandra

I det enklaste fallet när inga av linjerna är lodräta (figuren ovan) kan man hitta skärningspunkten genom att sätta Kx+M=kx+m och sedan undersöka om x ligger mellan x-värdena för barnen resp. planket. Man kan lätt göra ett specialfall när ena linjen är lodrät. Man måste också kolla om linjerna är parallella. Alternativt kan man representera linjerna som vektorer vilket ger en enklare lösning.

6. Robot

Hur många olika svar (kartor) finns det? 2^16 = 65536 st. Detta låga antal gör att man med gott mod kan dela upp problemet i två delproblem:

  1. Generera alla möjliga kartor.
  2. För varje karta: Låt roboten börja gå från varje dörr och se var den hamnar. Så fort den hamnar vid fel dörr vet man ju att kartan är fel och man kan då gå vidare till nästa karta. Detta gör att mycket tid sparas, ofta behöver roboten kanske bara gå en eller två vandringar. Om den går rätt från alla 16 dörrarna har man hittat sin lösning.

I praktiken görs kartorna lämpligen rekursivt och "innerst", d.v.s. när alla 16 rutorna tilldelats en riktning, anropas en funktion som kör vandringarna. En vandring sker enklast genom att hålla reda på robotens riktning och position och iterera tills den stiger ut. Lägg märke till att tack vare de relativa riktningarna kan roboten aldrig fastna där inne. Inte heller kan den komma ut genom samma dörr för olika ingångsdörrar.

Ett tips: Dörrarnas numrering kan tyckas vara lite svår att koda. Det enklaste sättet är att använda konstanta arrayer som lagrar startposition (x och y) samt startriktning för var och en av de 16 dörrarna. Om riktningen anges med 0 (öster), 1 (norr), 2 (väster) eller 3 (söder) kan man alltså i C skriva

int rs[16] = {0,1,2,3,3,3,3,3,3,2,1,0,0,0,0,0};  // Start-raden
int cs[16] = {0,0,0,0,0,1,2,3,3,3,3,3,3,2,1,0};  // Start-kolumnen
int ds[16] = {0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3};  // Start-riktningen

Vill du läsa mer om algoritmer: Programmeringsolympiadens tränings-sajt
Än så länge innehåller den mest sådant som kan vara intressant inför de internationella tävlingarna, men vissa saker kan vara nyttiga även i svenska finalen.

Om du har frågor eller kommentarer om uppgifterna eller något annat: Skriv till
Pär Söderhjelm,  paso3493@student.uu.se   eller
Håkan Strömberg,   hakan@haninge.kth.se