ZOJ Problem Set - 2356
A company named Outdaters is running a small computer wire line network, called Outernet. Not like Internet, Outernet is not base on the TCP/IP protocol. Due to lacking of money, not all the computers in Outernet can communicate with each other directly.
Outdaters have already found the solution. They created a protocol to make all computers in the network become application proxies. An application proxy can receive data from a connected computer and send them out to another connected computer. Therefore, by using this protocol in Outernet, if a computer wants to send something to a computer not linked directly, it has to send them to a connected computer/application proxy and ask it to help sending them to the destination or another connected computer/application proxy.
The protocol is described as
Application proxies use port to indicate each connected computer. Port number is an integer number from 0 to 32,767. To an application proxy, 0 means the application proxy itself, each other port number represents a unique computer connected to the application proxy.
The application proxy accepts only 3 commands, case sensitive: TO, DATA, QUIT.
To each incoming command, application proxy will response with 3-digit result code in a line to the incoming port after handled this command.
100: OK. No error/Data routed to destination
1. TO:<destination computer name><LF>
Possible result codes are:
2. DATA<LF><the data><a dot "."><LF>
Send <the data> to destination computer. <the data> will be regarded as a data stream, and sent to the destination without any alteration if the destination computer is not the application proxy itself. The backslash ("\") is the meta character, "\." means a simple dot ".", instead of then end indicator, and "\\" means "\".
Possible result codes are:
End this communication session.
Possible result codes are:
When a computer (the requester) sends a "TO" command to an application proxy, a communication session begins; when a "QUIT" command is sent to the application proxy, the session ends. In a session, the requester can send multiple "TO" and "DATA" commands to an application proxy to send out multiple messages.
An application proxy is able to handle sessions simultaneously from different ports.
D. Routing table
Each application proxy holds a routing table. It uses this table to find which port should be used the destination computer name. Each line in the routing table contains 2 fields, the first is the destination computer name, and the second is the outgoing port number. It means, the data to be sent to a computer with the destination computer name, will be sent out via the port with the outgoing port number. Port number 0 means, the data should be routed to the application running on this application proxy; that destination computer name is actually the application proxy's name.
Application proxies use the same "TO", "DATA", "QUIT" commands to route the incoming data if the routing is possible.
After searching on the routing table, if the outgoing port found, application proxies must create a complete session on the outgoing port for each valid incoming "TO" command: one "TO" command at the beginning, zero or more DATA commands to route the data, one "QUIT" command in the end if the incoming session ends or another incoming "TO" command is received.
Port 0 is handled as same as other outgoing ports except that no actually outgoing command is sent, i.e. all the commands�� result code will be sent to the incoming port, but no commands will be sent to any outgoing port.
Now, Outdaters hires you to write the engine to implement the protocol for the application proxy.
The input consists of a sequence of testcases. Each begins with a routing table of an application proxy and then the incoming requests of the application proxy.
A routing table includes, in order, a line with an integer M (1 <= M <= 32,768), the number of lines in the routing table; M lines, each of which has a routing line. Each routing line contains a unique destination computer name (1 to 15 alphanumeric characters in the routing table), and then the outgoing port number (0 to 32,767 integer), separated by a space, and the computer names are case sensitive.
The incoming requests of the application proxy include several request sessions from the connected computers. A line starts with a number sign "#" and then an integer P (-1, 1 to 32,767), means the following input is from port P, P<0 means the testcase finishes. The commands in request sessions will not be broken by the "#" lines. To simplify the input handling, data commands in our input file will just contain "0"-"9", "a"-"z", "A"-"Z", "@", "#", "_", "+", "-", "*", "/" , "\", "?", ",", "." and <LF>.
The input is terminated by a single zero
For each testcase, print all the outputs of the ports sending out data, in the order of the corresponding input. For each port��s output, a line starts with a number sign "#" and then an integer P (-1, 1 to 32,767), means the following commands are output in port P, P=-1 means the output of the current testcase finishes. Following the ��#�� line is the commands output in this port till another ��#�� line. A "#" line is needed only when the port number need to be changed.
Hint: <LF> means 0xa.
Source: Asia 2003, Guangzhou (Mainland China)