Programmeringsolympiaden 2012: Onlinekvalet

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

Uppgift 1 - Sjusovarefull indata
Uppgift 2 - Spellistanfull indata
Uppgift 3 - Flygbolagetöppen indata
Uppgift 4 - Börsenöppen indata
Uppgift 5 - Pokeröppen indata
Uppgift 6 - Tivoliöppen indata
Uppgift 7 - Flygbolaget igenöppen indata

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:

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




Uppgift 1 - Sjusovare

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

Först kommer antalet personer, n, därefter följer n rader med fyra heltal på, de beskriver tills när en person sover. Raden har formatet hh mm st sn, det betyder att alarmet är inställt på hh:mm, därefter kommer personen snooza sn gånger, varje snooze är på st minuter. Ingen person kommer sova till tolv. Det kommer finnas max 100 personer varav minst en kommer vara sjusovare.

Utdata

En rad med heltal, indexen på personerna som blev sjusovare, i stigande ordning. Första personen i indata har index 1 o.s.v.

Exempel: Indata

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

Exempel: Utdata

1 2 4



Uppgift 2 - Spellistan

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 x0 och en modulator M och beräknar sedan fram resterande tal med följande formel:

xn+1 = xn2 mod M

Du låter nu talet xi 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 xi gånger (efter den sista kommer du tillbaka till den första o.s.v.). Observera att det är x1 som avgör vilken den första låten blir.

Antaget att du vet vilka m låtar du kommer ogilla i förväg, skriv ett program som tar reda på i vilken ordning dessa kommer tas bort från spellistan samt hur många låtar du hinner lyssna på tills spellistan är färdig.

Indata

Indata består av tre rader. På första raden står de två heltalen x0 och M, som beskriver slumpalgoritmen (0 ≤ x0 < M ≤ 100000). På andra raden står de två heltalen n och m, antalet låtar totalt och antalet låtar som ska tas bort (0  ≤  m  <  n  ≤  100). På den tredje raden står m unika heltal mellan 1 och n, numren på de låtar som du inte gillar.

Utdata

Utdatan ska bestå av 2 rader. Den första ska innehålla alla m låtnumrena i den ordning de togs bort, och den sista raden ska innehålla det totala antalet låtar du har lyssnat på när den sista låten tagits bort. I samtliga testfall kommer detta antal vara under 10000.

Exempel: Indata

3 19 
4 3
1 4 3

Exempel: Utdata

3 4 1
5

Exempel: Förklaring

Slumpalgoritmen ger talen 9, 5, 6, 17, 4, 16, 9... Vidare har vi 4 låtar varav vi ogillar 3. Notera att vi har hunnit lyssna på den omtyckta låten 2 gånger innan den sista dåliga låten elimineras och vi är klara (vi lyssnade på låtarna i ordningen 2, 2, 3, 4, 1).



Uppgift 3 - Flygbolaget

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 (Dij) 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. Dij + Djk ≥ Dik. 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.

Exempel: Indata

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

Exempel: Utdata

3



Uppgift 4 - Börsen

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

På första raden står ett heltal N (2 ≤ N ≤ 100000), antalet dagar. På andra raden står ett flyttal Q (0 ≤ Q ≤ 100), avgiften i kronor per transaktion. Därefter följer N rader med vardera ett flyttal, aktiekursen för dag 1, dag 2, o.s.v., t.o.m. dag N. Kursen ligger alltid mellan 1 och 1000 kr per aktie.

Utdata

En rad med ett flyttal X som anger hur mycket kontanter (inte aktier) Evelina maximalt kan ha efter N dagar. Svaret kan anges med godtyckligt antal decimaler, men ska ha ett relativt fel (felet dividerat med det rätta svaret) som är mindre än 10-5. Observera att hon inte är tvungen att handla några aktier (alltså gäller X ≥ 100). I samtliga testfall kommer X vara under en miljon.

Exempel: Indata

6 
2.3
75.6
86.2
83.1
91.3
72.5
95.7

Exempel: Utdata

147.3742

Exempel: Förklaring

Dag 1 köper hon 1.29233 aktier för alla sina pengar. Dag 4 säljer hon alltihop och får tillbaka 115.689 kr. Dag 5 köper hon på nytt aktier för alla sina pengar och får 1.56399 stycken, som hon slutligen säljer dag 6.




Uppgift 5 - Poker

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

52 rader med en bokstav och ett tal på varje rad, separerade med blanksteg. Varje rad beskriver ett kort. Bokstaven kan vara R, S, H eller K och anger kortets färg, medan talet ligger i intervallet 1 till 13 och anger kortets valör. De fem första raderna beskriver de fem korten Kurt har i sin starthand. De återstående raderna beskriver övriga kort i den ordning de ligger i kortleken. Den sjätte raden beskriver alltså det första kortet han kan byta till sig o.s.v. Varje möjligt kort återfinns exakt en gång.

Utdata

En rad med 8 heltal, antalet bytesomgångar som behövs för att uppnå var och en av de åtta handtyperna i listan ovan (i denna ordning). Talet 0 betyder att starthanden redan är av denna handtyp.

Exempel: Indata

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

Exempel: Utdata

0 1 2 4 3 3 7 11 

Exempel: Förklaring

Kurt har redan par i 10:or. För att få två par byter han 1:an och 8:an och får en 4:a och en andra 3:a. För att få triss slänger han däremot sitt par och samlar bara på 3:or. Och så vidare...




Uppgift 6 - Tivoli

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

Första raden består av heltalet N, antalet attraktioner Lisa vill åka (1 ≤ N ≤ 15). Därefter följer N rader, där den första raden beskriver attraktion nummer 1, den andra raden attraktion nummer 2 o.s.v. Varje rad innehåller fyra heltal: x- och y-koordinat för den första anläggningen av denna attraktion, samt x- och y-koordinat för den andra anläggningen av denna attraktion. Koordinaternas absolutbelopp understiger en miljon.

Utdata

Utdatan ska först bestå av flyttalet hur långt Lisa måste gå, och därefter N rader med två heltal som, varav det första inom 1..N som säger vilken attraktion hon ska gå till och det andra inom 1..2 vilken av anläggningarna. Det första av dessa N rader säger alltså vilken anläggning som hon först går till och den sista raden vilken anläggning hon sist går till. Om det finns flera vägar som ger lika kort sträcka (det finns ju åtminstone alltid två håll att gå) kan du ange vilken som helst av dem. Notera även att det första flyttalet som skrivs ut ska ta till hänsyn även att Lisa måste börja och sluta vid entrén. Det relativa felet ska understiga 10-5.

Exempel: Indata

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

Exempel: Utdata

14.233345
2 2
1 1
3 1



Uppgift 7 - Flygbolaget igen

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".

Exempel: Indata

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

Exempel: Utdata

2

Exempel: Förklaring

Bo kan exempelvis lägga ut en ny flight från flygplats 2 till flygplats 4 med avgångstid när som helst mellan 320 och 430. Då behöver han endast två flygplan medan det krävdes tre med de ursprungliga flighterna (se uppgift 3).