Algorithm

Problem link- https://codeforces.com/problemset/problem/11/A
A. Increasing Sequence
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

A sequence a0, a1, ..., at - 1 is called increasing if ai - 1 < ai for each i: 0 < i < t.

You are given a sequence b0, b1, ..., bn - 1 and a positive integer d. In each move you may choose one element of the given sequence and add d to it. What is the least number of moves required to make the given sequence increasing?

Input

The first line of the input contains two integer numbers n and d (2 ≤ n ≤ 2000, 1 ≤ d ≤ 106). The second line contains space separated sequence b0, b1, ..., bn - 1 (1 ≤ bi ≤ 106).

Output

Output the minimal number of moves needed to make the sequence increasing.

Examples
input
Copy
4 2
1 3 3 2
output
Copy
3

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <cstdio>

int main(){

    long n(0), d(0); scanf("%ld %ld\n", &n, &d); 
    long current(-1), total(0);
    for(int k = 0; k < n; k++){
        long temp(0); scanf("%ld", &temp);
        if(current < temp){current = temp;}
        else{
            long times = 1 + (current - temp)/d;
            current = temp + times * d;
            total += times;
        }
    }

    printf("%ld\n", total);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4 2
1 3 3 2

Output

x
–
+
cmd
3
Advertisements

Demonstration

Codeforces Solution-A. Increasing Sequence-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+