SP2153 IMATCH - Internet is Faulty

David 遇到了一个难题：他需要将一个大型文件从家里的电脑传输到公司工作的电脑上，文件的大小为 $S$ 千字节。 网络由 $N$ 台计算机组成，编号从 1 到 $N$。其中，David 家中的计算机编号为 1，公司用的计算机编号为 2。一些计算机之间通过各种类型的链接（如网线或 Wi-Fi）连接。有的链接可能是单向的（比如卫星链接），所以我们假定所有的链接都是单向传输。 数据以包的形式在网络中传输，每个包精确包含 1 千字节的数据。David 知道每条链接的可靠性，即数据包通过该链接成功传输的概率。我们假设，每次数据包的传输都是独立的，前一个包是否传输成功不会影响下一个包的传输概率。 由于网络环境不稳定，且公司用电脑可能距离家里电脑较远，即便选择了最佳传输路径，仍可能耗费较长时间。幸运的是，David 在网络中的某些计算机上有账户，他可以利用这些计算机作为临时存储，以缩短传输时间。 文件传输会被分解为多个步骤。在每个步骤中，David 会选择一条路径，这条路径从已经有文件的计算机出发，直到他拥有账户的另一台计算机。在数据传输前，文件被分成 $S$ 个包，然后包会被依次通过选定的路径发送。每个包成功到达目标计算机的概率为经过所有链接的概率的乘积。如果包丢失，会立即重发。无论发送是否成功，每次尝试发送一个包都需要准确 1 毫秒的时间，并且与路径长度无关。所有包传输完成后，David 可以从新的计算机发起接下来的传输，如此反复。 **本翻译由 AI 自动生成**

无

无