1627 . 聖誕燈泡
TopCoder
Tags
Description
聖誕節的時候都有很多一串一串的燈泡，現在你家裡就掛了一串。
這一串燈泡總共有 n 顆燈泡，第 i (1≦i≦n)顆燈泡會固定亮t_i秒後熄滅t_i，接著再亮t_i秒後熄滅t_i秒……。
一開始所有的燈泡都是亮的。
那請問在 [k秒, k+1秒) 這段時間時，總共有幾顆燈泡亮著呢 ?
Input Format
輸入可能包含多筆測資，以 EOF 結束輸入。
每筆輸入的第一行依序是三個正整數，N、T、Q，
接下來的一行有 N 個數字，第 i 個數字代表 t_i，
接下來的那一行共有 Q 個數字，第 j 個數字 q_j 即詢問在 [q_j, q_j + 1) 的時間中有幾顆燈泡亮著。
條件限制：
1 ≦ N, Q ≦100,000
1 ≦ t_i ≦ T ≦ 5,000,000
0 ≦ q_j ＜ T
Output Format
對於每一筆詢問請輸出一行，即詢問的那一秒有幾顆燈泡亮著。
每組測試資料後請輸出一個空白行。
Sample Input 1
3 6 6
1 2 3
0 1 2 3 4 5
1 2 2
1
0 1
1 2 3
0 1 2 3 4 5
1 2 2
1
0 1
Sample Output 1
3
2
2
0
2
1
1
0
2
2
0
2
1
1
0
Hints
對於第一筆範例測資來說：
時間點
0 1 ２ 3 ４ 5 ６
燈 １│亮│ │亮│ │亮│ │
泡 ２│亮│亮│ │ │亮│亮│
３│亮│亮│亮│ │ │ │
總數： 3 3 ２ 0 ２ 1
Problem Source
原TIOJ1627 / Problem Setter: suhorng
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |