(本題敘述稍長, 不喜看故事者可以直接跳到下面題目敘述)
順利地拖過了m秒, 妁艷舉起了武器, 開始和敵人糾纏在一起.
經過社辦激烈的一戰, 妁艷戰勝了, 社員倒在地上顫抖, 體力透支了的樣子, 但仍然有意識.
賺了不少經驗值的妁艷也升了幾等, 能夠拿更強的武器, 用更強的技能了.
妁艷走向已經倒在地上的社員.
"這到底是怎麼回事? 能告訴我嗎?"
"咦! 我怎麼會>//////<, 討厭, 大葛格你對我做了什麼!?"
"剛才妳好像中了魔法似的, 想要攻擊我. 我出於無奈只好做出防衛了. 妳可以告訴我這到底是怎麼回事嗎?"
"我不知道, 我最後一次有記憶的時候......., 好像是體育課的時候吧...., 我突然失去了知覺, 一直到現在才回復意識."
"......"
"快放我離開>//////<, 不要看這裡, 我很難為情. "
眼看無法再逼出口供, 再待下去會產生許多麻煩的妁艷, 只好快速離開, 到妹妹的教室尋找妹妹.
沿路上, 所有教室全都是暗的, 這是夜晚的學校.
妁艷走到了妹妹的教室門口, 教室仍然一片漆黑, 伸手不見五指.
他鼓起勇氣, 打開了教室的門. 裡面仍然毫無反應.
妁艷於是進了教室, 摸了摸教室的牆壁, 黑板, 桌椅.
一切正常, 妁艷鬆了口氣, 卸下武裝.
他喊了妹妹的名字, 但沒有半點回應.
為了尋找線索, 妁艷走到了妹妹的座位, 翻了翻妹妹的抽屜, 雖然教室一片漆黑, 但至少先拿些東西走吧? RPG不都是要到處搜刮道具嗎?
背德的行為總是讓人感到興奮, 妁艷心裡燃起了火(?).
這個時候, 教室的燈竟然在一瞬間全部亮起.
妁艷在驚嚇之虞望了望四周, 四周竟然全是妹妹的同學. 密密麻麻, 門口也被封死了!
用不著說, 她們全部都中了魔法, 用奇怪的眼神看著妁艷!
這時, 妁艷瞭解了自己現在的處境------他被包圍了!!!
同學們站在原地看著妁艷.
"葛格, 呵呵呵, 大家快看, 這裡有一個可愛的葛格喔~♥"
"哈~呵~哈~呵~哈~♥"
"葛格, 還站在哪裡做什麼? 快來這裡啊…, 我會溫柔地告訴葛格妹妹在哪喔♥"
"我的名字..."
雖然沒有直接的攻擊, 但這些話對妁艷似乎具有混亂效果, 就像神奇寶貝中的超音波!
"不!!!不行!!!再這樣下去我會失去理智啊~~~", 妁艷道.
妁艷決定拔劍而戰, 他將武器裝上了增強貫穿性的套件, 準備快速解決所有敵人.
戰場的狀況如下(以下題目敘述開始):
(1) 妁艷被包圍在中央, 外圍都是妹妹的同學(敵人).
(2) 武器威力很強, 並且具有貫穿性, 攻擊一個特定方位, 被攻擊到的敵人都會倒地顫抖進入無法戰鬥的狀態.
(3) 武器的僵硬時間(CD)很大, 所以妁艷必須使用武器最少次來擊倒所有敵人.
(4) 由於敵人的位置有近有遠, 在視覺上有的比較大有的比較小.
(5) 妁艷將自己的四面八方平分成0~L-1的L個角度單位, 並快速掌握了每個敵人所占的方位(一個區間).
(6) 武器必須攻擊到敵人的內點(interior)才會有效果, 擦到邊邊(boundary)無效.
快幫助妁艷算出如何有效利用武器, 以最少攻擊次數擊倒所有敵人吧.
第一行有兩個數字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).
輸出唯一個數字, 代表至少要發射幾發才能擊倒所有敵人(不一定要往整數點方向發射).
灰線是角度等分點, 黑線是妹妹同學.
妁艷發射2發(紅線)在2.5和7.5即可攻擊到所有敵人的內點.
原TIOJ1755 / problem setter: willyliu.
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 |