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. Egy elektromos terepjáró autóval szeretnénk eljutni egy dimbes-dombos területen az egyik helyről a másikra. A területet gondolatban egyforma négyzetre osztjuk, és minden egyes négyzethez egy magassági adatot rendelünk. A négyzetek számozása a bal felső saroktól indul jobbra, illetve lefelé. Az autó útját úgy modellezzük, mintha egy-egy oldalukkal egymással érintkező négyzeteken haladna keresztül. Az egyik négyzetről a másikra történő mozgáskor az autó 1 egységnyit meríti az akkumulátorát, ha a két négyzet azonos magasságban van. Alacsonyabb magasságban lévő négyzetről magasabban lévő négyzetre mozgáskor a szintkülönbség kétszerese plusz 1 egységnyit merül az akkumulátor. Amikor az autó lefelé halad, akkor a szintkülönbség számértékének megfelelő egységnyit töltődik az akkumulátor, miközben 1 egységet merül. Az autó indulási pontja a térkép négyzete, a cél a térkép négyzete. Kérdés, hogy legkevesebb hány egységnyi töltéssel kell rendelkeznie az autónak a kiindulási négyzetben, hogy eljusson a cél négyzetbe úgy, hogy közben egyszer sem kell külső energiával tölteni, csupán a szintkülönbség csökkenésekor kap energiát. Az autó nem tud továbbmenni, ha egy négyzetbe érve nem pozitív az energiája, ezért az csak a cél négyzetben lehet 0. A feladatot megoldó program olvassa be a standard bemenetről a térképhez tartozó és értékét, majd a következő sor mindegyikében pozitív egész számot, melyek a térkép -edik sorában és -edik oszlopában lévő négyzet szintértékét adják, illetve a következő sorban az induló és cél négyzetek adatait: , , , . A program írja a szabványos kimenetre a legkisebb akkumulátor töltöttséget, amellyel az autó a kiindulási helyről a célba érhet. Példa:
Korlátok: , . Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak kisebb és értékek esetén ad helyes eredményt 1 másodpercen belül. Beküldendő egy is20.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja. |