Pera ima gajbica poređanih u nizu, u kojima se nalaze jabuke. U -toj gajbici se nalazi jabuka. Pera ne voli kada mu se u neke dve uzastopne gajbice nalazi u zbiru više od jabuka, i zbog toga će on baciti neke jabuke iz nekih gajbica.
Koliko najmanje jabuka Pera može da baci, tako da se u svake dve uzastopne gajbice nalazi najviše jabuka?
Opis ulaza
U prvoj liniji standardnog ulaza nalaze se dva broja odvojena razmakom i . U drugoj liniji standardnog ulaza nalazi se brojeva odvojenih razmakom, koje predstavljaju niz , odnosno broj jabuka redom u gajbicama.
Opis izlaza
U prvoj i jedinoj liniji standardnog izlaza ispisati minimalni broj jabuka koje Pera može da baci da bi ispunio uslov iz zadatka.
Primer
Standardni ulaz | Standardni izlaz | |
---|---|---|
3 4 3 3 2 |
2 | |
5 10 6 7 8 9 5 |
10 |
Objašnjenje test primera
U prvom test primeru prva i druga gajbica imaju u zbiru 6 jabuka, dok druga i treća imaju u zbiru 5 jabuka, što je veće od 4 koliko je dozvoljeno. Ukoliko iz druge gajbice izvadimo 2 jabuke ostaće nam {3, 1, 2}, pa će u prve dve uzastopne zbir biti 4, a u druge dve 3, što nije veće od 4.
U drugom test primeru možemo u svakoj gajbici ostaviti po tačno 5 jabuka, iz prve ćemo izbaciti 1, iz druge 2, iz treće 3 i iz četvrte 4 jabuke, što je u zbiru 10 jabuka. Ne može se postići željeni uslov izbacivanjem manje od 10 jabuka.
Ograničenja i podzadaci
()
()
Comments