[ Colex @ 22.02.2007. 10:55 ] @
Code: //Japanska buba uletjela je u špilju punu prepreka: stalagmita (stoje na podu špilje) i stalaktita (vise sa stropa špilje). //Špilja je duljine N (gdje je N paran broj) i visine H. Prva prepreka je stalagmit a zatim se izmjenjuju stalaktiti i stalagmiti. //Na slici je primjer jedne špilje duljine 14 i visine 5 (slika odgovara drugom primjeru test podataka): // | | | | | | | // | | | | | | | | // | | | | | | | | | | | | // | | | | | | | | // | | | | | | | //Japanskoj bubi se ne da izbjegavati prepreke, nego ona odabere jednu od H razina i zaleti se s jednog kraja špilje na drugi, te sa svojim kung fu vještinama poruši sve prepreke na putu. //Na primjer, ako u špilji sa prethodne slike odabere četvrtu razinu od poda, onda ce porusiti ukupno osam prepreka: // | | | | | | | // | | | | | | | | // | | | | | | | | | | | | // | | | | | | | | // | | | | | | | //U ovom primjeru manje ce se umoriti ako odabere prvu ili petu razinu, jer ce u ta dva slučaja porušiti samo sedam prepreka. //Zadane su dimenzije špilje i duljine svih prepreka. napišite program koji određuje koliko NAJMANJE PREPREKA buba mora porušiti da bi prošla na drugu stranu, te na koliko različitih razina se postiže ta najmanja vrijednost. //ULAZNI PODACI: //U prvom redu ulaza nalaze se prirodni brojevi N i H, 2 =< N =< 200 000, 2 =< H =< 500000, dimenzije špilje. N će biti paran. //Slijedećih N redova sadrži redom duljine svih prepreka, prirodne brojeve manje od H. //U prvi i jedini red ispišite dva cijela broja odvojena jednim razmakom, najmanji broj prepreka koji buba mora porušiti te na koliko različitih razina se postiže ta najmanja vrijednost. // ULAZ: ULAZ: // 6 7 14 5 // 1 1 // 5 3 // 3 4 // 3 2 // 5 2 // 1 4 // 3 // IZLAZ: 4 // 2 3 3 /// 3 // 3 // 2 /// 3 // 3 // /// IZLAZ: // // 7 2 // // // // |