TopCoder

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

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

63.6% (7/11)

Tags

Description

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

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

舉例來說,N=3s1=4s2=8s3=7t=2T=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 個以空白分隔的整數 s1,s2,,sN,代表 N 個鬧鐘第一次響的時間點。

  • 1N105
  • 1t106
  • 0si,T109

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