Automatic Door (Codeforces 883A)
Tags: Implement, implementation

There is an automatic door at the entrance of a factory. The door works in the following way:  when one or several people come to the door and it is closed, the door immediately opens automatically and all people immediately come inside,  when one or several people come to the door and it is open, all people immediately come inside,  opened door immediately closes in d seconds after its opening,  if the door is closing and one or several people are coming to the door at the same moment, then all of them will have enough time to enter and only after that the door will close. For example, if d = 3 and four people are coming at four different moments of time t1 = 4, t2 = 7, t3 = 9 and t4 = 13 then the door will open three times: at moments 4, 9 and 13. It will close at moments 7 and 12.It is known that n employees will enter at moments a, 2·a, 3·a, ..., n·a (the value a is positive integer). Also m clients will enter at moments t1, t2, ..., tm.Write program to find the number of times the automatic door will open. Assume that the door is initially closed.

Input: The first line contains four integers n, m, a and d (1 ≤ n, a ≤ 109, 1 ≤ m ≤ 105, 1 ≤ d ≤ 1018) — the number of the employees, the number of the clients, the moment of time when the first employee will come and the period of time in which the door closes.The second line contains integer sequence t1, t2, ..., tm (1 ≤ ti ≤ 1018) — moments of time when clients will come. The values ti are given in non-decreasing order.

Output: Print the number of times the door will open.

Note: In the first example the only employee will come at moment 3. At this moment the door will open and will stay open until the moment 7. At the same moment of time the client will come, so at first he will enter and only after it the door will close. Thus the door will open one time.

Sample Inputs:
1 1 3 4
7

4 3 4 2
7 9 11

Sample Outputs:
1

4

Solution (Python):
import sys
from math import *
from bisect import *

def read_input(input_path=None):
    if input_path is None:
        f = sys.stdin
    else:
        f = open(input_path, 'r')
    (n, m, a, d) = map(int, f.readline().split())
    t = list(map(int, f.readline().split()))
    return (n, m, a, d, t)

def sol(n1, m, a, d, t):
    insort(t, a * n1)
    pred = 0
    k = 0
    n = 0
    step = d // a + 1
    answer = 0
    fl = 0
    for i in t:
        if i > pred:
            if fl == 0:
                n = (i - pred + pred % a) // a
                if n != 0:
                    k += n // step * step - step * (n % step == 0) + 1
                    if k > n1:
                        k = n1
                        fl = 1
                if k * a + d >= i and n != 0:
                    pred = k * a + d
                else:
                    pred = i + d
                    k = floor(pred // a)
                    answer += 1
                k = min(floor(pred // a), n1)
                answer += n // step + (n % step != 0)
            else:
                answer += 1
                pred = i + d
        if i == a * n1:
            fl = 1
    return [f'{answer}']

def solve(input_path=None):
    return sol(*read_input(input_path))

def main():
    for line in sol(*read_input()):
        print(f'{line}')
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    (n1, m, a, d) = list(map(int, input().split()))
    t = list(map(int, input().split()))
    from bisect import insort
    from math import floor
    insort(t, a * n1)
    pred = 0
    k = 0
    kpred = 0
    n = 0
    step = d // a + 1
    sol = 0
    fl = 0
    for i in t:
        if i > pred:
            if fl == 0:
                n = (i - pred + pred % a) // a
                if n != 0:
                    k += n // step * step - step * (n % step == 0) + 1
                    if k > n1:
                        k = n1
                        fl = 1
                if k * a + d >= i and n != 0:
                    pred = k * a + d
                else:
                    pred = i + d
                    k = floor(pred // a)
                    sol += 1
                k = min(floor(pred // a), n1)
                sol += n // step + (n % step != 0)
            else:
                sol += 1
                pred = i + d
        if i == a * n1:
            fl = 1
    print(sol)
solve()

Solution (Python):
def solve():
    (n1, m, a, d) = list(map(int, input().split()))
    t = list(map(int, input().split()))
    from bisect import insort
    from math import floor
    insort(t, a * n1)
    pred = 0
    k = 0
    kpred = 0
    n = 0
    step = d // a + 1
    sol = 0
    fl = 0
    for i in t:
        if i > pred:
            if fl == 0:
                n = (i - pred + pred % a) // a
                if n != 0:
                    k += n // step * step - step * (n % step == 0) + 1
                    if k > n1:
                        k = n1
                        fl = 1
                if k * a + d >= i and n != 0:
                    pred = k * a + d
                else:
                    pred = i + d
                    k = floor(pred // a)
                    sol += 1
                k = min(floor(pred // a), n1)
                sol += n // step + (n % step != 0)
            else:
                sol += 1
                pred = i + d
        if i == a * n1:
            fl = 1
    print(sol)
solve()