Kezdőlap


Feladat:	I.451	Korcsoport: -	Nehézségi fok: -
Füzet:	2018/március, 164 - 165. oldal		PDF \| MathML
Témakör(ök):	Feladat, Programozás, algoritmusok

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Kukac-robot egy számsoron szeretne végighaladni, végigkúszni. A robot onnan kapta a nevét, hogy mozgása a kukacokéra emlékeztet. A kúszás két fázisból áll: először összehúzza magát úgy, hogy testének első része helyben marad a számsoron és a végét előre húzza, amíg csak lehet; majd másodszor fordítva, testének utolsó pontja marad egy helyben és előre kinyúlik, amíg a szabályok engedik.
Szabályok:

‐	Összehúzott állapotban a Kukac-robot alatt lévő számok összege legalább $K$ , és a lefedett számok száma kettőnél nem lehet kevesebb.

‐	Kinyújtott állapotban legfeljebb $L$ lehet az alatta levő számok összege és nem nyúlhat öt számnál hosszabban.

‐	A Kukac-robot induló helyzete: az első két számon helyezkedik el összehúzott állapotban. (A kezdőállapotra a szabályokat nem kell vizsgálni.)

‐	Beérkezésnek számít az a kinyújtott állapot, amikor a számsor utolsó tagját lefedi.

Készítsünk programot i451 néven, amely meghatározza, hogy Kukac-robot végig tud-e menni a számsoron és ha igen, akkor legkevesebb hány lépésben.
A program standard bemenetének első sorában 3 szám van:

N

(

10 \leq N \leq 10 000

) a számsor hossza,

K

(

2 \leq K \leq 20

) összehúzott állapotban a Kukac-robot alatti és

L

(

K < L \leq 45

) a kinyújtott állapot alatti számok összege. Az ezt követő sorban a számsor tagjait adjuk meg szóközzel elválasztva, azaz

N

darab számot

x_{i}

(

0 \leq x_{i} \leq 9)

.
A program írja ki a standard kimenetre, hogy legkevesebb hány megnyúlás alatt kúszik át a Kukac-robot a számsoron. Ha nem tud a számsoron végigkúszni, akkor a kimenet legyen -1.

\begin{matrix} Példa a bemenetre & Kimenet \\ 12 10 30 & 5 \\ 6 7 8 0 4 9 9 8 9 1 1 8 \\ 10 9 17 & -1 \\ 2 8 0 2 2 4 8 8 2 1 \end{matrix}

Beküldendő egy tömörített i451.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.