Školsko natjecanje 2011. / Osnovna škola (6. razred) - 3. zadatak

Pčelac Medić ima samo jedan pokušaj da položi stručni pčelarski ispit. Polaganje ispita se odvija na poligonu koji ima \(10\) cvjetova (\(0\), \(1\), \(...\) , \(9\)), a čiji je nacrt Pčelac dobio prije ispita.

Na početku ispita Pčelac dobije vreću s \(50\) grama peluda. S tom torbom polijeće sa starta (cvijet oznake „\(0\)“), leti s cvijeta na cvijet, te treba doletjeti do cilja (cvijet oznake „\(9\)“) prateći i poštujući putokaze. Na svakom cvijetu (osim „\(0\)“ i „\(9\)“), Pčelac može dobiti još peluda kao nagradu ili mora ostaviti peluda kao preduvjet za nastavak puta. Ako u torbi ne bude imao dovoljno peluda za ostaviti na cvijetu, tada je odmah pao ispit. Svaki cvijet smije dotaknuti samo jednom.

Pčelac je položio ispit ako je došao do cilja i ako je količina peludi koju je imao u torbi bila najveća moguća koju je mogao sakupiti poštujući zadana pravila ispita.

Analizirajući poligon i zadane uvjete, Pčelac je otkrio da postoji samo jedna prava putanja kretanja koja će mu omogućiti da iz prve položi ispit. Napiši program koji ispisuje tu optimalnu putanju kretanja i maksimalnu količinu peludi koju će Pčelac Medić sakupiti na tom putu.

u primjerima vrijednima \(70\%\) bodova, Pčelac će uvijek imati dovoljno peluda u torbi;

Ulazni podaci

Osam cijelih brojeva \(C_i\) \((-50\leq C_i \leq 50, i=1..8)\), gdje je \(C_i\) količina peluda u gramima na cvijetu oznake i koju Pčelac može dobiti ili mora ostaviti. Pozitivan broj je količina peluda koju će dobiti, a negativan broj količina peluda koju mora ostaviti;

Izlazni podaci

• niz jednoznamenkastih brojeva odvojenih razmakom koji predstavljaju oznake cvjetova u poretku optimalne putanje iz uvjeta zadatka (start i cilj su uključeni u putanju);
• prirodan broj koji predstavlja maksimalnu količinu sakupljene peludi iz uvjeta zadatka.

Primjeri test podataka

Ulaz

22
1
-44
29
-12
-38
46
26

Izlaz

0 1 2 3 4 5 6 7 8 9
80

Objašnjenje

Ulaz

26
-20
-5
29
27
21
26
-19

Izlaz

0 1 2 3 4 5 6 7 8 9
135