Programmeringsolympiaden 2009: Onlinekvalet

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

Uppgift 1 - Chokladkartongen
Uppgift 2 - Biblioteket
Uppgift 3 - Bygga med klossar
Uppgift 4 - Digital Signal Processor
Uppgift 5 - Entropiberäkning
Uppgift 6 - Jan Ersa och Per Persa

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: chokladkartongen

Bosse tycker om choklad. Han har därför alltid en öppnad chokladkartong i skafferiet. När den tar slut köper han i hemlighet en ny och låtsas som ingenting. Bosses fru, som är misstänksam av naturen, förundras över att den där kartongen aldrig tar slut. Därför börjar hon då och då räkna antalet chokladbitar som är kvar. Skriv ett program som, givet hennes observationer, beräknar det minsta antalet nya kartonger Bosse kan ha köpt under perioden.

Indata

På första raden står ett heltal N ≤ 100, antal observationer. Därefter följer en rad med N heltal, antalet chokladbitar i asken (mellan 1 och 100) vid varje observation, i den ordning de görs.

Utdata

Programmet ska skriva ut en rad med ett heltal: det minsta antal nya kartonger Bosse bevisligen måste ha köpt under perioden.

10
17 15 16 16 18 17 14 12 13 9

3

Problem id: biblioteket

Du jobbar på ett bibliotek och vill ställa tillbaka ett antal böcker i hyllorna. Hyllorna är placerade längs x-axeln. Givet i vilken hylla varje bok ska stå (en x-koordinat mellan -1000 och 1000) och det maximala antalet böcker som du kan bära samtidigt, bestäm den kortaste sträckan du måste gå för att ställa tillbaka alla böcker. Böckerna som ska ställas tillbaka befinner sig ursprungligen på position 0. Du behöver inte gå tillbaka efter att ha återställt den sista boken.

Indata

På första raden står två heltal: antalet böcker som ska ställas tillbaka N, där 1 ≤ N ≤ 100, och antalet böcker du kan bära samtidigt K, där 1 ≤ K ≤ 100. Sedan följer N rader med ett heltal på varje rad, x-koordinaten för den hylla där varje bok ska stå.

Utdata

Programmet ska skriva ut en rad med ett heltal: den minimala sträckan du måste gå för att sätta tillbaka alla böckerna.

4 2
3
1
4
-4

14

Problem id: klossar

När Henning bygger med klossar lägger han en kloss i taget, antingen ovanpå en av de tidigare lagda klossarna eller direkt på golvet, alltså aldrig så att den vilar direkt på mer än en kloss. Han har tänkt ut precis hur han ska lägga varje kloss för att det ska bli fint. Eftersom han ännu inte fyllt två år har han dock inte mekanikens lagar helt klart för sig, så ofta rasar tornet innan han är färdig. Du ska skriva ett program som tar emot information om storleken på varje kloss och var Henning tänker lägga den, och som beräknar hur många klossar han kan lägga innan byggnationen rasar.

Vi tänker oss problemet i två dimensioner (se figur ovan). Varje kloss beskrivs då med en bredd B och en höjd H. Dessutom anges positionen för klossens centrum (i x-led) C enligt Hennings planer. För enkelhets skull får programmet också veta vilken kloss den aktuella klossen vilar på (eller om den vilar direkt på golvet). Man kan förutsätta att utsträckningen av den aktuella klossen och den kloss den vilar på sammanfaller i åtminstone något intervall. Ifall den sammanlagda tyngdpunkten skulle hamna exakt på hörnet av den underliggande klossen kan du räkna det som ett ras eller inte (det spelar ingen roll för resultatet i givna testdata).

Byggnationen rasar om det någonstans finns en kloss som, tillsammans med alla ovanpåliggande klossar, har en tyngdpunkt vars x-koordinat ligger utanför den kloss den vilar på. Den gemensamma tyngdpunktens x-koordinat för ett antal godtyckliga klossar 1,2,3...k kan beräknas genom formeln:

Indata

På första raden står ett heltal N, 1 ≤N ≤1000, antalet klossar. Sedan följer N rader med fyra tal på varje rad som beskriver varje kloss i den ordning de ska läggas. Det första talet är ett heltal som anger ordningstalet på den kloss som den aktuella klossen ska vila på (numrerade 1, 2, 3....), eller 0 om den ska vila direkt på golvet (som är oändligt stort). De följande tre talen anger bredden B, höjden H samt centrumet C för den aktuella klossen, dessa är alla heltal mellan 0 och 100.

Utdata

Programmet ska skriva ut en rad med ett heltal: antalet klossar Henning kan lägga ut innan det sker ett ras någonstans. Om det sker ett ras när den tredje klossen läggs ska programmet alltså skriva ut 2, medan om han lyckas lägga alla klossarna utan ras så ska talet N skrivas ut.

10
0 26 8 28 
1 31 3 40
2 20 9 27
2 6 7 52 
0 15 4 57
3 8 2 18
5 6 8 64
4 30 3 54 
8 10 9 56
3 10 12 29

8

Problem id: dsp

Anna-Maria tänker bygga ett vindkraftverk, och har uppfunnit en ny sorts processor som hon tänker använda som komponent i vindkraftverkets styrsystem. Processorn är en s.k. DSP, Digital Signal Processor, som bearbetar digitala signaler. I praktiken innebär detta att DSP:n matas med en serie heltal som indata, bearbetar dessa enligt den mjukvara som är inprogrammerad, och producerar en serie heltal som utdata.

Anna-Maria har skickat en beställning till en fabrik som ska producera DSP:n åt henne, men på grund av den ekonomiska krisen drar produktionen ut på tiden. Anna-Maria, som redan har skrivit massor av program till sin DSP, blir lite otålig och vill försäkra sig om att hennes program verkligen kommer fungera på en gång när DSP:erna är klara. Hon ber dig därför skriva ett program som simulerar DSP:ns beteende, så hon kan testa sina program innan DSP:n finns tillgänglig.

Mjukvaran som definierar DSP:ns beteende består av en sekvens av N (upp till 256) maskininstruktioner (även kallade assemblerinstruktioner), numrerade från 0 till N-1. Det finns 7 sorters instruktioner: CONST, ADD, SUB, JNZ, INPUT, OUTPUT och HALT. Varje instruktion har 0-2 parametrar, som var och en är ett heltal 0..255. DSP:n har också ett arbetsminne som består av 256 st register, vart och ett av dessa innehåller en byte (dvs, ett heltal 0..255).

Ett program körs genom att DSP:n börjar exekvera instruktion 0, sedan instruktion 1, o.s.v., tills en HALT-instruktion exekveras, då avslutas programmets körning. När körningen börjar har alla register värdet 0.

Maskininstruktionerna definieras på följande vis:

CONST x y	Sätt register nr y till värdet x. ([y] = x)
ADD x y	Addera värdet i register nr x till register nr y. ([y] = [y] + [x])
SUB x y	Subtrahera värdet i register nr x från värdet i register nr y. ([y] = [y] - [x])
JNZ x y	Jump if Not Zero: Om register nr x inte är 0, "hoppa" till instruktion nr y, dvs låt instruktion y bli nästa instruktion att exekvera. Om register nr x däremot är 0, fortsätt exekveringen som vanligt med instruktionen efter JNZ.
INPUT x	Läs in nästa byte från DSP:ns indata, lagra den i register nr x.
OUTPUT x	Skicka innehållet i register nr x som utdata från DSP:n.
HALT	Avsluta körningen.

Indata

Indata består av programmet som ska köras på DSP:n, följt av det indata som DSP:n kommer matas med.

På första raden står ett heltal N, 0<N<256, antalet maskininstruktioner i programmet. Därpå följer N rader med instruktioner. Varje instruktion består av instruktionens namn, följt av instruktionens parametrar. Varje parameter beskrivs av ett heltal i intervallet 0..255. Efter de N raderna med maskininstruktioner, följer ett antal tal i intervallet 0..255, ett tal på varje rad. Talen utgör indata till DSP:n, dvs den talserie som DSP-programmets INPUT-instruktioner läser från.

Du kan förutsätta att DSP-programmet och dess indata uppfyller följande:

Utdata

Ditt program ska simulera DSP:ns körning av det program som ges av uppgiftens indata, och skriva ut DSP:ns utdata: För varje exekvering av en OUTPUT-instruktion, ska ditt program skriva ut en rad med ett heltal i intervallet 0..255, utdatat som skickas från OUTPUT-instruktionen.

15
INPUT 4
JNZ 4 3
HALT
INPUT 0
INPUT 1
CONST 0 2
JNZ 0 11
OUTPUT 2
CONST 1 0
SUB 0 4
JNZ 0 1
ADD 1 2
CONST 1 3
SUB 3 0
JNZ 3 6
5
1
1
2
2
3
3
4
4
5
6

1
4
9
16
30

Problem id: entropi

I statistisk termodynamik är man ofta intresserad av på hur många olika sätt, W, energin i ett system kan vara fördelat på de ingående partiklarna. Logaritmen av detta tal (multiplicerad med en konstant) kallas för entropi (oordning).

Vi tänker oss nu ett enkelt system bestående av N molekyler, som vardera har en viss energi. Genom kvantmekanikens lagar är energin "kvantiserad", så att energin för varje molekyl bara kan vara ett heltal 0, 1, 2, 3 o.s.v. (ingen begränsning uppåt). Den totala energin E, alltså summan av molekylernas energier, är given. Skriv ett program som beräknar på hur många sätt denna energi kan vara fördelad på de N molekylerna.

Indata

En rad med två heltal N och E, där 1 ≤ N ≤ 17 och 1 ≤ E ≤ 17

Utdata

4 6

84

Problem id: janersa

Så här börjar en dikt av Gustaf Fröding:
Jan Ersa ägde Nackabyn,
Per Persa ägde Backabyn
i By i Västra Ed.
Jan Ersa,
Per Persa,
de höllo aldrig fred.

När Jan Ersa och Per Persa, på äldre dagar, flyttade in till staden såg de till att de hamnade så långt från varandra som möjligt. Skriv ett program som läser in information om gatorna i staden och som sedan bestämmer mellan vilka två hus den kortaste vägen är som längst, samt längden av denna väg.

Indata

På första raden står ett tal N, 2 ≤ N ≤ 100, som anger antalet hus i staden. Husen är numrerade från 1 till N. På nästa rad återfinns ett tal som anger antalet gator V, 2  ≤ V ≤ 500. Därefter följer V rader med tre tal på varje rad: från hus nummer, till hus nummer och gatans längd (givet i 100-tals meter). I givna indata går det alltid att ta sig från vilket hus som helst till vilket annat hus som helst.

Utdata

Programmet ska skriva ut en rad med tre tal åtskilda av blanksteg: Numren på de två husen längst ifrån varandra (det lägsta numret först) samt avståndet i meter. Om det finns flera par av städer som ligger på detta avstånd kan du ange vilket som helst av dem.

15
27
1 12 10 
1 2 9 
2 12 9 
6 12 9 
3 6 9 
2 3 8 
3 12 10 
3 4 8 
4 13 6 
5 13 11 
5 6 8 
4 6 11 
4 5 15 
6 7 12 
7 8 8 
8 11 6 
9 11 11 
9 10 8 
7 10 10 
10 11 14 
8 15 11 
5 15 9 
5 7 13 
5 8 12 
5 14 12 
13 14 16
14 15 8 

1 9 4900