编程介的小学生 2019-09-14 02:41 采纳率: 20.5%
浏览 102

Outernet 网络的算法问题

Description

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
A. Port
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.

B. Commands
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.
Format:
xxx< LF > xxx -- the 3-digit result code
Result codes:
100: OK. No error/Data routed to destination
101: OK. Data routed to application. (Destination computer is application proxy itself.)
200: Session ends (Response to QUIT command)
300: Unknown command
301: Unknown destination
302: No session began
303: Looping not allowed (when incoming port = outgoing port)

Details for each command:
1. TO:< destination computer name >< LF >
Tell the application proxy, the following data need to be sent to < destination computer name > ,and cancel the last "TO" command's effect (send a "QUIT" command to the original destination computer). If TO command fails (result code is neither 100 nor 101), the state of the application proxy will not be changed.
Possible result codes are:
100: The destination computer is found in routing table, and not the application proxy itself.
101: The destination computer is found in routing table, and IS the application proxy itself.
301: The destination computer is not found in routing table
303: The destination computer is found in routing table, but incoming port = outgoing port

  1. 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:
    100: The destination computer is found in routing table, and not the application proxy itself. The data is routed to the corresponding outgoing port.
    101: The destination computer is found in routing table, and IS the application proxy itself.The data is routed to the application running on this application proxy.
    302: No session began, this command is ignored.

  2. QUIT< LF >
    End this communication session.
    Possible result codes are:
    200: Session ends(Response to QUIT command)
    302: No session began, this command is ignored.

C. Session
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.

E. Routing
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.
Input

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
Output

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.
#< port number >< LF >
the commands output in this port
#< another port number >< LF >
the commands output in this port
...
#-1< LF >
Sample Input

5
RED 0
YELLOW 1
GREEN 2
BLUE 3
WHITE 3
#1
TO:GREEN
DATA
HELLO
.
#4
TO:WHITE
#1
Quit
QUIT
#2
TO:GREEN
DATA
A JOKE to myself
.
QUIT
#3
TO:ORANGE
QUIT
#4
QUIT
#-1
0
Sample Output

#2
TO:GREEN
#1
100
#2
DATA
HELLO
.
#1
100
#3
TO:WHITE
#4
100
#1
300
#2
QUIT
#1
200
#2
303
302
302
#3
301
302
QUIT
#4
200

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 matlab图像高斯低通滤波
    • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
    • ¥15 钢筋实图交点识别,机器视觉代码
    • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
    • ¥50 400g qsfp 光模块iphy方案
    • ¥15 两块ADC0804用proteus仿真时,出现异常
    • ¥15 关于风控系统,如何去选择
    • ¥15 这款软件是什么?需要能满足我的需求
    • ¥15 SpringSecurityOauth2登陆前后request不一致
    • ¥15 禅道二次开发编辑版本,上传不了发行包