B. Vanya and Food Processor
time limit per test 1 second
memory limit per test 256 megabytes
input standard input
output standard output
Vanya smashes potato in a vertical food processor. At each moment of time the height of the potato in the processor doesn't exceed hand the processor smashes k centimeters of potato each second. If there are less than k
Vanya has n pieces of potato, the height of the i-th piece is equal to ai. He puts them in the food processor one by one starting from the piece number 1 and finishing with piece number n. Formally, each second the following happens:
- If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece.
- Processor smashesk
Provided the information about the parameter of the food processor and the size of each potato in a row, compute how long will it take for all the potato to become smashed.
Input
The first line of the input contains integers n, h and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 109) — the number of pieces of potato, the height of the food processor and the amount of potato being smashed each second, respectively.
The second line contains n integers ai (1 ≤ ai ≤ h) — the heights of the pieces.
Output
Print a single integer — the number of seconds required to smash all the potatoes following the process described in the problem statement.
Examples
input
5 6 3
5 4 3 2 1
output
5
input
5 6 3
5 5 5 5 5
output
10
input
5 6 3
1 2 1 1 1
output
2
Note
Consider the first sample.
- First Vanya puts the piece of potato of height 5 into processor. At the end of the second there is only amount of height 2
- Now Vanya puts the piece of potato of height 4. At the end of the second there is amount of height 3
- Vanya puts the piece of height 3 inside and again there are only 3
- Vanya finally puts the pieces of height 2 and 1 inside. At the end of the second the height of potato in the processor is equal to 3.
- During this second processor finally smashes all the remaining potato and the process finishes.
In the second sample, Vanya puts the piece of height 5 inside and waits for 2 seconds while it is completely smashed. Then he repeats the same process for 4 other pieces. The total time is equal to 2·5 = 10
In the third sample, Vanya simply puts all the potato inside the processor and waits 2
題解:有一個榨汁機,有n個potato,一個一個地放進去,榨汁機可以一次性榨掉的高度為h,每秒鐘可以榨k米,問榨完最少需要多少時間。
貪心呗,從最小的開始榨,然後就是數學了。。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[100010]={0};
int main()
{
LL n,h,k;
while(cin>>n>>h>>k)
{
for(int i=0;i<n;i++)
{
scanf("%I64d",&a[i]);
}
LL sum=0,ans=0;
for(int i=0;i<n;i++)
{
if(sum+a[i]<=h) sum+=a[i];
else
{
sum=a[i];
ans++;
}
LL t=sum/k;
ans+=t;
sum-=t*k;
}
if(sum)ans++;
printf("%I64d\n",ans);
}
return 0;
}