time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You received a notebook which is called Death Note. This notebook has infinite number of pages. A rule is written on the last page (huh) of this notebook. It says: "You have to write names in this notebook during n consecutive days. During the i-th day you have to write exactly ai names.". You got scared (of course you got scared, who wouldn't get scared if he just receive a notebook which is named Death Note with a some strange rule written in it?).
Of course, you decided to follow this rule. When you calmed down, you came up with a strategy how you will write names in the notebook. You have calculated that each page of the notebook can contain exactly m names. You will start writing names from the first page. You will write names on the current page as long as the limit on the number of names on this page is not exceeded. When the current page is over, you turn the page. Note that you always turn the page when it ends, it doesn't matter if it is the last day or not. If after some day the current page still can hold at least one name, during the next day you will continue writing the names from the current page.
Now you are interested in the following question: how many times will you turn the page during each day? You are interested in the number of pages you will turn each day from 1 to n.
Input
The first line of the input contains two integers n, m (1≤n≤2⋅105, 1≤m≤109) — the number of days you will write names in the notebook and the number of names which can be written on each page of the notebook.
The second line contains n integers a1,a2,…,an (1≤ai≤109), where ai means the number of names you will write in the notebook during the i-th day.
Output
Print exactly n integers t1,t2,…,tn, where ti is the number of times you will turn the page during the i-th day.
Examples
input
3 5
3 7 9
output
0 2 1
input
4 20
10 9 19 2
output
0 0 1 1
input
1 100
99
output
0
Note
In the first example pages of the Death Note will look like this [1,1,1,2,2],[2,2,2,2,2],[3,3,3,3,3],[3,3,3,3]. Each number of the array describes during which day name on the corresponding position will be written. It is easy to see that you should turn the first and the second page during the second day and the third page during the third day.
Hopefully you've skimmed through the problem.
The answer to the problem is simple but I here I'll not directly jump to the answer. I'll try to break the problem in small problems, find the solution and then construct an answer.
Note: Now there might be more efficient or straightforward answers available out there.
Hopefully you've skimmed through the problem.
Now let's talk about the first test case.
Hopefully you've gone through the problem statement thoroughly. So without any further ado, let's dive in.
In the first case the maximum number of names that we can write on a page is 5.
Let's number these lines of those pages starting from 1 to 5.
All of these pages have lines starting from line 1 to line 5 just like this picture below.
I've drawn all the pages in this timeline format to make it easier for you to understand.
Now in our first day we'll have to write 3 words. Therefore we'll have to write on the first three lines starting from 1 to 3.
It'll look something like this.
And therefore we can say we didn't have to turn a single page, because there were in total 5 lines in the first page, but we had to write only 3 (I'll denote this value with variable 'x') and therefore the number of pages needed to turn is 0.
Now one thing if you notice here, you can easily construct a formula. You can find out the total number of pages that needs to be turned by simply dividing the total number of names you'll have to write on that given day by the maximum number of names you can write on the page.
So the formula is number of pages = x/m
So in this case it's going to be 3/5 = 0 times.
well, let me easily explain it to you with another example.
say we've got 22 names to write on a particular day and we've a maximum limit of 5 in each pages.
How many times do you need to turn pages for that?
4 times at least, or 22/5 = 4 times.
In this case well only take the floor value of the result. In the picture the two symbols wrapping '3/5' is actually a floor function if you're not familiar with it.
Now let's get back to our problem. After writing x=3 lines of names we'll be on line number 3. Or we can say we've taken 3 extra steps. Now how to find out which line am I on? For that we'll have to just mod the total number of names I need to write by the maximum number of names I can write on a page.
So, the line I'm on currently, current_line = (x%m);
Now one thing that I want to mention is that whenever the value of the line I'm currently on or current_line becomes '0', it will mean that I'm on the the first line of the next page or the last line of the current page actually. Now I'm on the last line is as good as saying I'll start anew from the next page and therefore whenever I'll be on the last line of a page, the value of current_line will become '0'.
Now just remember this, because this is what we're going to need in the next scenario.
Now the next day we'll have to write 7 names (now 'x' becomes 7). Now remember last time we ended at line 3, and therefore we'll have to start from after that line.
If we start after the line 3 and write 7 names in the book we'll have to turn 2 pages as we can see it from the output. And that's absolutely correct if you check it manually.
But if we apply the formula we've used earlier then we find (x/m) = (7/5) = 1, so this formula says we'll have to turn 1 page, but this is not the right answer.
Then where is the problem? The problem lies in the number of line that we start from.
This formula only works if we start from the same line, or in this case line 1.
Now the solution to it is also really simple, have a look at the picture below.
In this case we are starting from node 4 actually, because the last line we were on was 3. And if we start after the last line 3, then we'll end up at line 5. So we had to go from page one to page two, and in page two we're at the last line therefore we'll actually have to turn the page although we won't write after turning the page, so that counts as well. So in total I'll have to turn the pages twice.
Now as you can see that the problem in this case is we started from line 4, now if we start from line 4 and write 7 names then we'll stop at 5 on the send page.
Now if we start at line 1 and write 10 names on the book then we'll also end up at line 5 on the 2nd page.
Therefore starting from line 4, or I should instead say, starting to write after line '3' is as good as starting from line 1 and writing 10 names.
Now '10' is what we get to from '7' because we'll have to start from line 1 for our formula to work.
we can simply say 10 = 7 + 3 = x + last_current_line.
Now in our previous iteration we found out current_line is 3. and in our current iteration we haven't changed the value of current line. and therefore the value of current_line is actually the value of last_current_line.
Now we'll just assign this 10 as the new value of x.
Now that we've found out where we should actually start from, we can now apply our formula on the new value of x.
so, x/m = 10/5 = 2.
Now it's giving us the right answer, because now we're starting at the 'correct' node.
Now let's check out the new value of current_line. current_line = x%m = 10%5 = 0.
But we can see from the picture that the current line should instead be 5.
But if you can recall from our earlier discussion about the last line, when we're at the last line we'll turn to the next page whether we'll write name on the next page or not. Therefore value of current_line has become 0 because we'll start from the first line of the next page in our next iteration.
Now those are the three formulas we need to solve this problem!
Now code for the given problem using this solution is attached below.
Now when the while loop works for the first line the the value of last_line should be '0'.
It's because we're starting from the first page, and therefore there is no last page. Or even if we assume that there was a last page then we can also assume that we would must be on the last line of the last page because we'll have to write names from the first line of the current page or the first page in this case.
And the rest of the code does all the works described here.
Hopefully you've skimmed through the problem.
The answer to the problem is simple but I here I'll not directly jump to the answer. I'll try to break the problem in small problems, find the solution and then construct an answer.
Note: Now there might be more efficient or straightforward answers available out there.
Hopefully you've skimmed through the problem.
Now let's talk about the first test case.
input
3 5
3 7 9
output
0 2 1
Hopefully you've gone through the problem statement thoroughly. So without any further ado, let's dive in.
In the first case the maximum number of names that we can write on a page is 5.
Let's number these lines of those pages starting from 1 to 5.
All of these pages have lines starting from line 1 to line 5 just like this picture below.
I've drawn all the pages in this timeline format to make it easier for you to understand.
Now in our first day we'll have to write 3 words. Therefore we'll have to write on the first three lines starting from 1 to 3.
It'll look something like this.
And therefore we can say we didn't have to turn a single page, because there were in total 5 lines in the first page, but we had to write only 3 (I'll denote this value with variable 'x') and therefore the number of pages needed to turn is 0.
Now one thing if you notice here, you can easily construct a formula. You can find out the total number of pages that needs to be turned by simply dividing the total number of names you'll have to write on that given day by the maximum number of names you can write on the page.
So the formula is number of pages = x/m
So in this case it's going to be 3/5 = 0 times.
well, let me easily explain it to you with another example.
say we've got 22 names to write on a particular day and we've a maximum limit of 5 in each pages.
How many times do you need to turn pages for that?
4 times at least, or 22/5 = 4 times.
In this case well only take the floor value of the result. In the picture the two symbols wrapping '3/5' is actually a floor function if you're not familiar with it.
Now let's get back to our problem. After writing x=3 lines of names we'll be on line number 3. Or we can say we've taken 3 extra steps. Now how to find out which line am I on? For that we'll have to just mod the total number of names I need to write by the maximum number of names I can write on a page.
So, the line I'm on currently, current_line = (x%m);
Now one thing that I want to mention is that whenever the value of the line I'm currently on or current_line becomes '0', it will mean that I'm on the the first line of the next page or the last line of the current page actually. Now I'm on the last line is as good as saying I'll start anew from the next page and therefore whenever I'll be on the last line of a page, the value of current_line will become '0'.
Now just remember this, because this is what we're going to need in the next scenario.
Now the next day we'll have to write 7 names (now 'x' becomes 7). Now remember last time we ended at line 3, and therefore we'll have to start from after that line.
If we start after the line 3 and write 7 names in the book we'll have to turn 2 pages as we can see it from the output. And that's absolutely correct if you check it manually.
But if we apply the formula we've used earlier then we find (x/m) = (7/5) = 1, so this formula says we'll have to turn 1 page, but this is not the right answer.
Then where is the problem? The problem lies in the number of line that we start from.
This formula only works if we start from the same line, or in this case line 1.
Now the solution to it is also really simple, have a look at the picture below.
In this case we are starting from node 4 actually, because the last line we were on was 3. And if we start after the last line 3, then we'll end up at line 5. So we had to go from page one to page two, and in page two we're at the last line therefore we'll actually have to turn the page although we won't write after turning the page, so that counts as well. So in total I'll have to turn the pages twice.
Now as you can see that the problem in this case is we started from line 4, now if we start from line 4 and write 7 names then we'll stop at 5 on the send page.
Now if we start at line 1 and write 10 names on the book then we'll also end up at line 5 on the 2nd page.
Therefore starting from line 4, or I should instead say, starting to write after line '3' is as good as starting from line 1 and writing 10 names.
Now '10' is what we get to from '7' because we'll have to start from line 1 for our formula to work.
we can simply say 10 = 7 + 3 = x + last_current_line.
Now in our previous iteration we found out current_line is 3. and in our current iteration we haven't changed the value of current line. and therefore the value of current_line is actually the value of last_current_line.
Now we'll just assign this 10 as the new value of x.
Now that we've found out where we should actually start from, we can now apply our formula on the new value of x.
so, x/m = 10/5 = 2.
Now it's giving us the right answer, because now we're starting at the 'correct' node.
Now let's check out the new value of current_line. current_line = x%m = 10%5 = 0.
But we can see from the picture that the current line should instead be 5.
But if you can recall from our earlier discussion about the last line, when we're at the last line we'll turn to the next page whether we'll write name on the next page or not. Therefore value of current_line has become 0 because we'll start from the first line of the next page in our next iteration.
Now those are the three formulas we need to solve this problem!
- new value of x = x + current_line;
- no of pages needed to be turned = floor (new value of x / m);
- current_line = new value of x % m;
Now code for the given problem using this solution is attached below.
Now when the while loop works for the first line the the value of last_line should be '0'.
It's because we're starting from the first page, and therefore there is no last page. Or even if we assume that there was a last page then we can also assume that we would must be on the last line of the last page because we'll have to write names from the first line of the current page or the first page in this case.
And the rest of the code does all the works described here.
0 Comments