P16598 [SYSUCPC 2025] Network

Computer Networks is a very important course in computer science. Suppose there are two machines, A and B, that need to transmit data through a chain-like network formed by $n-1$ routers. Specifically, when machine A wants to send data to machine B, it first sends the data to router 1, which then forwards it to router 2, router 2 forwards it to router 3, and so on, until router $n-1$ finally forwards the data to machine B. Now, machine A needs to send $K$ bits of data to machine B. It first divides the data into $m$ groups, where the size of each group is $l_i$, satisfying $\sum l_i=K$. These groups are pushed to router 1 in the order of $l_1,l_2,...,l_m$. The push rate of machine A is $r_0$ bit/s, the push rate of router 1 is $r_1$bit/s, ..., and the push rate of router $n-1$ is $r_{n-1}$bit/s. The routers forward data in units of groups. When a router receives bits from a group, it waits until all bits of that group have arrived before starting to push the group to the next router. The forwarding strategy of the routers is first-come-first-served. While a router is forwarding data from one group, data from other groups is stored in the router's buffer, waiting to be forwarded. Assume that once a router or machine pushes a bit, the bit immediately arrives at the next router or machine. The question is: starting from the time when machine A pushes the first bit, at what time will machine B completely receive all $K$ bits of data sent by machine A?

The first line contains three positive integers $n(1 \leq n \leq 10^5), m(1 \leq m \leq 3\times 10^5), K(1\leq K\leq 3\times 10^5)$, which represent that the communication between machine A and machine B passes through $n-1$ routers, machine A divides the data to be transmitted to B into $m$ groups, and the total number of bits of data that machine A wishes to transmit to B is $K$, respectively. The second line contains $n$ positive integers. The first integer is $r_0(1\leq r_0\leq 10^9)$, representing the push rate (in bit/s) of machine A. The following $n-1$ integers are $r_i(1\leq r_i\leq 10^9)$, where the $i$-th integer represents the push rate (in bit/s) of the $i$-th router. The third line contains $m$ positive integers. The $i$-th integer is $l_i(1\leq l_i\leq K)$, representing the number of bits in the $i$-th group. It is guaranteed that $\sum l_i=K$.

A real number, in seconds, representing the time from when machine A pushes the first bit until machine B completely receives the entire $K$ bits of data that machine A intends to transmit to B. Suppose your answer is $Your\_Answer$ and the standard answer is $Answer$. If either $\frac{|Your\_Answer−Answer|}{Answer}\leq 10^{−9}$ or $|Your\_Answer−Answer|\leq10^{−9}$ is satisfied, then your answer is considered correct.

The data link is: A $\to$ Router 1 $\to$ B, where the push rate of A is 2 bit/s, and the push rate of Router 1 is 1 bit/s. A intends to transmit 3 bits of data to B. Before sending, A divides the data into two groups, with lengths of 1 bit and 2 bits, respectively. A first pushes the group of length 1, followed by the group of length 2. The second group is completely pushed to Router 1 after waiting for $\frac{1+2}{2}=1.5$ seconds. Since the first group completely arrives at Router 1 after waiting for $\frac{1}{2}=0.5$ seconds (i.e., the time for A to push it), and Router 1 takes $\frac{1}{1}=1$ second to completely push out the first group after fully receiving it, the second group arrives at Router 1 exactly when the first group is completely pushed out from Router 1. Thus, the second group does not need to queue at Router 1 and can be pushed out immediately. Therefore, the answer is $\frac{2+1}{2}+\frac{2}{1}=3.5$ seconds.