Histogram

Histogram je grafički prikaz statističke distribucije — funkcije koja svakom cijelom broju j između 1 i n pridružuje određenu vrijednost hj. Histogram crtamo tako da za svaki broj j nacrtamo stupac širine 1 i visine hj te sve takve stupce uredno posložimo na x-os slijeva nadesno počevši od ishodišta.

Slika 1: Histogram iz prvog primjera test podataka te sva tri moguća pravokutnika.

Zadan je histogram i prirodan broj p, odredite broj različitih pravokutnika R za koje vrijedi: vrhovi od R su točke s cjelobrojnim koordinatama, jedna stranica od R leži na x-osi, unutrašnjost od R je potpuno pokrivena histogramom i površina od R je barem p.

U prvom redu nalaze se prirodni brojevi n i p — širina histograma i najmanja dozvoljena površina pravokutnika. U sljedećem redu nalazi se n prirodnih brojeva h1, h2, . . . , hn — vrijednosti distribucije predstavljene histogramom.

Ispišite traženi broj pravokutnika.