Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Taulukko

Taulukko


View task | Model solution | Statistics


Taulukko

Time limit:1.00 s
Memory limit:128 MB

Annettuna on syklinen taulukko, jossa on $n$ lukua. Syklisyys tarkoittaa, että kohdassa $n$ olevan luvun jälkeen tulee taas kohdassa $1$ oleva luku.

Tehtäväsi on jakaa taulukko yhtenäisiin väleihin niin, että jokaisen välin lukujen summa on enintään $k$. Mikä on pienin mahdollinen välien määrä?

Syöte

Syötteen ensimmäisellä rivillä on luvut $n$ ja $k$.

Syötteen toinen rivi sisältää $n$ lukua $x_1,x_2,\ldots,x_n$: taulukon sisältö.

Mikään taulukon luku ei ole suurempi kuin $k$.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: pienin välien määrä.

Rajat
Esimerkki

Syöte:
8 5
2 2 2 1 3 1 2 1


Tuloste:
3

Selitys: Jako on seuraava: "2 | 2 2 1 | 3 1 | 2 1". Huomaa, että yksi ryhmistä jatkuu taulukon lopusta alkuun.