레이팅 미적용설명
무한히 긴 1차선 트랙에서 N마리의 소가 조깅을 하고 있다 (1 <= N <= 100,000). 각 소는 서로 다른 위치에서 출발하며, 소마다 조깅 속도가 다를 수 있다. 차선이 하나뿐이라 소들은 서로를 추월할 수 없다. 더 빠른 소가 다른 소를 따라잡으면 속도를 늦추고 같은 그룹의 일원이 된다.
소들은 T분 동안 달린다 (1 <= T <= 1,000,000,000). 이 시점에 몇 개의 그룹이 남아 있을지 농부 존이 알 수 있도록 도와주자. T분이 끝났을 때 같은 위치에 있는 두 소는 같은 그룹에 속한다.
제약
입력 형식
첫째 줄에 두 정수 N과 T가 주어진다.
둘째 줄부터 1+N번째 줄까지 각 줄에 소 한 마리의 초기 위치와 속도가 주어진다 (각각 10억 이하의 음이 아닌 정수/양의 정수). 모든 소는 서로 다른 위치에서 출발하며, 위치가 증가하는 순서로 주어진다.
출력 형식
T분 후에 남아 있는 그룹의 수를 나타내는 정수 하나를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
cowjog.in · 출력을 쓸 파일 cowjog.out예제 1
입력
5 3
0 1
1 2
2 3
3 2
6 1출력
3문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > December > Silver
태그