하이킹하는 사슴

Herbert Hooves 사슴은 자신이 가장 좋아하는 원형 산책로를 도를 기준으로 시계 방향으로 한 바퀴 도는 하이킹을 떠나려 한다. Herbert는 자신의 속도를 완벽하게 제어할 수 있으며, 속도는 언제든 임의의 음이 아닌 값(반드시 정수일 필요는 없음)이 될 수 있다. 그는 원할 때마다 순간적으로 속도를 바꿀 수 있다. Herbert가 출발점에 다시 도달하면 하이킹이 끝난다.

이 산책로는 사람인 하이커들도 이용하며, 이들 역시 산책로를 시계 방향으로 걷는다. 각 하이커는 출발점이 있으며 자신만의 일정한 속도로 이동한다. 사람들은 산책로를 영원히 계속해서 돈다.

Herbert는 사람을 무서워하는 겁 많은 사슴이다. 그는 하이커와 조우하는 것을 싫어한다. Herbert와 하이커가 정확히 같은 시각에 정확히 같은 장소에 있을 때마다 조우가 발생한다. Herbert와 하이커들은 원의 둘레 위에 있는 점으로 간주해야 한다.

Herbert는 같은 하이커와 서로 별개인 조우를 여러 번 할 수 있다.

같은 순간에 두 명 이상의 하이커와 조우하면, 모두 별개의 조우로 센다.

Herbert가 하이킹을 마치는 바로 그 순간의 조우도 여전히 조우로 센다.

Herbert가 하이커와 조우한 뒤 자신의 속도를 그 하이커의 속도와 정확히 같게 바꾸고 함께 따라간다면, 조우가 무한히 많이 발생할 것이다! 물론 그는 절대로 이렇게 해서는 안 된다.

조우는 하이커들의 행동을 바꾸지 않으며, 하이커끼리 조우할 때는 아무 일도 일어나지 않는다.

Herbert는 각 하이커의 출발 위치와 속도를 알고 있다. 그가 하이커들과 조우할 수 있는 최소 횟수는 얼마인가?

이 문제 풀기

일반적으로 Google Code Jam 문제에는 1 소형 입력과 1 대형 입력이 있다. 이 문제에는 2개의 소형 입력과 1개의 대형 입력이 있다. 두 번째 소형 입력을 시도하려면 먼저 첫 번째 소형 입력을 해결해야 한다. 평소와 마찬가지로 소형 입력에는 시간 페널티를 받고 다시 시도할 수 있다. 두 소형 입력을 모두 해결하면 대형 입력을 다운로드할 수 있다. 평소와 마찬가지로 대형 입력에는 단 한 번만 도전할 수 있다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $D_{i}$ ≤ 359. 1 ≤ N ≤ 1000. 1 ≤ $H_{i}$. 1 ≤ $M_{i}$ ≤ $10^{9}$. (이는 각 그룹에서 가장 빠른 하이커가 한 바퀴를 도는 데 필요한 시간에만 상한을 둔다는 점에 유의한다. 그룹에서 더 느린 하이커들은 더 오래 걸린다.)

소형 데이터 세트 1

시간 제한: 240초. 각 테스트 케이스의 전체 하이커 수는 2을 초과하지 않는다.

소형 데이터 세트 2

시간 제한: 240초. 각 테스트 케이스의 전체 하이커 수는 10을 초과하지 않는다.

대형 데이터 세트

시간 제한: 480초. 각 테스트 케이스의 전체 하이커 수는 500000을 초과하지 않는다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N이 있는 한 줄로 시작하며, 이어지는 N개의 줄은 각각 산책로의 같은 위치에서 출발하는 하이커 그룹 하나를 나타낸다. 이 중 i번째 줄에는 공백으로 구분된 세 정수가 주어진다. 출발 위치 $D_{i}$(사슴의 출발점에서 산책로를 따라 $D_{i}$/360만큼 이동한 지점을 나타냄), 그룹의 하이커 수 $H_{i}$, 그리고 그 그룹에서 가장 빠른 하이커가 원을 완전히 한 바퀴 돌 때마다 걸리는 시간(분)인 $M_{i}$이다. 그 그룹의 다른 하이커들은 각각 $M_{i}$+1, $M_{i}$+2, ..., $M_{i}$+$H_{i}$-1분에 한 바퀴를 돈다. 예를 들어 다음 줄은

180 3 4

세 명의 하이커가 사슴의 출발점에서 산책로의 절반만큼 떨어진 곳에서 출발하며, 산책로를 완전히 한 바퀴 돌 때마다 각각 4, 5, 6분이 걸린다는 뜻이다.

Herbert는 항상 위치 0(원을 따라 0/360만큼 이동한 지점)에서 출발하며, 어떤 하이커 그룹도 그곳에서 출발하지 않는다. 여러 하이커 그룹이 같은 장소에서 출발할 수 있지만, 같은 장소에서 출발하면서 속도도 같은 두 하이커는 없다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 사슴이 하이커들과 조우할 수 있는 최소 횟수이다.

케이스 #1에서는 모든 하이커가 우연히 같은 속도로 이동하며, Herbert가 그 누구와도 조우하지 않는 한 가지 방법은 그들과 정확히 같은 속도로 이동하는 것이다.

케이스 #2에서는 두 번째 하이커가 첫 번째 하이커보다 훨씬 빠르게 이동한다. Herbert가 첫 번째 하이커를 추월하지 않을 만큼 느리게 이동하면 빠른 두 번째 하이커와 여러 번 조우하게 된다. Herbert의 최적 전략 중 하나는 두 번째 하이커와 정확히 같은 속도로 이동하여 첫 번째 하이커와 한 번 조우하고 두 번째 하이커와는 전혀 조우하지 않는 것이다.

케이스 #3에서는 두 하이커가 같은 장소에서 출발하지만, 한 명은 다른 한 명보다 두 배 빠르다. 최적 전략 중 하나는 Herbert가 느린 하이커를 추월하지 않으면서 즉시 따라잡고, 그 하이커가 사슴의 출발 위치를 지날 때까지 바로 뒤에서 따라간 다음, 빠른 하이커가 Herbert를 따라잡기 전에 재빨리 하이킹을 마치는 것이다.