실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
총 () 개의 세계가 있고, 각 세계에는 포털이 있습니다.
처음에는 번째 세계(단, )는 좌표가 위치이고, 좌표가 () 입니다.
또한 각 세계에는 사람이 있습니다. 시간이 일 때, 모든 좌표는 서로 다르며 세계들이 멀어지기 시작합니다 : 세계 는 매 초마다 단위로 음의 방향으로 지속적으로 움직입니다.
두 세계가 같은 좌표에 도달하는 어떤 시점에서(소수 시간일 수 있습니다) 포털들이 '정렬'되는데, 이는 한 세계의 사람이 순간적으로 다른 세계로 이동할 수 있음을 의미합니다.
각 번째에 대하여, 세계 의 사람이 세계 로 () 이동하려고 합니다.
각 사람이 최적으로 이동한다면 그 여정이 얼마나 걸리는지 알려주세요.
각 쿼리 출력은 분수 형태로 나와야 하는데, 여기서 와 는 서로소인 양수이거나, 여정이 불가능한 경우 이어야 합니다.
첫 번째 입력 줄에는 하나의 정수 이 주어집니다.
다음 줄에는 개의 공백으로 구분된 정수 을 입력합니다.
다음 줄에는 개의 공백으로 구분된 정수 을 입력합니다.
줄을 출력합니다, -번째 줄에는 사람 에 대한 여행 시간이 출력됩니다.
4 3 5 10 2 3 3 2 1
7/2 7/2 5/1 -1
원래 세계 2에 있던 사람에 대한 답을 고려하여 봅시다.
시간이 일 때, 세계 1과 2가 정렬되므로 사람은 세계 1로 이동할 수 있습니다.
시간이 일 때, 세계 1과 3이 정렬되므로 사람은 세계 3으로 이동할 수 있습니다.
출처: USACO 2020 January Contest, Platinum Problem 3. Falling Portals