친구만들기 timer 1s memory 64MB

길이가 L 인 도로와 N 명의 사람이 있다. i = 1, 2, ... , N 일 때 i 번째 사람은 T_i 시각에 길의 시작지점을 출발하여 Vⁱ 라는 일정한 속도로 길의 끝 지점을 향하여 걸어간다. 어떠한 두 사람도 같은 시각에 출발하지 않으며, 어떠한 두 사람도 같은 시각에 끝 지점에 도착하지 않는다.

i 번째 사람과 j 번째 사람이 길에서 만나게 되면 두 사람은 친구가 된다. 수학적으로 두 사람의 출발 시각이 T_i < T_j 이고 L / V_i + T_i > L / V_j + T_j 이면 “두 사람은 친구가 된다.” 라고 한다.

여러분이 해야 할 일은 서로 서로가 친구가 되는 여러 집합들 중에서 구성원의 수가 최대인 집합의 구성원 수를 구하는 프로그램을 작성하는 것이다.

예 1> L = 1000 이고 4명의 사람이 있는데 T₁ = 0, T₂ = 1, T₃ = 2, T₄ = 4 이고 V_<1 = 2, V₂ = 3, V₃ = 1, V₄ = 4 라고 하자.

여기서 첫 번째 사람과 두 번째 사람은 0 < 1 이고 1000 / 2 + 0 > 1000/3 + 1 이므로 친구가 된다. 이렇게 모든 사람 사이에 대하여 계산하면 아래와 같은 표를 얻을 수 있다.

따라서 첫 번째, 두 번째, 네 번째 사람은 서로 서로 친구가 되고 구성원의 수가 3으로서 최대가 된다. 세 번째, 네 번째 사람도 친구가 되지만 구성원의 수가 2 이므로 최대가 될 수 없다.

예 1> 또 다른 경우를 보자. L = 1000 이고 4명의 사람이 있으며 T₁ = 0, T₂ = 1, T₃ = 2, T₄ = 4 이고 V₁ = 1, V₂ = 1, V₃ = 1, V₄ = 1 라고 하자. 이 경우에는 어느 두 사람도 만나지 않는다. 따라서 구하고자 하는 값은 1이 된다.