Programmeringsolympiaden 2011: Onlinekvalet

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

Uppgift 1 - Snöskottning
Uppgift 2 - Bokstäver
Uppgift 3 - Erdös-nummer
Uppgift 4 - Dela tårtan
Uppgift 5 - Betygsoptimering
Uppgift 6 - Snailbook

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: 64 Mb

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

Problem id: skottning

Schott har som många andra haft problem under vintertiden med allt snö. Schotts hus måste skottas ofta, men han tycker själv att skotta varje dag är för ofta. Du ska hjälpa Schott att sätta upp ett skott-schema för de kommande N dagarna. Till din hjälp har du en detaljerad väderleksprognos, så du vet exakt hur många cm det snöar eller smälter varje dag (innan kvällen). När det ligger minst H cm snö en kväll så är det dags att skotta, och när man skottar så försvinner all snö. Från början är det ingen snö alls.

Indata

Första raden innehåller två heltal, antalet dagar 1 ≤ N ≤ 100 och snötröskeln 1 ≤ H ≤ 1000. Därefter följer N rader vardera innehållande ett heltal mellan -100 och 100 (inklusive). Dessa tal beskriver hur många cm snö det kommer under var pch en av de kommande N dagarna. Ett negativt värde betyder att denna mängd smälter istället (men snötäcket kan naturligtvis aldrig bli mindre än 0).

Utdata

Utdatat ska bestå av ett heltal, antalet kvällar Schott måste skotta.

10 27
5
-7
8
19
-20
22
8
26
-15
14

2

Problem id: bokstaver

Sofie håller på att lära sig läsa. Varje vecka lär hon sig en ny bokstav. Men otålig som hon är vill hon varje vecka välja den bokstav som gör att hon kan läsa flest nya ord (vi antar att för att kunna läsa ett ord måste man kunna alla de ingående bokstäverna). Skriv ett program som, utifrån en ordlista, bestämmer i vilken ordning Sofie ska lära sig bokstäverna.

Indata

På första raden står ett heltal N, antalet ord i ordlistan, där 1 ≤ N ≤ 10000. Därefter följer N rader med ett ord på varje rad. Varje ord består av minst 1 och högst 10 tecken. Endast versalerna A-Z förekommer.

Utdata

Programmet ska skriva en rad med de 26 bokstäverna A-Z i den ordning som gör att Sofie varje vecka kan läsa så många nya ord som möjligt. Om det någon vecka finns flera möjliga bokstäver som ger samma antal nya ord ska du välja den som står först i alfabetet.

7
ANNA
I
KALAS
BAKA
ABBA
ARASH
PAR

IABKNCDEFGHJLSRPMOQTUVWXYZ

Problem id: erdos

Matematikern Paul Erdös är bl.a. känd för att vara den matematiker som skrivit flest matematiska publikationer (Leonhard Euler har dock flest skrivna sidor). Erdös samarbetade väldigt mycket i sina publikationer. Ociterade källor hävdar att han ofta var temporärt inneboende hos en kollega. Under besöken skrev han en publikation tillsammans med kollegan och när gästfriheten tog slut flyttade Erdös vidare till nästa kollega.

Det innebär stor prestige att ha skrivit en publikation med Erdös. De som har skrivit en publikation med Erdös definieras ha Erdös-nummer 1. Ifall man skrivit en publikation med en person med Erdös-nummer 1 så får man Erdös-nummer 2 o.s.v.

Givet en lista över publikationer, skriv ut en lista med alla inblandade matematikers Erdös-nummer.

Indata

Först raden innehåller två heltal, 1 ≤ N ≤ 5000 och 1 ≤ M ≤ 40000, antalet matematiker respektive antalet publikationer. Därefter följer M rader. Varje rad börjar med ett heltal, antalet matematiker som samarbetade i publikationen. Sedan följer matematikernas namn (mellanslags-separerade), ordningen på matematikerna spelar ingen roll. Matematikernas namn består av 1 till 20 stora bokstäver, 'A' - 'Z'. Inga olika matematiker har samma namn. Erdös heter ERDOS. I varje publikation kommer det vara minst 2 och högst 5 matematiker. Du kan anta att Erdös-numret är ändligt för alla inblandade matematiker.

Utdata

En nyrads-separerad lista med matematiker och deras Erdös-nummer. ERDOS ska vara med i denna lista, hans Erdös-nummer är alltid 0. Listan ska vara sorterad i alfabetisk ordning.

5 4
2 ERDOS IMMERMAN
2 JACKSON IMMERMAN
3 ERDOS JACKSON IMMERMAN
3 BACH JACKSON RUBINSTEIN

BACH 2
ERDOS 0
IMMERMAN 1
JACKSON 1
RUBINSTEIN 2

10 10
2 ERDOS JYVZ
2 QHD DNJMFFHIVNTXOR
2 GXNVNYPG ERDOS
2 JYVZ DNJMFFHIVNTXOR
3 RIZTHDDFLKTKHLUMS GXNVNYPG AOFJAZXUBICBIIPP
2 LFX GXNVNYPG
2 GOGDYHYXDRHCKQHQV AOFJAZXUBICBIIPP
2 AOFJAZXUBICBIIPP QHD
3 NWLMBD AOFJAZXUBICBIIPP QHD
2 DNJMFFHIVNTXOR NWLMBD

AOFJAZXUBICBIIPP 2
DNJMFFHIVNTXOR 2
ERDOS 0
GOGDYHYXDRHCKQHQV 3
GXNVNYPG 1
JYVZ 1
LFX 2
NWLMBD 3
QHD 3
RIZTHDDFLKTKHLUMS 2

Problem id: tartan

Du får en 5x5 matris som föreställer en tårta indelad i 25 områden. Varje område har en bokstav (vald bland A-E) som markerar dess "innehåll" (aprikos, banan, chokladbit, druva eller extragrädde). Dela tårtan i fem delar så att alla delar är sammanhängande, lika stora och innehåller samma saker.

Indata

5 rader vardera innehållande 5 tecken, valda bland A-E (men alla behöver inte förekomma). Antalet bokstäver av ett visst slag är alltid delbart med fem.

Utdata

Programmet ska skriva ut 5 rader med 5 tecken (valda bland 1-5), föreställande samma tårta som i indatan men där varje siffra nu motsvarar en tårtbit. Du kan räkna med att det alltid finns minst en lösning och det spelar ingen roll hur du numrerar tårtbitarna.

CBCAB
ABCAA
ACACB
ACACA
BCCCA

11114
12444
22245
32355
33355

Problem id: betyg

Albert är student, men har väldigt lite tid. Trots detta vill han ha så höga betyg som möjligt i skolan. Just nu läser Albert N stycken kurser samtidigt, och på varje kurs kan man få K olika betyg, från 0 till K-1. Varje kurs avslutas med en tentamen, och alla tentor går ungefär samtidigt så pluggandet måste ske innan tentorna börjar. Den j:te tentamen har betygsgränserna B_j,1, B_j,2,...,B_j,K-1. Albert har totalt T timmar kvar att plugga på. Han har räknat ut att för att få varje poäng på den j:te tentamen måste han plugga P_j timmar. Beräkna hur Albert skall plugga för att summan av hans betyg skall bli så hög som möjligt.

Indata

Första raden består av heltalen N, K och T. Därefter följer en rad med N mellanslagsseparerade heltal: P₁,P₂, ..., P_N. Till sist följer N rader med K-1 heltal vardera, betygsgränserna för varje ämne (det i:te talet på den j:te raden är alltså B_j,i). T och B_j,i är mellan 2 och 20'000. De övriga värdena (N, K, P_i) är mellan 2 och 100. Strikt bättre betyg har alltid strikt högre poäng, d.v.s. B_j,i > B_j,i-1.

Utdata

3 2 100
5 2 20
15
25
2

2

4 4 129
2 3 4 5
5 15 35
4 12 35
10 11 12
2 3 50

9

Problem id: snailbook

Sociala nätverk är inget nytt. Redan på 1800-talet användes informella nätverk för att brevledes sprida nyheter och skvaller. Det kunde gå till så att varje deltagare hade en sändlista med personer hon skickade brev till när hon fick veta någon nyhet.

Tänk dig att du vill sprida en intressant nyhet till alla i detta nätverk (du är inte själv en del av det). Skriv ett program som, givet allas sändlistor, beräknar det minsta antalet personer du måste skicka nyheten till.

Indata

Första raden innehåller ett heltal 1 ≤ N ≤ 10000, antalet personer i nätverket. Personerna är numrerade från 1 till N. Därefter följer N rader som vardera beskriver sändlistan för en person (den första listan gäller person 1, den andra person 2 o.s.v.). Första talet på varje rad anger listans längd 0 ≤ K ≤ 100 och därefter följer K tal: numren på de personer som listans ägare skickar brev till.

Utdata

Ett heltal, det minsta antalet personer du måste skicka nyheten till för att den ska spridas till alla N personer.

14
1 6
0
0
0
1 8
2 7 11
1 1
3 2 3 4
2 8 10
1 9
0
2 11 13
0
1 12

4