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
//
//
//
//
//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
//
//
//
//