### PROBLEM LINK:

**Author:** Egor Bobyk

**Tester:** Mugurel Ionut Andreica

**Editorialist:** Lalit Kundu

### DIFFICULTY:

Simple

### PREREQUISITES:

implementation, basic maths

### PROBLEM:

Some chefs go for a tour lasting N days. They take packages of bread for food. Each package has K pieces of breads. In i-th day, they eat A_i pieces of bread.

**Each day** the last piece of bread of an open package goes bad. Find minimum number of packages required to complete the tour.

### EXPLANATION:

================

Let’s think step by step here.

- Chefs should never leave more than one package open, since each night from each package one bread goes bad. So, it is intuitive.
- From previous statement, we can also imply that Chefs will keep opening packages on a day until that day’s demand A_i is met. And, leave the remaining(if remaining) breads for the next day.
- We can, in constant time, find the number of new packages to be opened if we know current(say extrm{cur}) and required(say extrm{req}) number of breads. We need to open x packages such that x*K + cur \ge req where x \ge 0. Now, we can easily define x as extrm{ceil}(\frac{req - cur}{K}) or basically in integer operations as
(req - cur)/K + ((req - cur)%K > 0)

Second term is required to satisfy the inequality.

This is our solution expressed as a pseudo code:

N, K, A[] = input cur = 0 //total number of breads available right now ans = 0 //total number of packages opened till now for i = 0 to N - 1: //solve for inequality cur + x*K >= A* where x>=0 x = (A*-cur)/K + ((A*-cur)%K > 0) //if x < 0, no package required x = 0 //increase answer if packages opened ans += x //change current number of breads left after consumption cur = cur +x*K- A* //decrease 1 bread if some number of breads are left if (cur > 0) cur-- print ans

### COMPLEXITY:

For each test case, complexity is O(N) because we are traversing over number of days ie. N here.