TopCoder

拉菲好可愛 >////<
迷子でもいい、迷子でも進め!

User's AC Ratio

66.7% (4/6)

Submission's AC Ratio

50.0% (4/8)

Tags

Description

明天就是 NSSPC 決賽了!緊張的你為了避免睡過頭遲到,你買了 $N$ 個鬧鐘,並且設定好第 $i$ 個鬧鐘會在明天早上七點後的 $s_i$ 微秒(一微秒是 $10^ {-6}$ 秒)這個瞬間響起。另外,你設定了一個所有鬧鐘共用的週期 $t$,當一個鬧鐘響了之後,它就會在 $t$ 微秒後再響一次,也就是說,第 $i$ 個鬧鐘會在早上七點後的 $s_i,s_i+t,s_i+2t,\ldots$ 微秒時響。當一個鬧鐘響的時候,它只會響一瞬間而已,比一微秒還要短,因為你的聽力驚人,所以你一定聽得到。

雖然你聽力驚人,但你很喜歡賴床。隔天早上你起床的時候,發現現在已經是早上七點過後 $T$ 微秒了,你想知道在這之前,你已經聽見過幾次鬧鐘。注意到如果有多個鬧鐘同時響起,你只會聽見一次鬧鐘而已,另外,早上七點後 $T$ 微秒當下如果有鬧鐘響了,那也算一次。

舉例來說,$N=3$、$s_1=4$、$s_2=8$、$s_3=7$、$t=2$、$T=11$,那麼第 1 個鬧鐘會在七點後 $4,6,8,10$ 微秒時響、第 2 個鬧鐘會在七點後 $8,10$ 微秒時響、第 3 個鬧鐘會在七點後 $7,9,11$ 微秒時響,你總共會聽見 7 次鬧鐘,因為有 7 個不同的有鬧鐘響的時間點,分別是七點後 $4,6,7,8,9,10,11$ 微秒。

Input Format

第一行有三個整數 $N,t,T$,分別代表鬧鐘的數量、所有鬧鐘共用的週期,以及你起床的時間點是早上七點後 $T$ 微秒。

第二行有 $N$ 個以空白分隔的整數 $s_1,s_2,\ldots,s_N$,代表 $N$ 個鬧鐘第一次響的時間點。

  • $1 \leq N \leq 10^ 5$
  • $1 \leq t \leq 10^ 6$
  • $0 \leq s_i,T \leq 10^ 9$

Output Format

輸出一個整數,代表你在早上七點過後 $T$ 微秒以前(含第 $T$ 微秒當下)聽見了幾次鬧鐘。

Sample Input 1

3 2 11
4 8 7

Sample Output 1

7

Sample Input 2

11 6 1000000000
0 1 2 3 4 5 6 7 8 9 10

Sample Output 2

1000000001

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~11 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2