1998 . 網路遮罩

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

87.0% (60/69)

Submission's AC Ratio

33.3% (104/312)

Tags

CKcon 2017-CKcon-fin implementation sorting

Description

網路遮罩 (subnet mask) 是在讀網路概論時，會學到的東西。在這裡就稍微介紹一下「網路遮罩」。

網路遮罩的格式是 A.B.C.D/N。A,B,C,D的範圍是在0∼255，而N的範圍是在1∼32。A.B.C.D是IPv4位址，N是遮罩的長度。每一個網路遮罩都會包含一段IP的區間。

例如 192.168.0.1/24 就是一個網路遮罩，那要如何算這個網路遮罩的位址區間呢?

先將IP寫成2進位：11000000 10101000 00000000 00000001
接下來固定前N位：11000000 10101000 00000000 ********

所以 192.168.0.1/24 所包含的IP只要是上面這行的格式就好，換句話說就是 192.168.0.0∼192.168.0.255 這個區間的IP。

有一天，一位網管人員要設計防火牆，但因為他數學不好，所以請你幫忙算一些資料。

這位網管人員會給你M個網路遮罩，接著再給你N個IP，問你每個IP是否有包含在這些網路遮罩中。

Input Format

第一行包含兩個正整數M,N，M代表網路遮罩的數量，N代表IP的數量。
接著有M行，每行有一個網路遮罩。
再來有N行，每行有一個IP。

對於所有測資，M≤2×105,N≤3×105

子任務（測資） 額外限制 分數
1 (0~5) M≤2×103,N≤3×103 41
2 (0~10) 無 59

Output Format

針對每筆IP，如果包含在網路遮罩裡，輸出TRUE。
否則輸出FALSE。

Sample Input 1

1 3
140.112.8.8/19
140.112.30.42
140.112.30.43
140.118.31.215

Sample Output 1

TRUE
TRUE
FALSE

Hints

每一個網路遮罩都是一個區間。

Problem Source

Problem Set by Ting.H
建國中學106學年度校隊選拔：複試pB

Subtasks

No. Testdata Range Score
1 0~5 41
2 0~10 59

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 131072 262144 1 2
1 900 131072 262144 1 2
2 900 131072 262144 1 2
3 900 131072 262144 1 2
4 900 131072 262144 1 2
5 900 131072 262144 1 2
6 1900 131072 262144 2
7 1900 131072 262144 2
8 1900 131072 262144 2
9 1900 131072 262144 2
10 1900 131072 262144 2
Submit
Back to Top