| ENG RUS | Timus Online Judge |
1829. Routing TablesTime limit: 2.0 second Memory limit: 64 MB Routers are special devices used to forward data packets in modern computer
networks. The behavior of a router is defined by a routing table. This table
consists of several lines each of which contains the IP address of a
destination network d, a mask m, and the IP address of a gateway g. For
example, the line “192.168.24.0 255.255.255.0 192.168.14.1” means that a
packet addressed to network 192.168.24.0 with mask 255.255.255.0 should
be forwarded through gateway 192.168.14.1.
An IP address is a 32-bit integer, which is divided
for convenience into four bytes. The value of each byte is written in decimal
notation and these values are separated by dots. For example, the notation
192.168.24.0 means the binary number 11000000101010000001100000000000.
Masks are written similarly; moreover, the binary representation of a mask is
started with ones only, which are followed by zeros only.
The algorithm of choosing a route is as follows. Consider a packet sent to
address a. The router selects form the table all the lines satisfying the
condition d and m = a and m (`and' is the bitwise AND operation). A line
with the maximal number of ones in the mask is then chosen from these lines and
the packet is sent to the gateway specified in this line. It is guaranteed that
there is at most one such line for any destination address.
Two routing tables are equivalent if a packet with any destination address will be sent to
the same gateway (or will not be sent at all) according to these tables. The following
routing tables are equivalent:
InputThe first line contains the number of lines in the first routing table.
This table is given in the following lines in the
format described above. Then follows the second routing table in the same format.
The total number of lines in these tables doesn't exceed 65536. OutputIf the tables are equivalent, output “YES”. Otherwise, output “NO”. Samples
Problem Author: Igor Andrianov Problem Source: XII USU Open Personal Contest (March 19, 2011) Tags: none |