codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

291C.md (2860B)


      1 Source: https://codeforces.com/problemset/problem/291/C
      2 
      3 C. Network Mask
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 The problem uses a simplified TCP/IP address model, please make sure you've read the statement attentively.
     22 
     23 Polycarpus has found a job, he is a system administrator. One day he came across *n* IP addresses. Each IP address is a 32 bit number, represented as a group of four 8-bit numbers (without leading zeroes), separated by dots. For example, the record 0.255.1.123 shows a correct IP address and records 0.256.1.123 and 0.255.1.01 do not. In this problem an arbitrary group of four 8-bit numbers is a correct IP address.
     24 
     25 Having worked as an administrator for some time, Polycarpus learned that if you know the IP address, you can use the subnet mask to get the address of the network that has this IP addess.
     26 
     27 The subnet mask is an IP address that has the following property: if we write this IP address as a 32 bit string, that it is representable as "11...11000..000". In other words, the subnet mask first has one or more one bits, and then one or more zero bits (overall there are 32 bits). For example, the IP address 2.0.0.0 is not a correct subnet mask as its 32-bit record looks as 00000010000000000000000000000000.
     28 
     29 To get the network address of the IP address, you need to perform the operation of the bitwise "and" of the IP address and the subnet mask. For example, if the subnet mask is 255.192.0.0, and the IP address is 192.168.1.2, then the network address equals 192.128.0.0. In the bitwise "and" the result has a bit that equals 1 if and only if both operands have corresponding bits equal to one.
     30 
     31 Now Polycarpus wants to find all networks to which his IP addresses belong. Unfortunately, Polycarpus lost subnet mask. Fortunately, Polycarpus remembers that his IP addresses belonged to exactly *k* distinct networks. Help Polycarpus find the subnet mask, such that his IP addresses will belong to exactly *k* distinct networks. If there are several such subnet masks, find the one whose bit record contains the least number of ones. If such subnet mask do not exist, say so.
     32 
     33 Input
     34 
     35 The first line contains two integers, *n* and *k* (1 ≤ *k* ≤ *n* ≤ 105) — the number of IP addresses and networks. The next *n* lines contain the IP addresses. It is guaranteed that all IP addresses are distinct.
     36 
     37 Output
     38 
     39 In a single line print the IP address of the subnet mask in the format that is described in the statement, if the required subnet mask exists. Otherwise, print -1.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 5 3  
     47 0.0.0.1  
     48 0.1.1.2  
     49 0.0.2.1  
     50 0.1.1.0  
     51 0.0.2.3
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 255.255.254.0
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 5 2  
     64 0.0.0.1  
     65 0.1.1.2  
     66 0.0.2.1  
     67 0.1.1.0  
     68 0.0.2.3
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 255.255.0.0
     75 ```
     76 
     77 Input
     78 
     79 ```
     80 2 1  
     81 255.0.0.1  
     82 0.0.0.2
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 -1
     89 ```