POJ 2799 - IP Networks

http://poj.org/problem?id=2799

概要

m 個の IPv4 アドレスが与えられるので，それらからなるサブネットワークのネットワークアドレスとサブネットマスクを答える．

制約

• m <= 1000

解法

サブネットマスクは高々33通りしかないので全通り試した．

 1 #include <iostream>
 2 #include <sstream>
 3 #include <limits>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 string show(unsigned u)
 8 {
 9   ostringstream oss;
10   oss << ((u>>24)&0xFF) << "." << ((u>>16)&0xFF) << "." << ((u>>8)&0xFF) << "." << (u&0xFF);
11   return oss.str();
12 }
13 
14 int main()
15 {
16   int M;
17   cin >> M;
18   unsigned l = numeric_limits<unsigned>::max();
19   unsigned h = 0;
20   for (int i = 0; i < M; i++) {
21     unsigned a, b, c, d;
22     char e;
23     cin >> a >> e >> b >> e >> c >> e >> d;
24     const unsigned f = (a<<24) | (b<<16) | (c<<8) | d;
25     l = min(l, f);
26     h = max(h, f);
27   }
28 
29   unsigned m;
30   for (int n = 0; n <= 32; n++) {
31     m = ~((1ULL<<n)-1U);
32     if ((l & m) == (h & m)) {
33       break;
34     }
35   }
36 
37   cout << show(l & m) << endl;
38   cout << show(m) << endl;
39   return 0;
40 }