아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

고속도로 요금소

시간 제한6초메모리 제한128 MB

요약
정렬된 진입점 위치가 주어질 때 연속된 요금소 사이에 진입점이 하나씩 들어가도록 등간격 요금소를 배치할 수 있는 최소와 최대 간격을 기약분수로 구합니다.
난이도

어려움10점 중 8점

유형
수학, 기하, 이분 탐색
정답자
아직 제출이 없습니다

문제

오토바이트사는 바이트랜드의 고속도로 하나를 짓고 있다. 얼마 전까지 이 회사는 고속도로 시작점에서만 통행료를 받았고, 그래서 운전자가 내는 금액은 바이트마일로 잰 주행 거리와 상관이 없었다. 새 회장 바이트아사르는 고속도로 전 구간에 요금소를 세우기로 했다.

바이트아사르는 고속도로를 달리면서 자동차 주행 거리계로 진입로 nn개의 위치를 모두 적어 두었다. 진입로의 위치는 고속도로 시작점에서 그 진입로까지의 거리다. 회사는 요금소 n+1n+1개를 일정한 간격으로 세운다. 즉 이웃한 두 요금소 사이의 거리가 어디서나 같다. 또 이웃한 두 요금소 사이에는 진입로가 있어야 하고, 이웃한 두 진입로 사이에는 요금소가 있어야 한다. 바이트아사르가 적어 둔 위치는 이런 배치를 허용한다.

정확히 말하면, 첫 요금소의 위치 b0b_0가 존재해서 나머지 요금소가 b0+ℓb_0 + \ell, b0+2ℓb_0 + 2\ell, ..., b0+nℓb_0 + n\ell에 놓이고 jj번째 진입로가

b0+(j−1)ℓ≤aj≤b0+jℓb_0 + (j-1)\ell \le a_j \le b_0 + j\ell

을 만족하는 간격 ℓ\ell을 찾는다. 요금소가 진입로와 정확히 같은 위치에 놓일 수도 있다. 이때는 진입로 바로 앞이나 바로 뒤에 요금소를 세우므로 위 구간은 양 끝을 포함한다.

가능한 간격 ℓ\ell의 최솟값과 최댓값을 구하라.

입력

첫째 줄에 진입로의 개수 nn이 주어진다. (3≤n≤1063 \le n \le 10^6)

둘째 줄에 진입로의 위치 a1<a2<⋯<ana_1 < a_2 < \dots < a_n이 증가하는 순서로 주어진다. (0≤ai≤1090 \le a_i \le 10^9)

주어지는 위치는 항상 조건을 만족하는 배치를 하나 이상 허용하고, 간격의 최솟값과 최댓값은 10−910^{-9} 이상 차이가 난다.

출력

이웃한 두 요금소 사이 거리의 최솟값과 최댓값을 이 순서대로 한 줄에 공백 하나로 구분해 출력한다.

두 답은 모두 유리수다. 각 답을 기약분수 p/q 꼴로 정확하게 출력한다. q>0q > 0이고 gcd⁡(p,q)=1\gcd(p, q) = 1이다. 분모가 11이어도 분모를 적는다. 간격이 33이면 3/1로 출력한다.

예제2

  1. 예제 1

    입력
    6
    2 3 4 5 6 7
    
    예상 출력
    5/6 5/4
    
  2. 예제 2

    입력
    3
    0 1 2
    
    예상 출력
    2/3 2/1