 |
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:
2 dolgozat érkezett. 9 pontot kapott: Horváth Milán. 2 pontot kapott: 1 versenyző.
A KöMaL 2022. decemberi informatika feladatai