Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 166. feladat (2022. december)

S. 166. Marika néni palacsintázójában egy ember süti és tölti a palacsintákat. Eddig, ha érkezett egy rendelés, akkor megsütötte a megfelelő számú palacsintát, majd beletöltötte a kért tölteléket, és odaadta a pénztárosnak, aki a fizetést elhanyagolható időn belül elintézte. Az utóbbi időben azonban nagyon népszerű lett a hely, ezért néha nagyon sokat kell várni. Hamar kiderült, hogy a sütés és palacsintatöltés közötti váltás sok időt vesz el. Azt szeretnénk kideríteni, hogy ez valóban probléma-e.

Írjunk programot, amely kiszámolja, mennyi a várakozási idők maximuma, ha minden rendelést külön-külön szolgálunk ki, illetve mennyi a várakozási idők maximumának lehető legkisebb értéke, ha pont jókor váltunk a sütés és töltés között.

Ezen a helyen nem szeretik a pazarlást, így csak akkor állnak neki egy palacsinta megsütésének, ha már van rá leadott rendelés. Tehát olyan nem fordulhat elő, hogy több megsütött palacsintánk van, mint a kiszolgálatlan rendelések összege.

A bemenet első sorában egy palacsinta megsütésének ideje S, egy palacsinta töltésének ideje \(\displaystyle T\), és a kettő közötti váltás ideje \(\displaystyle V\) szerepel. A második sorban a rendelések \(\displaystyle R\) száma van. A következő \(\displaystyle R\) sor mindegyikében két egész szám szerepel: az adott rendelés leadásának időpontja és a kért palacsinták száma.

A kimenet első sorába írjuk ki, mennyi a várakozási idők maximuma, ha a rendeléseket egyesével szolgáljuk ki, azaz mindig csak annyi palacsintát sütünk, amennyi a következő rendeléshez kell. A kimenet második sorába pedig azt, hogy mennyi a várakozási idők maximumának lehető legkisebb értéke.

Minta:

Bemenet (a / jel sortörést helyettesít) Kimenet (a / jel sortörést helyettesít)
2 1 1 / 2 / 0 5 / 2 1 19 / 18

Magyarázat (zárójelben a befejezési idő szerepel): az első esetben megsütünk 5-öt (10), majd megtöltjük (16), majd váltunk és sütünk még egyet (19), majd azt is megtöltjük (21). A várakozási idő csökkenthető, ha előbb megsütünk 5-öt (10), majd mivel van rá rendelés, még egyet (12), majd váltunk és megtöltjük az első ötöt (18), majd még egyet (19).

Korlátok: \(\displaystyle 1\le S,T,V \le 10^4\), \(\displaystyle R \le 10^5\). A rendelés ideje és a rendelések számának összege is legfeljebb \(\displaystyle 10^5\). Időlimit: 1 mp.

Értékelés: a pontok 20%-a kapható, ha a program által adott kimenet első sora helyes. További 40% kapható, ha a program helyes kimenetet ad az \(\displaystyle R\le 10\) és a palacsinták számának összege legfeljebb 20 esetekben.

Beküldendő egy s166.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

A beküldési határidő 2023. január 16-án LEJÁRT.


Statisztika:

Az S. 166. feladat értékelése még nem fejeződött be.


A KöMaL 2022. decemberi informatika feladatai