레이팅 미적용누가 더 빠른 소인지를 둘러싼 오랜 논쟁을 마침내 매듭짓기 위해, 베시(Bessie)와 친구 엘시(Elsie)는 농장을 가로지르는 경주를 하기로 했다.
두 소는 같은 위치에서 출발하여 같은 시각에 같은 방향으로 달리기 시작한다. 각 소의 진행은 일련의 "구간"으로 표현되며, 각 구간 동안 소는 일정한 속도로 달린다. 예를 들어 베시는 3 단위 시간 동안 속도 5로 달린 뒤, 6 단위 시간 동안 속도 10으로 달릴 수 있다. 베시와 엘시는 같은 총시간 동안 달린다.
소들은 경주 동안 선두가 바뀐 횟수를 세는 데 당신의 도움을 받고 싶어 한다. 선두 교체는 소 A가 소 B를 앞지르는 시점에 일어나는데, 단 직전에 어느 소든 선두였던 마지막 순간의 선두가 소 B였던 경우이다. 예를 들어 B가 선두였다가 A가 앞서 나가면 이는 선두 교체이다. B가 선두였다가 A가 한동안 B와 나란히 달린 뒤 마침내 앞서 나가는 경우도 선두 교체로 센다.
첫째 줄: 공백으로 구분된 두 정수 N과 M. (1 <= N, M <= 1000)
둘째 줄부터 1+N번째 줄까지: 각 줄에 베시의 달리기의 N개 구간 중 하나가 두 정수로 주어진다. 베시의 속도와 그 속도로 달리는 시간이다 (두 정수 모두 1..1000 범위).
2+N번째 줄부터 1+N+M번째 줄까지: 각 줄에 엘시의 달리기의 M개 구간 중 하나가 같은 형식으로 주어진다.
경주 동안 선두가 바뀐 횟수.
cowrace.in · 출력을 쓸 파일 cowrace.out4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 92Output details: Elsie is ahead until time t=3, when both cows meet. Bessie then pulls ahead briefly (first leadership change), only to be overtaken by Elsie (second leadership change).