English · Original
Chinese · Translation
Formal · Original
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 _t_1 = 4, _t_2 = 7, _t_3 = 9 and _t_4 = 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 _t_1, _t_2, ..., _t__m_.
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 _t_1, _t_2, ..., _t__m_ (1 ≤ _t__i_ ≤ 1018) — moments of time when clients will come. The values _t__i_ are given in non-decreasing order.
## Output
Print the number of times the door will open.
[samples]
## 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.
工厂入口处有一扇自动门。门的工作方式如下：
例如，若 #cf_span[d = 3] 且四个人分别在时刻 #cf_span[t1 = 4]、#cf_span[t2 = 7]、#cf_span[t3 = 9] 和 #cf_span[t4 = 13] 到达，则门将在时刻 #cf_span[4]、#cf_span[9] 和 #cf_span[13] 打开三次，在时刻 #cf_span[7] 和 #cf_span[12] 关闭两次。
已知 #cf_span[n] 名员工将在时刻 #cf_span[a, 2·a, 3·a, ..., n·a] 进入（其中 #cf_span[a] 为正整数）。同时，#cf_span[m] 名客户将在时刻 #cf_span[t1, t2, ..., tm] 到达。
请编写程序计算自动门将打开多少次。假设门初始为关闭状态。
第一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[a] 和 #cf_span[d]（#cf_span[1 ≤ n, a ≤ 109], #cf_span[1 ≤ m ≤ 105], #cf_span[1 ≤ d ≤ 1018]）——分别表示员工人数、客户人数、第一名员工到达的时刻以及门关闭所需的时间间隔。
第二行包含整数序列 #cf_span[t1, t2, ..., tm]（#cf_span[1 ≤ ti ≤ 1018]）——客户到达的时刻。这些值按非递减顺序给出。
请输出门打开的次数。
在第一个示例中，唯一的一名员工将在时刻 #cf_span[3] 到达。此时门将打开，并保持开启直到时刻 #cf_span[7]。在同一时刻，一名客户也到达，因此他先进入，之后门才关闭。因此门总共打开一次。
## Input
第一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[a] 和 #cf_span[d]（#cf_span[1 ≤ n, a ≤ 109], #cf_span[1 ≤ m ≤ 105], #cf_span[1 ≤ d ≤ 1018]）——分别表示员工人数、客户人数、第一名员工到达的时刻以及门关闭所需的时间间隔。第二行包含整数序列 #cf_span[t1, t2, ..., tm]（#cf_span[1 ≤ ti ≤ 1018]）——客户到达的时刻。这些值按非递减顺序给出。
## Output
请输出门打开的次数。
[samples]
## Note
在第一个示例中，唯一的一名员工将在时刻 #cf_span[3] 到达。此时门将打开，并保持开启直到时刻 #cf_span[7]。在同一时刻，一名客户也到达，因此他先进入，之后门才关闭。因此门总共打开一次。
**Definitions**
Let $ n, m, a, d \in \mathbb{Z}^+ $, with $ 1 \leq n, a \leq 10^9 $, $ 1 \leq m \leq 10^5 $, $ 1 \leq d \leq 10^{18} $.
Let $ E = \{ ka \mid k \in \{1, 2, \dots, n\} \} $ be the set of entry times for employees.
Let $ C = \{ t_1, t_2, \dots, t_m \} $ be the set of entry times for clients, with $ t_1 \leq t_2 \leq \dots \leq t_m $.
Let $ T = E \cup C $ be the multiset of all entry times, sorted in non-decreasing order.
**Constraints**
1. All times in $ T $ are positive integers.
2. The door is initially closed.
3. When a person arrives at time $ \tau $:
- If the door is closed, it opens and remains open until time $ \tau + d $.
- If the door is already open (i.e., $ \tau \leq \text{closing time} $), it remains open and the closing time is extended to $ \tau + d $.
4. Multiple people may arrive at the same time; each triggers the door to open (but only once per open event).
**Objective**
Compute the number of distinct door-opening events as people arrive in chronological order.
Each opening event is triggered the first time a person arrives during a closed interval.
The door opens once per such event, regardless of how many people arrive during the open interval.
Let $ S = \emptyset $ be the set of opening times.
Initialize $ \text{closing\_time} = -\infty $.
For each $ \tau \in T $ in increasing order:
If $ \tau > \text{closing\_time} $:
Add $ \tau $ to $ S $,
Set $ \text{closing\_time} = \tau + d $.
Output $ |S| $.
API Response (JSON)
{
"problem": {
"name": "A. Automatic Door",
"description": {
"content": "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 automaticall",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF883A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There is an automatic door at the entrance of a factory. The door works in the following way:\n\n* when one or several people come to the door and it is closed, the door immediately opens automaticall...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "工厂入口处有一扇自动门。门的工作方式如下：\n\n例如，若 #cf_span[d = 3] 且四个人分别在时刻 #cf_span[t1 = 4]、#cf_span[t2 = 7]、#cf_span[t3 = 9] 和 #cf_span[t4 = 13] 到达，则门将在时刻 #cf_span[4]、#cf_span[9] 和 #cf_span[13] 打开三次，在时刻 #cf_span[7] 和 #cf...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, a, d \\in \\mathbb{Z}^+ $, with $ 1 \\leq n, a \\leq 10^9 $, $ 1 \\leq m \\leq 10^5 $, $ 1 \\leq d \\leq 10^{18} $. \nLet $ E = \\{ ka \\mid k \\in \\{1, 2, \\dots, n\\} \\} $ be the se...",
"is_translate": false,
"language": "Formal"
}
]
}