Programmeringsolympiaden 2012: Onlinekvalet

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

Lösningarna skickas in via Kattis Submit-sida.Problemets ID står i början av varje problembeskrivning.

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

• Maximal exekveringstid: 5 sekunder (Poker och Tivoli har 10 sekunder).
• Maximal minnesanvändning: 64 Mb

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

Problem id: sjusovare

Enligt legenden så kommer den som sover länge på sjusovardagen (27:e juli) att vara trött ett helt år framåt. Låt oss säga att den som sover ända fram till klockan sju blir en sjusovare (även om begreppet sjusovare egentligen inte har med klockslaget sju att göra). Många har ovanan att snooza ett par gånger innan de går upp. Givet n personers alarmtid, snoozetid och antal snoozes ska du avgöra vilka av dem som blir sjusovare.

Indata

Utdata

5
6 45 10 3
9 00 00 0
6 45 10 1
6 55 10 1
6 55 3  1

1 2 4

Problem id: spellistan

Du vill göra din egen musikspellista. Du börjar med att skaffa n låtar som du aldrig hört innan (numrerade från 1 till n). Sedan lyssnar du igenom låtarna och tar bort dem du inte tycker om. Nu har du en färdig spellista!

Du vill dock inte lyssna igenom låtarna sekventiellt, utan i slumpad ordning. Du bestämmer dig för följande deterministiska slumpalgoritm. Du börjar med ett tal x₀ och en modulator M och beräknar sedan fram resterande tal med följande formel:

x_n+1 = x_n² mod M

Du låter nu talet x_i avgöra den i:te låten du ska lyssna på genom att starta från den första kvarvarande låten och trycka framåt x_i gånger (efter den sista kommer du tillbaka till den första o.s.v.). Observera att det är x₁ som avgör vilken den första låten blir.

Indata

Utdata

3 19 
4 3
1 4 3

3 4 1
5

Problem id: flyg

Bo Arding har startat ett flygbolag. Han har en tabell som visar hur lång tid det tar att flyga mellan olika flygplatser, och han har redan skapat en tidtabell för vilka sträckor bolaget ska trafikera och när flighterna (turerna ska avgå). Nu återstår bara en detalj: att köpa flygplan. Till sin förvåning upptäcker han att det är ganska dyrt med flygplan, så han vill inte köpa fler än nödvändigt. Skriv ett program som hjälper Bo att beräkna det minsta antalet flygplan som behövs för att flyga alla flighter (turer) i tidtabellen.

Vi tittar på alla fighter som avgår under ett dygn. Du kan anta att flygplanen befinner sig på vilka flygplatser du vill när dygnet börjar. Alla flygtider inkluderar in- och avlastning så en ny flight kan avgå vid samma tidpunkt som en annan anländer och ändå använda samma flygplan.

Flighterna i exemplet färgade enligt en tänkbar uppdelning: ett flygplan kan köra de röda, ett kan köra de blåa och ett kan köra de gröna flighterna. I allmänhet kan det gå flera flighter mellan två flygplatser.

Indata

På första raden står två heltal: antalet flygplatser (2 ≤ N ≤ 100) och antal flighter (turer) under dagen (1 ≤ M ≤ 500). Sedan följer N rader med N heltal på varje rad: en "avståndstabell" där det j:te talet på den i:te raden (D_ij) anger hur många minuter det tar att flyga från flygplats i till flygplats j. Samma sträcka kan ta olika tid i olika riktningar, men tar alltid minst en minut. Talen på diagonalen är alltid 0 och varje triplett (i,j,k) av flygplatser uppfyller triangelolikheten, d.v.s. D_ij + D_jk ≥ D_ik. Slutligen följer M rader som beskriver flighterna. Varje rad består av tre heltal A, B och T, som anger att en flight ska gå från flygplats A till flygplats B vid tidpunkten T, räknat i minuter från midnatt (1 ≤ A,B ≤ N och 1 ≤ T ≤ 1440, d.v.s. ett dygn).

Utdata

En rad med ett heltal, det minimala antalet flygplan som behövs för att genomföra de planerade flighterna.

6 7
0 150 50 110 45 120
145 0 180 90 60 80
50 160 0 40 38 45
110 90 37 0 50 20
47 60 40 52 0 65
120 80 40 20 60 0
1 2 170
6 5 400
5 4 470
2 6 318
4 3 520
3 6 700
2 1 25

3

Problem id: borsen

Evelina vill bli rik och tänker börja spekulera på börsen. Egentligen är hon dock rätt ointresserad av ekonomi och orkar aldrig läsa mer än den första aktiekursen i tidningen. Men, tänker hon, det är ni andra som krånglar till det. Om man bara köper och säljer i rätt lägen kan man ju lika väl tjäna pengar på detta enda företag, som vi kan kalla A. Genom att ständigt fråga sina vänner hur mycket fiskbullar de äter lär hon sig att förutsäga exakt hur A:s aktiekurs kommer att variera under N dagar framåt. Skriv ett program som beräknar hur mycket pengar hon har i slutet av denna period om hon hade 100 kronor från början och investerar optimalt. Hon kan aldrig låna pengar utan endast använda sina egna.

Aktiekursen uppdateras en gång om dagen och är densamma för köp och försäljning. Varje dag kan Evelina antingen köpa valfri mängd aktier, sälja valfri mängd aktier eller inte göra någonting. Mängden hon köper eller säljer behöver inte vara ett heltal. För varje transaktion hon gör måste hon betala en fast avgift. Avgiften betalas med kontanter, d.v.s. innan hon köper aktier måste hon först betala avgiften, och efter att hon har sålt aktier måste hon betala avgiften.

Indata

Utdata

6 
2.3
75.6
86.2
83.1
91.3
72.5
95.7

147.3742

Problem id: poker

Poker är ett kortspel som spelas med en vanlig kortlek där vardera av de 52 korten har en av fyra "färger" och en av 13 valörer, från 1 till 13. Man har alltid fem kort på handen, och dessa kort brukar kallas en "pokerhand". Spelet går ut på att få en så "bra" hand som möjligt, där en hand värderas enligt en speciell skala. (I verkligheten handlar spelet mer om att värdera chansen att man har bättre hand än motspelarna men det behöver vi inte bekymra oss om här.) Man förändrar handen genom att slänga ett valfritt antal av sina kort (0, 1, 2, 3, 4 eller 5 stycken) och ta upp lika många nya från toppen av den återstående kortleken. Ett sådant byte av valfritt antal kort kallar vi för en "omgång". De åtta handtyper som finns är:

1. Par: minst två kort av samma valör
2. Två par: minst två kort av en valör och minst två kort av en annan valör
3. Triss: minst tre kort av samma valör
4. Stege: alla fem korten med valörer i följd, t.ex. 1,2,3,4,5 eller 7,8,9,10,11. (men inte t.ex. 10,11,12,13,1)
5. Färg: alla fem korten av samma färg
6. Kåk: tre kort av en valör och två av en annan valör
7. Fyrtal: fyra kort av samma valör
8. Färgstege: en stege där alla korten har samma färg

Observera att med våra definitioner kan man exempelvis räkna en triss som ett par om man så önskar.

Kurt spelar ofta poker med sig själv. Han är besatt av att räkna ut hur många omgångar han minst måste byta kort i sin pokerhand för att uppnå olika handtyper, om han vet hur korten ligger ordnade i kortleken. Skriv ett program som, givet hans starthand och ordningen på korten i kortleken, räknar ut detta åt honom.

Indata

Utdata

R 1
S 10
H 10
K 8
R 3
K 4
S 3
K 1
R 6
S 9
H 3
R 8
S 5
S 12
R 10
S 2
K 9
H 11
H 4
R 5
H 6
R 11
K 12
H 12
S 7
H 2
K 10
R 13
R 4
K 13
S 4
S 1
H 9
S 13
K 7
H 13
H 5
K 3
R 2
K 5
H 8
K 2
K 11
H 1
R 7
S 11
S 6
S 8
K 6
R 9
H 7
R 12

0 1 2 4 3 3 7 11 

Problem id: tivoli

Lisa har kommit till tivolit och har bestämt vilka N attraktioner hon vill åka, hon vill åka varje attraktion en gång. För varje attraktion finns det två stycken anläggningar som är likvärdiga, det finns alltså totalt 2N anläggningar. Givet positionerna för samtliga anläggninar, hjälp Lisa att planera vilka N anläggningar hon ska välja och i vilken ordning för att minimera den sträcka hon måste gå för att ha åkt alla N attraktioner. Hon börjar dessutom vid entrén och ska också sluta där. Entrén är vid origo.

Tivolit i exemplet med origo som ett blått kors och Lisas väg utritad. Den första anläggningen av varje attraktion är färgad rosa och den andra gul.

Indata

Utdata

3
3 5 1 -1
-2 0 0 4
4 4 0 6

14.233345
2 2
1 1
3 1

Problem id: flygigen

Bo Arding (se uppgift 3) har nu funderat lite till och insett att om man utökar antalet flighter kan man kanske klara sig undan med färre flygplan. Skriv ett program som beräknar hur många plan man behöver för att uppfylla samtliga flighter (ursprungliga och nya) om man får skapa godtyckligt många nya flighter mellan flygplatserna. Indata följer samma specifikationer och gränser som för uppgift 3. De nya flighterna får flygtider enligt "avståndstabellen".

6 7
0 150 50 110 45 120
145 0 180 90 60 80
50 160 0 40 38 45
110 90 37 0 50 20
47 60 40 52 0 65
120 80 40 20 60 0
1 2 170
6 5 400
5 4 470
2 6 318
4 3 520
3 6 700
2 1 25

2