#PU998. USACO 2020 January Contest, Platinum — Problem 3. Falling Portals
USACO 2020 January Contest, Platinum — Problem 3. Falling Portals
USACO 2020 January Contest, Platinum — Problem 3. Falling Portals
题目描述
There are () worlds, each with a portal. Initially, world (for ) is at -coordinate , and -coordinate (). There is also a cow on each world. At time , all -coordinates are distinct and the worlds start falling: world moves continuously in the negative- direction at a speed of units per second. At any time when two worlds are at the same -coordinate (possibly a fractional time), the portals "align", meaning that a cow on one of the worlds can choose to travel instantaneously to the other world. For each , the cow on world wants to travel to world (). Help each cow determine how long her journey will take, if she travels optimally. Each query output should be a fraction where and are positive and relatively prime integers, or if it the journey is impossible.
输入格式
The first line of input contains a single integer The next line contains space-separated integers The next line contains space-separated integers
输出格式
Print lines, the -th of which contains the journey length for cow
数据范围
Test cases 2-3 satisfy Test cases 4-5 satisfy Test cases 6-14 satisfy no additional constraints.
样例
样例 1
4
3 5 10 2
3 3 2 1
7/2
7/2
5/1
-1
Consider the answer for the cow originally on world 2. At time $2$ worlds 1 and
2 align, so the cow can travel to world 1. At time $\frac{7}{2}$ worlds 1 and 3
align, so the cow can travel to world 3.
Problem credits: Dhruv Rohatgi