Ifi-mesterskapet i programmering 1999

Ifi-mesterskapet ble avholdt i Ifis lokaler den 23. oktober etter forutgående invitasjon.

Oppgavene

Denne oppgaven er rimelig enkel hvis den løses med «bredde først»-søk. De som prøvde på «dybde først»-leting fikk alle problemer med tiden.

Test-data Test-resultat Min løsning Vinnerlagets løsning

Oppgave B: Time and motion

Denne oppgaven er ikke vanskelig, men krever pinlig nøyaktighet. En ørliten feil vil gi enorme utslag i resultatene. Dessuten er det umulig å sjekke resultatet for hånd.

Test-data Test-resultat Min løsning

Oppgave C: Bookshelves

Denne oppgaven løses enklest ved å lage et søketre av bokstavene i boktitlene. Da kan man rekursivt lete nedover i treet til man finner subtrær som får plass i en hylle.

Test-data Test-resultat Min løsning

Oppgave D: A calendar

Denne oppgaven regner jeg for den nest enkleste. Det er bare spørsmål om å være nøyaktig og å passe på at den vertikale sentreringen blir riktig.

Test-data Test-resultat Min løsning Vinnerlagets løsning

(Denne oppgaven var det flest som klarte, men også den som hadde flest innleverte feil.)

Oppgave E: Kissin' cousins

Denne oppgaven regner jeg som den nest vanskeligste. Det å bygge opp en graf av familietreet bør ikke by på store problemer, men søkealgoritmene er ikke trivielle.

Test-data Test-resultat Min løsning

Oppgave F: Pendulum

Dette problemet er nok det vanskeligste, men hvis man husker litt trigonometri fra videregående skole, bør det ikke være umulig å løse den. Det viktigste er å ta for seg de tre tingene som kan skje når pendelen svinger:

Pendelsnoren trekker en spiker. Da svinger pendelen videre, man den har fått et nytt rotasjonspunkt.
Pendelen kommer opp til utgangshøyden. Da vil den fortsette å svinge slik frem og tilbake, og vi kan nå beregne svingbuen.
Pendelsnoren treffer ingen flere spiker, og snoren er for kort til at pendelen kommer opp til utgangshøyden. Da vil pendelen rotere rundt den siste spikeren, og vi må beregne omkretsen av denne rotasjonen.

Test-data Test-resultat Min løsning

Oppgave H: Train swapping

Denne oppgaven er den aller enkleste, spesielt om man innser at ombyttingen av vogner egentlig er en boble-sortering.

Test-data Test-resultat Min løsning Vinnerlagets løsning

Resultatet

Lag	Oppgaver							Totalt
Lag	A:Maze	B:Clock	C:Books	D:Calendar	E:Cousins	F:Pendulum	G:Trains	#OK	Tid
5	TT 3.11+40			X 1.58+20			2.36	3	8.45
8	X	3.47		2.04			3.16	3	9.07
4	X 1.54+20		X	XXX 3.56+60			X 3.32+20	3	11.02
2	T	X		X 3.02+20			2.51	2	6.13
7	2.17	X					X 4.54	2	7.10
1	TT			XXX			0.50	1	0.50
9	X			1.10			X	1	1.10
3				1.57				1	1.57
6	T						X	0	0.00
X-1	1.39			2.10	3.28	X	0.47	4	8.04

(En T betyr at programmet ikke ble godkjent fordi det brukte for lang tid, mens X betyr at programmet ikke er godkjent fordi det ga galt resultat. Lagene fikk et tillegg på 20 minutter for hver innlevering som ikke ble godkjent.)

Lagene

Standardklassen

1	Igor Rafienko	Martin Setek
2	Thomas Lund	Georg Lundesgaard
3	Kjetil Myhre	Audun Føyen	Stian Bakken
4	Eivind Kvedalen	Ketil Froyn
5	Andreas A. Hanssen	Steffen E. Thorkildsen
6	Kristoffer Gleditsch	Henrik Bakken	Siri Spjelkavik
7	Jon Grov	Knut Aksel Røysland
8	Marius Seglsten	Morten Lied Johansen	David Hsu
9	Morten Ofstad	Sverre Lunøe-Nielsen

Åpen klasse

X-1

Arne Gleditsch

Per Kristian Gjermshus

Veien videre

Andreas og Steffen reiste til semifinalen i 's-Hertogenbosch i Nederland 13-14. november. (På bildet sitter de nederst til venstre.)

De satset friskt, men hadde dessverre ikke dagen. De ble nummer 30 av i alt 40 lag.

Opprettet av Dag Langmyhr. Sist endret 10. januar 2000