레이팅 미적용설명
농부 존의 소 N마리가 (1 <= N <= 100,000) 다시 발굽 운동을 하러 나와 무한히 긴 트랙을 조깅하고 있다. 각 소는 서로 다른 위치에서 출발하며, 소마다 달리는 속도가 다를 수 있다.
트랙은 여러 차선으로 나뉘어 있어 소들이 서로를 지나칠 수 있다. 같은 차선에 있는 두 소는 어느 순간에도 같은 위치를 차지할 수 없다. 농부 존은 어떤 소도 차선을 바꾸거나 속도를 조절할 필요가 없기를 바라며, 소들이 T분 동안 달린다면 (1 <= T <= 1,000,000,000) 차선이 몇 개나 필요할지 궁금해한다.
제약
입력 형식
첫째 줄에 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 > Gold
태그