TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

100.0% (5/5)

Description


『報告船長,前方的山洞裡發現了寶藏,可是已經有其他海賊團先找到了。』一個海賊正在向船長報告偵查的結果。『那就用大砲把他們轟光搶過來啊!』船長不耐煩的揮了揮手。『可是…他們也料到了這個情況,所以人和寶藏混起來圍成一圈,大砲打下去很可能會毀壞許多寶藏。』那名海賊說。『這樣啊…』船長摸了摸下巴。『喂,參謀。你去看看要如何打才能得到最多寶藏吧。』

身為船上的參謀,你看了看報告以後發現,對面海賊團圍在一個圓圈上習慣用同樣的順序。而且一砲打下去殺死若干海賊毀壞若干寶藏以後,他們會重整然後一樣圍成一個圓,且之間的順序不變。他們所圍成的圈的半徑不會變,而且船上炮彈爆炸的半徑大於他們圍成的圈的半徑。檢查過船上的砲彈存量以後,你發現一次至少要炸死兩個敵方海賊(所以剩三個海賊的話一定要一次打死三個)。你決定寫個程式幫你計算。

Input Format

輸入檔中有許多組輸入,每組輸入的第一行有四個整數R1、R2、P、T(0 < R1 < R2 < 10000,2 ≦ P ≦ 100000,3 ≦ P+T ≦ 2147483647),分別代表他們圍成圈的半徑、炮彈爆炸的半徑、海賊的人數和寶藏的份數。下一行會有P個整數 N1、N2…Np(0 ≦ N1 ≦ N2 ≦ …≦ Np ≦ P+T),分別代表海賊所在的位置的編號(正北方為0號,依順時針編號)。遇到第一行為四個零“0 0 0 0”為檔案結束,不須處理這組輸入。

Output Format

對每組輸入請輸出一個數字代表最多可以拿到的寶藏份數,每個數字佔一行。

Sample Input

300 500 5 15
0 4 8 12 16
0 0 0 0

Sample Output

6

Hints

Problem Source

原TIOJ1102 / NPSC2006決賽(prob E)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1