Norgesmesterskapet i programmering 2001

Oppgave G: «Bridge placements»

Den naive løsningen, å teste alle mulige bru-plasseringer, vil ta alt for lang tid når det er mange bruer. Løsningen ligger i å innse at når den øverste brua er plasert, vil optimal løsning for de øvrige bruene være å plassere dem mest mulig jevnt nedover (og huske på at bakken fungerer som bru i nederste etasje).

For å finne plasseringen av øverste bru, er det enklest å starte med å plassere den i øverste etasje i det laveste huset, og så flytte den nedover til et minimum er funnet (dess flere bruer og/eller dess større forskjell mellom hus-høydene, dess nærmere toppen vil dette minimumet være). Med endel regning kan man også finne dette minimumet direkte.

Problemer

Dessverre ble det gjort en liten feil i programmeringen av løsningsforslaget så resultat-data ble feil. Dette medførte at ingen fikk godkjent denne oppgaven. (Program og data som nå ligger ute skal være korrekt.) Slikt er trist, og spesielt for de lagene som ble rammet.

Sist oppdatert 25.10.2001 av Dag Langmyhr.