Programmeringsolympiaden 2007: Onlinekvalet

OBS! Tävlingstiden är förlängd till 25 februari

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

Uppgift 1 - Soldaterna
Uppgift 2 - Kölappar
Uppgift 3 - Begränsningsarea
Uppgift 4 - Mångtydig Morse
Uppgift 5 - Tennisklubben
Uppgift 6 - Kontaktförmedlingen
Uppgift 7 - Kuben

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: 10 sekunder.
• Maximal minnesanvändning: 32 Mb

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

Problem id: soldat

Ett antal soldater står på ett led alla vända mot furiren, när han ger ordern "höger om". Eftersom många av soldaterna har svårt att skilja på höger och vänster blir det mest slumpen som avgör åt vilket håll de vänder sig. Ett exempel visas på första raden i figuren ovan. De soldater som på så sätt hamnar "öga mot öga" med en granne förstår båda två att de vänt sig åt fel håll och gör därför helt om (180 grader), för att kanske hamna öga mot öga med den andra grannen. Denna procedur fortsätter (steg 1 och 2 i figuren) och upphör då inga soldater längre är vända mot varandra (steg 3).

Indata

Den första raden består av heltalet n, där 2 ≤ n ≤ 100, som anger antalet soldater. Den andra raden består av en sträng med n tecken, dår varje tecken är antingen V eller H. Dessa anger åt vilket håll soldatens näsa pekar i utgångsläget.

Utdata

Programmet ska skriva ut hur många steg som behövs från utgångsläget tills lugnet infinner sig.

6
VHVVHV

3

Problem id: kolappar

Du råkar gå till banken i rusningstid. Ett vanligt kölapps-system används, men n kunder har lägre könummer än du. Dock är m kassor öppna. Skriv ett program som, givet hur lång tid varje kunds ärende tar, beräknar hur lång tid det tar innan det är din tur.

Varje kund har ett bankärende som tar ett helt antal minuter. Så fort det finns en ledig kassa kallas nästa person i kön fram. Kundbytet tar inget tid i anspråk. För enkelhets skull förutsätter vi att i det ögonblicket du tar din kölapp, låt oss kalla det tiden 0, så är alla kassorna lediga och m kunder kallas alltså fram omedelbart (vilket kan inkludera dig om n < m).

Indata

På första raden står två heltal: antalet personer före dig i kön (1 ≤ n ≤ 100) och antalet öppna kassor (1 ≤ m ≤ 10). Därefter följer en rad med n heltal i intervallet 1..20, antalet minuter för varje kunds ärende. Det första talet anger tiden för den första kunden i kön, det andra för den näst första kunden o.s.v.

Utdata

Programmet ska skriva ut efter hur många minuter du kallas fram och får påbörja ditt ärende.

7 3                 
2 5 6 2 4 5 3

8

Problem id: area

Betrakta den tredimensionalla figuren ovan. Den är ihopsatt av ett antal 1x1x1 kuber i ett 3d-rutnät. Om vi begränsar oss till figurer som har staplar fästa i "marken", kan figuren på bilden beskrivas genom att ange höjden för varje stapel:

4	2	3	1
2	1	0	1
0	0	0	1

Indata

På första raden står två heltal r och k, där 1 ≤ r,k ≤ 50. Sedan följer r rader med k heltal på varje rad: höjden (≤ 50) för varje stapel.

Utdata

Programmet ska skriva ut ett heltal: figurens begränsningsarea.

3 4
4 2 3 1
2 1 0 1
0 0 0 1

54

Problem id: morse

Tabellen ovan visar Morsealfabetet. Punkter och streck används för att beteckna korta respektive långa signaler. Normalt lämnas morsemeddelanden med ett uppehåll mellan varje bokstav, till exempel --. . - som står för ordet GET. Men av en obestämd anledning kommer det just nu in meddelanden i en oavbruten följd av långa och korta signaler, alltså utan uppehåll mellan bokstäverna. GET-signalen blir då --..- och kan därför stå för många andra bokstavssekvenser, t.ex. MU. Skriv ett program som tar emot en följd av streck och punkter, och som sedan skriver ut varje möjlig kombination av bokstäver som svarar mot den givna indatasträngen

Indata

På första raden står signalsträngen, som består av högst 15 tecken. Därefter följer 26 rader som beskriver Morse-alfabetet. Denna information är samma i alla testfall och motsvarar precis tabellen ovan. Den första av dessa rader ger signalen för A, den andra för B o.s.v.

Utdata

Programmet ska skriva ut alla möjliga bokstavssekvenser som svarar mot den givna indatasträngen. Sekvenserna ska skrivas ut i alfabetisk ordning med en per rad. Endast versalerna A-Z får förekomma.

--..-
.-
-...
-.-.
-..
.
..-.
--.
....
..
.---
-.-
.-..
--
-.
---
.--.
--.-
.-.
...
-
..-
...-
.--
-..-
-.--
--..

GA
GET
MEA
MEET
MIT
MU
TDT
TNA
TNET
TTEA
TTEET
TTIT
TTU
TX
ZT

Problem id: tennis

I en tennisklubb finns n spelare. De är alla rankade från den bäste med rankingnummer 1 till den sämste som har rankingnummer n. Men tennis är en oberäknelig sport och det kan bli så att den som är rankad 99:a någon gång vinner mot 32:an. Om 32:an i sin tur slår 85:an, som i sin tur slår 44:an som slår 1:an, innebär det att 99:an har en kedja med bara fyra länkar till toppen! Du ska skriva ett program som för en given spelare räknar ut längden av den kortaste kedjan upp till toppen, eller avgör att ingen sådan kedja finns. För den som direkt har vunnit mot 1:an är längden alltså 1 och för 1:an själv är förstås längden 0.

Indata

På första raden står två heltal n och k, (1 ≤ n ≤ 100 och 1 ≤ k ≤ n), där n är antalet spelare och k är rankingnumret för den spelare som vi är intresserade av. På andra raden står ett heltal m, (1 ≤ m ≤ 1000), antalet matcher som har spelats. Därefter följer m rader, vardera beskrivande en match. På var och en av dessa rader står två heltal i intervallet 1..n. Det första talet är rankingnumret för den spelare som vann matchen och det andra talet är rankingnumret för den spelare som förlorade matchen. Observera att samma par av spelare kan ha mötts flera gånger med samma eller olika resultat.

Utdata

5 4
8
1 3
2 5
4 2
5 2
3 4
5 1
2 3
1 4

3

Problem id: kontakt

En kontaktförmedling har specialiiserat sig på att para ihop människor med avseende på hur många intressen personerna har gemensamt. Personernas kön spelar däremot ingen roll. I en förmedlingsomgång deltar n personer. Var och en av dessa får fylla i ett frågeformulär med m stycken ja/nej-frågor av typen "Tycker du om katter?", "Programmerar du för nöjes skull?", etc. Målet är att varje person ska paras ihop med den av de andra personerna som har maximal överensstämmelse med de egna svaren, eller, om det finns flera som har maximal överensstämmelse, vem som helst av dessa.

Tyvärr är detta inte alltid möjligt. Två personer kanske båda passar bäst ihop med en tredje, medan denna tredje egentligen passar bäst ihop med någon helt annan person. Kontaktförmedlingen har dock kommit på en lösning på detta problem. Man väljer ut en mindre grupp personer och ser till att alla personerna i denna grupp paras ihop två och två så att önskemålet att alla får sin optimala partner bland personerna i den mindre gruppen tillgodoses. Då är dessa glada och nöjda eftersom de aldrig får veta att det kanske fanns någon person utanför den utvalda gruppen som egentligen passade ännu bättre.

Kontaktförmedlingen får betalt per antal nöjda kunder och man vill därför naturligtvis göra den utvalda gruppen så stor som möjligt. Du ska skriva ett program som beräknar det största antalet personer som kan ingå i gruppen.

Indata

På första raden står två heltal n och m, (4 ≤ n ≤ 20 och 10 ≤ m ≤ 100), där n är antalet personer och m är antalet frågor i formuläret. Därefter följer n rader, som var och en ger svaren för en person. Varje rad består av en sträng med m tecken som kan vara antingen j eller n. Det första tecknet anger svaret på första frågan (j=ja, n=nej), det andra tecknet anger svaret på andra frågan o.s.v. Alla personerna får naturligtvis frågorna i samma ordning.

Utdata

5 10
njjjnnnnnj
nnjnnnnnnn
jnjjnnjjnn
njjnnjjjjn
njnjjnjnjj

4

Exempel: Förklaring

Låt oss kalla personerna A, B, C, D och E i den ordning de ges i indata. Det enda sättet att få fyra nöjda kunder är att para ihop A med E (6 identiska svar) och C med D (5 identiska svar). Detta kan man göra trots att A egentligen passar bäst ihop med B (7 identiska svar), för B finns inte med i den utvalda gruppen. Observera att om man skulle para ihop A och B så skulle det inte bli något mer par eftersom C föredrar B, och E föredrar A.

Problem id: kuben

En kub av storleken 3x3x3 ska byggas ihop av ett antal tredimensionella "pusselbitar", som var och en består av ett antal sammanhängande småkuber, sammanlagt 27 stycken. I figuren ovan visas ett exempel på en sådan kub samt de fem pusselbitar den är uppbyggd av. För enkelhets skull är de avbildade roterade på det sätt som de sitter i kuben, men i verkligheten får pussel-lösaren de fem bitarna huller om buller. Du ska skriva ett program som tar emot en beskrivning av varje pusselbit och sedan vrider och pusslar ihop dem så att en kub med storlek 3x3x3 bildas.

Beskrivningen av pusselbitarna ges på samma sätt som i uppgift 3, d.v.s. biten läggs ner på ett 3x3 rutnät så att inga hålrum bildas och sedan anges höjden för var och en av de nio "staplarna". Låt oss t.ex. titta närmare på den blå pusselbiten. Den kan roteras så att den ligger enligt figuren nedan och kan därför beskrivas som i tabellen till höger.

När programmet har pusslat ihop kuben ska det, istället för att beskriva själva kubens uppbyggnad, räkna ut hur många av 1x1-kvadraterna på varje pusselbit som är exponerade på kubens utsida, d.v.s. som ligger på någon av kubens sex sidor. Anledningen till detta är att dessa tal är oberoende av hur man roterar den färdiga kuben.

Indata

På första raden står ett heltal n, (3 ≤ n ≤ 7): antalet pusselbitar. Sedan följer 3 rader för varje pusselbit, alltså sammanlagt 3n rader. På varje rad står tre heltal i intervallet 0..3, höjden för varje stapel.

Utdata

Programmet ska skriva ut n heltal separerade med blanksteg, antalet kvadrater av varje pusselbit som ligger på någon av kubens sex yttersidor. Ordningen på pusselbitarna ska vara samma som i indata. Om det finns flera lösningar kan du ange vilken som helst av dessa. Observera att summan av talen alltid ska vara lika med 54, vilket är kubens totala begränsningsarea.

5
1 1 0
1 0 0
1 1 0
0 0 0
0 3 0
2 2 1
0 1 1
1 1 0
0 0 0
1 0 0
2 0 0
1 1 0
0 0 2
1 1 1
0 0 0

12 13 8 11 10