Codeforces Solution-Death Note-Solution in C, C++, Java, Python

Algorithm

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 $a_{i}$ 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 \leq n \leq 2 \cdot 10^{5}$ , $1 \leq m \leq 10^{9}$ ) — 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 $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ), where $a_{i}$ means the number of names you will write in the notebook during the $i$ -th day.

Output

Print exactly $n$ integers $t_{1}, t_{2}, \dots, t_{n}$ , where $t_{i}$ is the number of times you will turn the page during the $i$ -th day.

Examples
input
Copy
3 5
3 7 9
output
Copy
0 2 1 
input
Copy
4 20
10 9 19 2
output
Copy
0 0 1 1 
input
Copy
1 100
99
output
Copy
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.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, m, a[N];

int main() {
  scanf("%d %d", &n, &m);
  for(int i = 0; i < n; ++i)
    scanf("%d", a + i);

  int rem = m;
  for(int d = 0; d < n; ++d) {
    int cur = a[d], res = 0;
    if(cur < rem)
      rem -= cur;
    else if(cur == rem)
      ++res, rem = m;
    else {
      cur -= rem;
      rem = m;
      ++res;

      if(cur < rem)
        rem -= cur;
      else if(cur == rem)
        ++res, rem = m;
      else {
        res += cur / rem;
        cur = cur % rem;
        rem -= cur;
      }
    }

    printf("%d ", res);
  }

  puts("");

  return 0;
}

Copy The Code & Try With Live Editor

Input

–

cmd

3 5

Output

–

cmd

0 2 1

Demonstration

Codeforces Solution-Death Note-Solution in C, C++, Java, Python,Death Note-Solution,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 11 months ago 386 0