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:

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




Uppgift 1 - Chokladkartongen

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.

Exempel: Indata

10
17 15 16 16 18 17 14 12 13 9

Exempel: Utdata

3



Uppgift 2 - Biblioteket

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.

Exempel: Indata

4 2
3
1
4
-4

Exempel: Utdata

14

Exempel: Förklaring

Du kan exempelvis börja med att ta med dig böckerna som ska till hylla 3 och 4. Därefter hämtar du boken som ska till hylla 1 och slutligen tar du boken som ska till hylla -4.




Uppgift 3 - Bygga med klossar

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.

Klossarnas placering i exemplet. När Henning lägger dit kloss 9 så tippar kloss 2 över kanten på kloss 1 (den gemensamma tyngdpunkten för klossarna 2, 3, 4, 6, 8 och 9 har x-koordinat 41.002 och hamnar därför utanför hörnet på kloss 1 som har x-koordinat 41.000). Observera att klossarna alltid läggs en i taget. Det hjälper alltså inte att kloss 10 skulle kunna stabilisera byggnationen igen.

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.

Exempel: Indata

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

Exempel: Utdata

8



Uppgift 4 - Digital Signal Processor

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:

  • Ingen ADD-instruktion kommer ge en summa större än 255, och ingen SUB-instruktion kommer ge ett tal mindre än 0 som resultat.
  • Programmet kommer alltid att avslutas korrekt genom att komma fram till en HALT-instruktion. Dvs, programmet kommer inte fastna i en evig loop.
  • Antalet instruktioner som behöver exekveras kommer inte att överstiga en miljon.
  • Det kommer alltid finnas tillräckligt med indata för att räcka till alla INPUT-instruktioner som behöver exekveras.
  • Programmet kommer aldrig försöka exekvera andra instruktioner än nr 0..N-1. Dvs, JNZ kommer aldrig att hoppa till en instruktion >= N, och instruktion nr N-1 kommer alltid antingen vara en HALT-instruktion, eller en JNZ-instruktion som hoppar till en tidigare instruktion.
  • 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.

    Exempel: Indata

    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
    

    Exempel: Utdata

    1
    4
    9
    16
    30
    

    Exempel: Förklaring

    Programmet tar ett tal M följt av M par av tal som indata, och skriver ut, för varje par, produkten av de två talen.




    Uppgift 5 - Entropiberäkning

    Problem id: entropi

    T.v. Ludwig Boltzmann's gravsten. T.h. De 6 sätten att fördela energin om N=3 och E=2. Siffran inuti varje "molekyl" anger hur stor energi den har.

    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

    En rad med ett heltal W, antalet sätt denna energi kan vara fördelad på de N molekylerna.

    Exempel: Indata

    4 6
    

    Exempel: Utdata

    84
    



    Uppgift 6 - Jan Ersa och Per Persa

    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.

    Kartan visar stadens alla hus och gator i exemplet. Vi ser också de röda husen där Jan Ersa och Per Persa numera bor. Dessa två hus (nr 1 och 9) är de hus i staden som ligger längst ifrån varandra (4900 meter).

    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.

    Exempel: Indata

    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 
    

    Exempel: Utdata

    1 9 4900