Norgesmesterskapet 2000

NM 2000 ble arrangert 21. oktober på følgende steder: Arrangementet er beskrevet i invitasjonen.

Oppgavene

Oppgavesettet besto av syv oppgaver:
A: Traffic planning
var en øvelse i enkel traversering av grafer. Man bygger en rettet graf av gatenettet (samt en liste over alle gatene i den gitte rekkefølgen); så besøker man rekursivt alle pekerne og merker gatene man kommer til. De gatene som ikke er merket, blir skrevet ut til sist.
B: A model railroad
Denne oppgaven krever en «brute force»-løsning; det er ikke noe annet å gjøre enn å starte i utganspunktet og så prøve å legge jernbanespor i ulike retninger inntil man kommer i mål.
C: Comment removal
Denne oppgaven er ikke vanskelig, men man må være nøyaktig for å få med seg alle særtilfellene. Mange hadde problemer med kommentartegn i tekstkonstanter eller anførselstegn i kommentarer.
D: R.Ø.L.P.
Denne oppgaven innebærer leting etter det gitte mønsteret («RØLP»). I stedet for å prøve alle rotasjoner, er det raskere å bare sjekke om du har fire etterfølgende tegn med en gitt forskjell i kodingsverdien.
E: A fair jury
Når man først har lest seg gjennom den matematiske formuleringen, ser man at dette er en oppgave hvor det er snakk om å plukke de m elementer 1-n som gir best verdi i evalueringsfunksjonen. Det er viktig å avskjære søkingen så raskt som mulig for at programmet ikke skal ta for lang tid; løsningsforslaget brukte 32 sekunder på testdataene.
F: Radio direction finder
Dette problemet krevde litt kunnskap i elementær geometri: man må kunne beregne hvor to linjer møtes. Problemet blir litt vanskeligere ved at alle beregninger må gjøres to ganger siden alle posisjoner kan være på begge sider av radiofyrene.
G: Returning books
Dette problemet er ganske lett når man har definert datastrukturen; jeg brukte en toveis liste med alle bøkene i sorteringsrekkefølgen. Å låne og levere tilbake bøker dreier seg da bare om å sette et statusflagg i det enkelte bokobjektet.
Interesserte kan studere løsningsforslaget samt testdata som ble benyttet ved evalueringen.

Løsning Testdata
A gater.c infil.A utfil.A
B tog.c infil.B utfil.B
C pascal.c infil.C utfil.C
D rolp.c infil.D utfil.D
E jury.c infil.E utfil.E
F Beacon.java infil.F utfil.F
G bib.c infil.G utfil.G

Resultatet

De 10 beste lagene ble disse:
Nr Lag Institusjon A B C D E F G Løst Tid
1 Programmeringsgruppa HiSør-Trøndelag 0.41 2.36 5.27 5.04 4 13.48
2 (HB) UiOslo 0.48 1.40 2.07 3 4.35
3 NoSuchTeamNameException NTNU 2.45 5.25 4.17 3 12.27
4 Agurk UiBergen 3.16 4.14 5.35 3 13.05
5 for(;ever;c++) UiBergen 0.48 1.42 2 2.30
6 (AAH) UiOslo 1.35 1.08 2 2.43
7 Y UiBergen 0.40 2.38 2 3.18
8 ANT UiBergen 1.58 3.57 2 5.55
9 (EK) UiOslo 4.59 1.11 2 6.10
10 (IR+MTS) UiOslo 1.57 4.31 2 6.28
De fire beste lagene reiser til semifinalen i Darmstadt i Tyskland 18.-19. november.

NB! På grunn av lokale tekniske problemer har flere lag og spesielt «NoSuchTeamNameException» fått en dårligere plassering enn de fortjener utifra innsatsen under konkurransen.

(Det finnes også en fullstendig resultatliste for alle de 51 lagene.)

Sist oppdatert 12.06.2001 av Dag Langmyhr.