파일 업로드

달리기 경주

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

유훈와 찬혁은 누가 더 빠른지 결정하기 위해 공원에서 경주를 하기로 결정했습니다.

두 사람은 동일한 위치에서 출발하여 동일한 방향으로 동시에 달리기 시작합니다. 두 사람의 진행 상황은 '구간'이라는 일련의 부분으로 설명되며, 각 구간 동안 일정한 속도로 달리게 됩니다. 예를 들어, 유훈은 3단위의 시간 동안 5의 속도로 달리고, 다음 6단위의 시간 동안 10의 속도로 달릴 수 있습니다. 유훈과 찬혁은 모두 동일한 총 시간 동안 달립니다.

두 사람은 경주 도중 선두 위치가 몇 번 바뀌는지 궁금합니다. 선두 교체는 한 주자가 다른 주자를 추월하여 경주에서 위치를 바꾸는 시점에 발생하는데, 예를 들어 찬혁이 앞서고 있다가 유훈이 추월하면 이것을 선두 위치 변경으로 생각합니다. 마찬가지로 유훈이 앞서고 있을 때, 찬혁이 따라잡아 동일한 속도로 달리다가 앞질러 나갈 때 선두 위치 변경으로 간주합니다.

💻 입력
  • 첫 번째 줄: 띄어쓰기로 구분된 두 정수, N과 M. (1 <= N, M <= 1000)
  • 두 번째 줄..1+N 번째 줄: 각 줄은 유훈의 달리기 구간 중 하나를 설명하며, 두 개의 정수로 구성된다: 유훈의 속도와 그 속도로 달리는 시간(둘 다 범위는 1..1000).
  • 2+N 번째 줄 ..1+N+M 번째 줄: 각 줄은 찬혁의 달리기 구간 중 하나를 설명하며, 두 개의 정수로 구성된다: 찬혁의 속도와 그 속도로 달리는 시간 (둘 다 범위는 1..1000).
🖨️ 출력
  • 첫 번째 줄: 경주 중 선두 교체 횟수.

💻 예제 입력 1
4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9
🖨️ 예제 출력 1
2

출처: USACO 2013 March Contest, Bronze Problem 1. Cow Race