Programmeringsolympiaden 2008: Onlinekvalet

Tävlingen består av sex uppgifter som alla finns i detta dokument. Snabblänkar finns här.

Uppgift 1 - Väggreparation
Uppgift 2 - Röstköp
Uppgift 3 - Gruppindelning
Uppgift 4 - Storken
Uppgift 5 - Pärlband
Uppgift 6 - Pyramidspaning

Lösningarna skickas in via Kattis Submit-sida.Problemets ID står i början av varje problembeskrivning. Observera att en lösning blir accepterad (Accepted) av Kattis bara genom att lösa exemplet som står i uppgiften. Detta är alltså ingen garanti för att lösningen ger någon poäng vid rättningen, som genomförs efter tävlingens slut.

För samtliga uppgifter gäller följande:

• Maximal exekveringstid: 5 sekunder.
• Maximal minnesanvändning: 32 Mb

OBS! Även om bara en rad skrivs ut så måste den alltid avslutas med radbrytning.

Problem id: vaggreparation

Framsidan av mitt hus är täckt med dekorativa kvadratiska brickor. Jag är dock orolig att några av brickorna inte sitter fast ordentligt och riskerar att ramla ner. Jag vill stadga upp de nuvarande brickorna så att väggen blir stabil. I figuren nedan är de ursprungliga brickorna svarta och de lediga utrymmena på väggen vita.

Väggen blir stabil om varje bricka är uppstadgad hela vägen från marken. För att fixa väggen ovan skulle jag behöva åtta brickor i de streckade positionerna nedan.

Givet en vägg, beräkna det minsta antalet brickor som krävs för att stadga upp de ursprungliga brickorna.

Indata

På första raden står två heltal: höjden (1 ≤ h ≤ 20) och bredden (1 ≤ w ≤ 40) på väggen. Därefter följer h rader, var och en innhållande en sträng bestående av exakt w tecken. Varje tecken i strängen är antingen ett 'X' (en bricka) eller ett '.' (ett ledigt utrymme). Den sista raden motsvarar den del av väggen som är närmast marken.

Utdata

Programmet ska skriva ut en rad med ett heltal: det minsta antal brickor jag behöver inhandla för att stadga upp de redan existerande brickorna.

4 12
..X...X.....
....X.X...XX
...........X
..X.......X.

8

Problem id: rostkop

Karl-Gunnar kandiderar till ordförandeposten i sin idrottsförening och vill inte riskera att förlora omröstningen. Han har lyckats få reda på vilken kandidat varje medlem tänker rösta på och tänker helt enkelt muta ett antal medlemmar så att de röstar på honom istället. Skriv ett program som beräknar hur många röster som måste köpas (d.v.s. medlemmar som behöver mutas) för att Karl-Gunnar ska vinna omröstningen. För att vinna krävs att man får fler röster än var och en av de andra kandidaterna.

Indata

På första raden står ett heltal: antalet kandidater (1 ≤ n ≤ 20). På andra raden står n heltal (mellan 0 och 1000): antalet röster varje kandidat skulle få utan mutor. Det första talet anger Karl-Gunnars röster.

Utdata

Programmet ska skriva ut en rad med ett heltal: det minsta antalet röster som behöver köpas för att Karl-Gunnar ska få fler röster än var och en av de övriga kandidaterna.

4
2 5 7 8

5

Problem id: gruppindelning

Under en skolutflykt ska eleverna delas in i olika grupper. Naturligtvis vill eleverna vara i samma grupp som sina kompisar. Skriv ett program som, givet namnet på varje elev samt vem som är kompis med vem, beräknar det maximala antalet grupper som eleverna kan delas in i (om eleverna får som de vill).

Indata

På första raden står ett heltal: antalet elever som ska på utflykt (2 ≤ n ≤ 100). Därefter följer n rader, var och en innehållande namnet på en elev. Varje namn är mellan 1 och 20 tecken långt och innehåller endast bokstäverna A-Z. Alla elever har olika namn. Sedan följer en rad med ett heltal: antalet kompispar (1 ≤ m ≤ 5050). Slutligen följer m rader innehållande kompisparen. För varje par anges två namn på samma rad, separerade med ett mellanslag.

Utdata

Programmet ska skriva ut en rad med ett heltal: det maximala antalet grupper som eleverna kan delas in i.

6
KALLE
MAJA
SARA
SVEN
HUGO
ANNA
3
KALLE ANNA
MAJA ANNA
SARA HUGO

3

Problem id: storken

En ibis-stork som bor vid Assuan-dammen hundra mil uppåt Nilen tänker hälsa på en kusin i Nildeltat. Han är dock ganska lat så att flyga själv är inget alternativ. Med tanke på den täta båttrafiken på Nilen bestämmer han sig för att lifta med flodbåtarna. Skriv ett program som, givet rutter, avgångstider och hastigheter för alla nedströms gående båtar, beräknar den tidigaste tidpunkten storken kan vara framme hos sin släkting.

Storken är resklar vid tidpunkten 0 timmar och han befinner sig då vid positionen 0 km. Resmålet ligger vid positionen 1000 km. Vi antar att storken utan fördröjning kan förflytta sig i "sidled" över floden, t.ex. från en båt till en annan eller från land till en förbipasserande båt. Däremot vägrar han flyga en enda kilometer längs med floden, så båtar måste användas för hela transporten.

Indata

Första raden innehåller ett heltal n, där 1 ≤ n ≤ 1000: antalet båtar. Därefter följer n rader som vardera beskriver en båt. Varje rad innehåller fyra heltal: startpositionen s, slutpositionen m, avgångstiden t samt hastigheten v, vilka uppfyller 0 ≤ s < m ≤ 2000, 0 ≤ t ≤ 1000 och 1 ≤ v ≤ 50. Positionerna anges i kilometer, avgångstiden i timmar och hastigheten i kilometer per timme. Rutten är planerad så att båten kommer fram till sin slutposition på ett helt klockslag, d.v.s. restiden (m-s)/v är alltid ett heltal.

Utdata

Programmet ska skriva ut en rad med ett heltal: det första hela klockslaget (d.v.s. antalet timmar efter tidpunkten 0) på vilket storken kan vara hos sin kusin. I samtliga testfall kan storken komma fram.

5
250 875 15 25
0 400 5 20
500 600 0 20
50 250 10 40
600 1100 30 15

57

Problem id: parlband

Du har en uppsättning pärlor i olika färger som du vill rada upp längs ett snöre. För att det ska se snyggt ut måste varje grupp av tre intilliggande pärlor bestå av tre olika färger. Skriv ett program som, givet antalet pärlor av varje färg, beräknar på hur många olika sätt pärlorna kan placeras på snöret. Alla pärlor måste användas.

Indata

På första raden står ett heltal: antalet olika färger på pärlorna (3 ≤ n ≤ 5). Därefter följer en rad med n heltal: antalet pärlor av varje färg (mellan 1 och 8).

Utdata

4
4 3 2 1

10

Problem id: pyramidspaning

Vi antar nu att du vunnit Programmeringsolympiaden och befinner dig i Egypten, omgiven av pyramider av varierande höjd. Vi antar också att marken är alldeles plan så att du har fri sikt oändligt långt åt alla håll. På grund av jordklotets krökning finns det ändå ett gränsavstånd s kilometer, för hur långt bort du kan se en given pyramid, därefter kommer den "nedanför horisonten". Avståndet s beror naturligtvis på pyramidens höjd: ju högre den är desto längre bort kan den ses, eftersom vi räknar att vi ser pyramiden även om bara den yttersta spetsen sticker upp ovanför horisonten.

Om vi antar att dina ögon befinner sig 1.7 meter över marken så kan s beräknas med formeln där h är pyramidens höjd i meter, medan s är det maximala siktavståndet i kilometer.

Du färdas på en väg som genomkorsar öknen och som vi antar är oändligt lång, helt rak och följer y-axeln (x=0) i ett tänkt koordinatsystem. Skriv ett program som, givet koordinaterna samt höjden för ett antal pyramider, beräknar hur många pyramider du maximalt kan se samtidigt från någon plats utmed vägen samt anger det längsta intervall där detta maximala antal kan observeras. Programmet behöver inte ta hänsyn till att pyramiderna kan skymma varandra.

Indata

På första raden står ett heltal: antalet pyramider (1 ≤ n ≤ 10000). Därefter följer n rader med tre decimaltal x, y och h på varje rad, vilka anger koordinaterna (-1000 ≤ x,y ≤ 1000) i kilometer samt höjden (1 ≤ h ≤ 1000) i meter för varje pyramid.

Utdata

4
-11.0 -17.5 40.5
-20.5 15.8 35.0
42.5 12.7 116.4
-15.3 46.85 8.05

3
5.1448 7.5615