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:

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




Uppgift 1 - Väggreparation

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.

Exempel: Indata

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

Exempel: Utdata

8



Uppgift 2 - Röstköp

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.

Exempel: Indata

4
2 5 7 8

Exempel: Utdata

5

Exempel: Förklaring

Karl-Gunnar kan t.ex. köpa 3 röster som skulle tillfallit den fjärde kandidaten samt 2 röster som skulle tillfallit den tredje kandidaten. Då får han själv 7 röster medan övriga kandidater får 5 röster.




Uppgift 3 - Gruppindelning

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.

Exempel: Indata

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

Exempel: Utdata

3



Uppgift 4 - Storken

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.

Exempel: Indata

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

Exempel: Utdata

57

Exempel: Förklaring

Storken startar sin resa med båt 2 som avgår "klockan 5". Mellan klockan 12 och 13 blir denna båt omkörd av båt 4 och storken flyger över till den. Detta gör att storken hinner fram till position 250 km precis när båt 1 avgår och fågeln kan sedan åka med denna båt till dess slutposition. Där får storken vänta i drygt 8 timmar (på land) innan båt 5 kommer förbi och tar honom till kusinen, dit han anländer strax innan klockan 57.




Uppgift 5 - Pärlband

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.

De tio olika sätten pärlorna kan placeras i exemplet.

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

Programmet ska skriva ut en rad med ett heltal: antalet olika sätt pärlorna kan placeras på snöret. Svaret ryms alltid i ett 64-bitars heltal (long long i C++ respektive long i Java).

Exempel: Indata

4
4 3 2 1

Exempel: Utdata

10



Uppgift 6 - Pyramidspaning

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

På första raden ska programmet skriva ut ett heltal: det maximala antalet pyramider som kan ses samtidigt från någon plats utmed vägen. På andra raden ska programmet skriva ut två decimaltal ymin och ymax, vilka specificerar det längsta kontinuerliga intervall av vägen inom vilket det maximala antalet pyramider kan ses. Talen ymin och ymax måste vara korrekta med minst tre decimalers noggrannhet.

Exempel: Indata

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

Exempel: Utdata

3
5.1448 7.5615