Savezno 2004. Ideje za neke zadatke ...zadatak koji mene najvishe zanima je sledeci :
Citat:
Zadatak 3. Terorista
Najveća zgrada u svetskoj prestionici Beonisu ima N spratova. Na svakom spratu se nalazi bazen. Terorista Joca želi da sruši zgradu, tako što će porušiti prvi sprat a samim tim i celu zgradu. Za svaki sprat su poznate sledeće informacije:
Wi – težina vode koja se nalazi u bazenu na i-tom spratu na početku
Li – najveća težina vode koju i -ti sprat može da izdrži
Ci – cena dinamita potrebnog da se poruši i-ti sprat
Sva voda iz srušenog sprata odlazi na sledeći niži. Ako težina vode na nekom spratu postane veća od dozvoljene koju može da izdrži, pod se ruši i sva voda prelazi nadole.
Vaš zadatak je da pomognete teroristi Joci da sa što manje novca sruši prvi sprat.
Ulaz: U prvom redu ulaza je prirodan broj N (1≤N≤100000), koji predstavlja broj spratova. U svakom od sledećih N redova nalaze se po tri cela broja Wi, Li, Ci (0≤Wi≤Li<2x109, 0<Ci<2x109), veličine naznačene u tekstu zadatka za i-ti sprat.
Izlaz: Na standardni izlaz ispisati minimalnu količinu novca potrebnu da se banka potopi. Zatim u sledećih nekoliko redova upisati redne brojeve spratova koje treba srušiti za minimalno rešenje, u redosledu rušenja.
Primer:
Ulaz:-----------------------------------------Izlaz:
4---------------------------------------------5
10 50 100-------------------------------------3
0 100 3---------------------------------------2
100 100 2
10 50 6
Objašnjenje: Terorista ruši treći, pa drugi sprat sa minimalnom cenom 5. Drugi sprat se ne ruši sam, jer je težina vode nakon eksplozije jednaka trećini izdržljivosti. Kada bi se rušio samo prvi sprat cena bi bila 100, a kada bi se rušio četvrti cena bi bila 6.
Mene ovo najvishe asocira na dinamichko programiranje, ali nikako ne mogu
da provalim formulu...
Inache, zanimaju me ideje josh i za 4. i 5. zadatak.
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
e, nije sex nego serem!
Re: Savezno 2004. Ideje za neke zadatke ...