TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

5.9% (1/17)

Tags

Description

(本題敘述稍長, 不喜看故事者可以直接跳到下面題目敘述)

順利地拖過了m秒, 妁艷舉起了武器, 開始和敵人糾纏在一起.

經過社辦激烈的一戰, 妁艷戰勝了, 社員倒在地上顫抖, 體力透支了的樣子, 但仍然有意識.

賺了不少經驗值的妁艷也升了幾等, 能夠拿更強的武器, 用更強的技能了.

妁艷走向已經倒在地上的社員.

"這到底是怎麼回事? 能告訴我嗎?"

"咦! 我怎麼會>//////<, 討厭, 大葛格你對我做了什麼!?"

"剛才妳好像中了魔法似的, 想要攻擊我. 我出於無奈只好做出防衛了. 妳可以告訴我這到底是怎麼回事嗎?"

"我不知道, 我最後一次有記憶的時候......., 好像是體育課的時候吧...., 我突然失去了知覺, 一直到現在才回復意識."

"......"

"快放我離開>//////<, 不要看這裡, 我很難為情. "

眼看無法再逼出口供, 再待下去會產生許多麻煩的妁艷, 只好快速離開, 到妹妹的教室尋找妹妹.

沿路上, 所有教室全都是暗的, 這是夜晚的學校.

妁艷走到了妹妹的教室門口, 教室仍然一片漆黑, 伸手不見五指.

他鼓起勇氣, 打開了教室的門. 裡面仍然毫無反應.

妁艷於是進了教室, 摸了摸教室的牆壁, 黑板, 桌椅.

一切正常, 妁艷鬆了口氣, 卸下武裝.

他喊了妹妹的名字, 但沒有半點回應.

為了尋找線索, 妁艷走到了妹妹的座位, 翻了翻妹妹的抽屜, 雖然教室一片漆黑, 但至少先拿些東西走吧? RPG不都是要到處搜刮道具嗎?

背德的行為總是讓人感到興奮, 妁艷心裡燃起了火(?).

這個時候,  教室的燈竟然在一瞬間全部亮起.

妁艷在驚嚇之虞望了望四周, 四周竟然全是妹妹的同學. 密密麻麻, 門口也被封死了!

用不著說, 她們全部都中了魔法, 用奇怪的眼神看著妁艷!

這時, 妁艷瞭解了自己現在的處境------他被包圍了!!!

同學們站在原地看著妁艷.

"葛格, 呵呵呵, 大家快看, 這裡有一個可愛的葛格喔~♥"

"哈~呵~哈~呵~哈~♥"

"葛格, 還站在哪裡做什麼? 快來這裡啊…, 我會溫柔地告訴葛格妹妹在哪喔♥"

"我的名字..."

雖然沒有直接的攻擊, 但這些話對妁艷似乎具有混亂效果, 就像神奇寶貝中的超音波!

"不!!!不行!!!再這樣下去我會失去理智啊~~~", 妁艷道.

妁艷決定拔劍而戰, 他將武器裝上了增強貫穿性的套件, 準備快速解決所有敵人.

戰場的狀況如下(以下題目敘述開始):

(1) 妁艷被包圍在中央, 外圍都是妹妹的同學(敵人).

(2) 武器威力很強, 並且具有貫穿性, 攻擊一個特定方位, 被攻擊到的敵人都會倒地顫抖進入無法戰鬥的狀態.

(3) 武器的僵硬時間(CD)很大, 所以妁艷必須使用武器最少次來擊倒所有敵人.

(4) 由於敵人的位置有近有遠, 在視覺上有的比較大有的比較小.

(5) 妁艷將自己的四面八方平分成0~L-1的L個角度單位, 並快速掌握了每個敵人所占的方位(一個區間).

(6) 武器必須攻擊到敵人的內點(interior)才會有效果, 擦到邊邊(boundary)無效.

快幫助妁艷算出如何有效利用武器, 以最少攻擊次數擊倒所有敵人吧.

Input Format

第一行有兩個數字N, L(1 ≤ N ≤ 100,000, 2 ≤ L ≤ 2,000,000,000), 分別代表有幾個敵人, 和上文中的L.
第2到N + 1行, 每行有兩個數字s, e(0 ≤s, e < L, s≠e), 代表描述的敵人所佔位置(上述的角度單位)由s到e(s, e是兩個boundary), (注意方位是環狀的, 即有可能s > e).

Output Format

輸出唯一個數字, 代表至少要發射幾發才能擊倒所有敵人(不一定要往整數點方向發射).

Sample Input 1

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

Sample Output 1

2

Hints


灰線是角度等分點, 黑線是妹妹同學.
妁艷發射2發(紅線)在2.5和7.5即可攻擊到所有敵人的內點.

Problem Source

原TIOJ1755 / problem setter: willyliu.

Subtasks

No. Testdata Range Score
1 0 1
2 1 1
3 2 1
4 3 1
5 4 1
6 5 1
7 6 1
8 7 1
9 8 1
10 9 1
11 10 1
12 11 1
13 12 1
14 13 1
15 14 1
16 15 1
17 16 1
18 17 1
19 18 1
20 19 1
21 20 1
22 21 1
23 22 1
24 23 1
25 24 1
26 25 1
27 26 1
28 27 1
29 28 1
30 29 1
31 30 1
32 31 1
33 32 1
34 33 1
35 34 1
36 35 1
37 36 1
38 37 1
39 38 1
40 39 1
41 40 1
42 41 1
43 42 1
44 43 1
45 44 1
46 45 1
47 46 1
48 47 1
49 48 1
50 49 1
51 50 1
52 51 1
53 52 1
54 53 47

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 15000 65536 262144 1
1 15000 65536 262144 2
2 15000 65536 262144 3
3 15000 65536 262144 4
4 15000 65536 262144 5
5 15000 65536 262144 6
6 15000 65536 262144 7
7 15000 65536 262144 8
8 15000 65536 262144 9
9 15000 65536 262144 10
10 15000 65536 262144 11
11 15000 65536 262144 12
12 15000 65536 262144 13
13 15000 65536 262144 14
14 15000 65536 262144 15
15 15000 65536 262144 16
16 15000 65536 262144 17
17 15000 65536 262144 18
18 15000 65536 262144 19
19 15000 65536 262144 20
20 15000 65536 262144 21
21 15000 65536 262144 22
22 15000 65536 262144 23
23 15000 65536 262144 24
24 15000 65536 262144 25
25 15000 65536 262144 26
26 15000 65536 262144 27
27 15000 65536 262144 28
28 15000 65536 262144 29
29 15000 65536 262144 30
30 15000 65536 262144 31
31 15000 65536 262144 32
32 15000 65536 262144 33
33 15000 65536 262144 34
34 15000 65536 262144 35
35 15000 65536 262144 36
36 15000 65536 262144 37
37 15000 65536 262144 38
38 15000 65536 262144 39
39 15000 65536 262144 40
40 15000 65536 262144 41
41 15000 65536 262144 42
42 15000 65536 262144 43
43 15000 65536 262144 44
44 15000 65536 262144 45
45 15000 65536 262144 46
46 15000 65536 262144 47
47 15000 65536 262144 48
48 15000 65536 262144 49
49 15000 65536 262144 50
50 15000 65536 262144 51
51 15000 65536 262144 52
52 15000 65536 262144 53
53 15000 65536 262144 54