4561 . 貳零貳參建北電資演算法小社賽 pA - Access Point
TopCoder
Tags
Description
我們風雨下的棲息地 靈魂的歸宿 的網路被封殺了!!!
這對所有人來說都是個天大的災難
如果沒有網路 社辦就不會有人
一個靠凝聚力組成的溫暖的大家庭就要沒了！
所以
有些人自願跳出來街上乙太網路
作為一個access point
將網路二次分享 三次分享給其他人
已知現在共n台裝置願意進行分享
其中第i台裝置的網路來源為 $a_i$
若$a_i$為零則代表他接上了有網路的網路交換器
aka dgs-1210
因為水獺對他施了神奇魔法
能連上他的裝置數量沒有上限
每台裝置依據其性能不同能夠分享給$b_i$個裝置使用
請計算在此情況下社辦能有幾台裝置使用網路服務
請注意就算一個裝置無法共享網路，其仍能連接他人所分享之網路
計算共有幾台裝置能使用網路服務時，請考慮其所有已經被接上的連接口與未接上之接口
且保證已經連上網路的人不會再次嘗試連網
此外，當一台正在分享網路的裝置的接口皆被接完時
如果有人還想接上去，試圖接上去把別人擠掉
請昭告此則惡行，並輸出
${name} wanna steal internet
並且顯然他不會獲得網路的使用權
Input Format
$N \ Q$
$name_1 \ num_1 \ a_1 \ b_1$
$name_2 \ num_2 \ a_2 \ b_2$
...
$name_Q \ num_Q \ a_Q \ b_Q$
其中
$0 \le Q \le N \le 5*10 ^ 6$
$0 \lt num, a_i \le N$
$N$為可分享網路的裝置的數量
共有 $Q$ 次操作 每次操作代表一個人依序嘗試聯網 他並不一定會成功
不得任意更改操作順序
$name$ 為這個裝置的使用者的名字
$num$ 為這個使用者的代號
$a_i \ b_i$ 同題目所述
Output Format
對於每次非法連接
輸出 ${name} wanna steal internet
並於最後輸出所以包括分享中的裝置能夠使用網路服務的裝置數量
Sample Input 1
otter 2 0 1
807 6 2 3
cjtsai 4 2 1
yoyo 9 6 3
Cc 5 6 2
willy 10 5 3
bclai 1 9 1
hehehe 3 10 3
starhuey 8 9 2
jimmy 7 6 3
Sample Output 1
22
Hints
對於第一筆範測
1. otter連上了交換器並放出了1個可連接的空位
2. 807接上了otter的裝置並放出3個空位，並佔掉otter放出的空位
3. cjtsai嘗試接上otter的裝置，但那個位置已經被807佔走了，所以輸出'cjtsai wanna steal internet'
4. yoyo接上了807的裝置並放出3個空位，並佔掉807放出的空位之一
5. Cc接上了807的裝置並放出2個空位，並佔掉807放出的空位之一
6. willy接上了Cc的裝置並放出3個空位，並佔掉Cc放出的空位之一
7. bclai接上了yoyo的裝置並放出1個空位，並佔掉yoyo放出的空位之一
8. hehehe接上了willy的裝置並放出3個空位，並佔掉willy放出的空位之一
9. starhuey接上了yoyo的裝置並放出2個空位，並佔掉yoyo放出的空位之一
10. jimmy接上了Cc的裝置並放出3個空位，並佔掉Cc放出的空位
共有9個裝置正在分享網路
所剩下的空間分別為
otter: 1-1=0
807: 3-2=1
yoyo: 3-2=1
Cc: 2-2=0
willy: 3-1=2
bclai: 1-0=1
hehehe: 3-0=3
starhuey: 2-0=2
jimmy: 3-0=3
0+1+1+0+2+1+3+2+3+9=22
Problem Source
為什麼大家不都接上交換器就好？
因為要接上交換器只能使用有線連接啊
畢竟網管中心可是封禁了社辦內所有透過router的無線連接呢
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $a_i = 0$ | 10 |
| 2 | 10~19 | $b_i=N$ | 13 |
| 3 | 20~29 | $N \le 1000$ | 27 |
| 4 | 0~39 | 無其他限制 | 50 |