ŠIOM — Erdvėlaivis

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1998_3e2_erdvelaivis_vyr.in

Rezultatų failas: lmio_1998_3e2_erdvelaivis_vyr.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Erdvėlaivis

Erdvėlaivis turi nugabenti svarbų krovinį iš vienos bazės į kitą, tačiau skrydžiui ne visada užtenka kuro, kurį jis gali pasiimti kelionės pradžioje. Todėl jis skrenda pro tarpines bazes, jose papildydamas kuro atsargas. Įvairiose bazėse kuro atsargų papildymas kainuoja nevienodai, todėl turėdamas ribotą kreditą skirtą kurui erdvėlaivio vadas ne visada pasirenka trumpiausią kelią. Galioja šios sąlygos:

kuro papildymas bazėje kainuoja ﬁksuotą piniginių vienetų skaičių (nesvarbu kiek pilama kuro), todėl kuro bakas užpildomas pilnai;
erdvėlaivis skrieja pastoviu greičiu;
laikoma,kad bazėse erdvėlaivis užtrunka artimą nuliui laiko tarpą, todėl kelionės trukmė proporcinga nuskristam keliui.

Užduotis

Parašykite programą, kuri rastų tokį erdvėlaivio skridimo maršrutą, kad krovinys būtų pristatytas kiek galima greičiau.

Pradiniai duomenys

Pradiniai duomenys – pirmoje eilutėje įrašyti keturi sveikieji skaičiai:

erdvėlaivio kuro bako talpa $V$ , nurodyta kuro tūrio vienetais,
kuro sąnaudos $S$ vienam ilgio vienetui,
turimas kreditas $K$ , išreikštas piniginiais vienetais,
bazių, kuriose erdvėlaivis gali papildyti kuro atsargas, skaičius $N$ .

Likusiose $N$ eilučių įrašyta po keturis sveikuosius skaičius $k$ , $x$ , $y$ , $z$ , apibūdinančius atitinkamą kuro bazę:

$k$ – kuro bako užpildymo kaina bazėje, nurodyta piniginiais vienetais,
$(x,y,z)$ – bazės padėtis erdvėje, visos koordinatės nurodytos ilgio vienetais.

Erdvėlaivis turi nugabenti krovinį iš pirmos bazės į $N$ -ąją. Pradiniu momentu erdvėlaivio kuro bakas yra tuščias.

Rezultatai

Reikia įrašyti bazių, kuriose erdvėlaivis papildo kuro atsargas skrisdamas optimaliu maršrutu, numerius. Numeriai turi būti rašomi ta tvarka, kuria bazės aplankomos, po vieną numerį į eilutę.

Į paskutiniąją eilutę įrašykite $N$ -osios bazės numerį.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
10 1 10 4 5 0 0 0 15 10 0 0 5 5 5 0 1 10 2 0	1 3 4

Ribojimai

$1\\leqV\\leq100$

$1\\leqS\\leq100$

$1\\leqK\\leq100$

$2\\leqN\\leq100$

$0\\leqk\\leq100$