수화물

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

요약
길이 L인 원형 벨트에 가방이 떨어지는 위치가 주어질 때, 떨어지는 가방이 다른 가방과 1m 이내로 겹치지 않도록 하는 직선 벨트의 최대 속도를 기약분수로 구한다.
난이도

보통10점 중 7점

유형
수학, 정수론, 정렬, 구현
정답자
아직 제출이 없습니다

문제

상근이는 공항 수화물 찾는 곳에서 원형 컨베이어 벨트 위에 짐이 서로 부딪히지 않도록 짐을 올려놓는 일을 한다. 모든 짐은 직선 컨베이어 벨트를 타고 운반된 뒤 원형 컨베이어 벨트로 떨어진다. 상근이는 직선 컨베이어 벨트의 속도를 조절해 짐이 서로 충돌하지 않게 한다.

상근이는 직선 컨베이어 벨트의 속도를 하나로 고정해 둔 채 잠시 자리를 비우려 한다. 직선 컨베이어 벨트에는 센서가 있어 모든 짐의 위치를 알 수 있다. 짐이 서로 충돌하지 않는 직선 컨베이어 벨트의 최대 속도를 구하는 프로그램을 작성하시오.

원형 컨베이어 벨트는 길이가 LL이고 1 m/s1\text{ m/s}의 속도로 움직인다. 어떤 짐이 원형 컨베이어 벨트에 떨어지는 순간, 그 짐으로부터 벨트를 따라 1 m1\text{ m} 이내에 다른 짐이 있으면 두 짐은 충돌한다(거리가 정확히 1 m1\text{ m}이면 충돌하지 않는다). 벨트가 원형이므로 거리는 길이 LL을 따라 한 바퀴 돌아 잰다. 중간에 사람들이 짐을 집어갈 수도 있지만 어떤 짐을 가져가는지 알 수 없기 때문에, 짐을 가져가는 경우는 없다고 가정한다. 직선 컨베이어 벨트는 0.1 m/s0.1\text{ m/s} 이상 10 m/s10\text{ m/s} 이하의 속도로 움직일 수 있다.

입력

첫째 줄에 짐의 개수 NN과 원형 컨베이어 벨트의 길이 LL이 주어진다 (1≤N≤L≤10001 \le N \le L \le 1000). 둘째 줄에는 각 짐의 위치 xix_i가 미터 단위로 주어진다 (0≤xi≤10000 \le x_i \le 1000). 각 xix_i는 소수점 둘째 자리까지 주어진다.

출력

짐이 서로 충돌하지 않게 하는 직선 컨베이어 벨트의 최대 속도를 기약분수로 출력한다. 즉 최대 속도를 pq\dfrac{p}{q} 꼴의 기약분수로 나타내어, 분모 qq가 11이면 정수 pp만을, 그 외에는 p/q 형식으로 출력한다. 짐이 충돌하지 않는 속도가 존재하지 않으면 no fika를 출력한다.

예제2

  1. 예제 1

    입력
    2 3
    0.00 2.00
    
    예상 출력
    2
    
  2. 예제 2

    입력
    3 4
    0.05 1.00 3.50
    
    예상 출력
    1/2