Mi lehet a megoldása a szöveges feladatnak?

Van.

Például, ha akármelyiknek odaadjuk az összeset. Feltéve, hogy az autó tankjába belefér.

De ha az autó tankja nagyon kicsi, kisebb mint a Balaton-kerület/K úthoz szükséges mennyiség, akkor viszont nincs megoldás.

A "bármilyen elrendezés" néha ugyanazt az eredményt adja, mint amit az 1-esben leírtam. Pl. az első kijelentésnél, ha minden benzinkút ugyanott van. A másodiknál, ha egyenletesen vannak elosztva és mindegyik ugyanannyi benzint kap.

Más szempontból is furcsa ez a feladat, mert a tank kapacitása nincs benne megemlítve, pedig az a kritikus. Ha az egész útra való benzin belefér a tankba, akkor akárhonnan indulhatunk. Ha meg nem fér bele, akkor mindenképpen van olyan elrendezés aminél nem tudunk körbeérni.

Inkább az lehetne valós kérdés, hogy mik azok tankkapacitások és benzin elhelyezési elrendezések, ahol számít, hogy honnan indulunk. De a feladat nem ezt kérdezi.

"Ha az egész útra való benzin belefér a tankba, akkor akárhonnan indulhatunk."

Mondjuk ez tényleg nem igaz. Ha valamerre elindulunk akkor az előzőleg összegyüjthető benzinnek minden benzinkútnál többnek kell lenni, mint az addig megteendő út.

Lassan eljutok oda, hogy felfogjam a feladatot. :-)

A tank nagy. Van egy kút és benzin elhelyezés.

Létezik-e olyan algoritmus, amivel ki tudjuk választani, hogy melyik kúttól, melyik irányba induljunk, ahhoz hogy körbeérjünk? Mondhatjuk-e, hogy ez az algoritmus mindig sikeres?

Nem hiszem, hogy létezik olyan autó, ami egy Balaton kört nem tesz meg egy tank benzinnel. :D Nyilván ezért nem is említi a feladat.

Arról van szó csak amit a #4-ben írtál.

Akkor az algoritmus:

Alakítsuk át az egészet egy hullámvasúttá, úgy hogy minden benzinkút legyen egy magassági pont. Mondjuk, az óramutató járásának megfelelően járunk körbe. Felvesszük valamilyen magasságba bármelyik kutat. Az lesz az első. Tegyük fel, hogy ennek a benzinje elég ahhoz, hogy eljussunk a másodikig és még marad x liter. Akkor a második kutat x méterrel lejjebb rajzoljuk. Ha hiányzik x liter a távolsághoz, akkor feljebb.

Ugyanígy megnézzük, hogy a második kút készletéből indulva, marad -e a benzinből y liter, ha elérjük a harmadikat. (Nem használjuk az első kút készletéből megmaradt benzint.) A harmadik kutat a másodiknál előjeles y méterrel lejjebb rajzoljuk.

És így kialakul egy hullámvasút, amelyik az egyes kútnál zárulni fog. Mert a benzin pont elegendő a teljes útra. A hullámvasút legmagasabb kútjától indulva lendületből körbe tudunk menni a pályán.

Ha az ellenkező irányba végezzük a felmérést, akkor egy másik hullámvasutat kapunk. De ott is lesz egy vagy több legmagasabb pont.