레이팅 미적용1차원 수직선 위의 위치 \(0\)과 \(L\) \((1\le L\le 10^9)\)에 두 개의 외양간이 있다. 또한 이 수직선 위의 서로 다른 위치에 \(N\)마리의 소 \((1\le N\le 5\cdot 10^4)\)가 있다(외양간과 소는 사실상 점으로 생각하면 된다). 각 소 \(i\)는 처음에 어떤 위치 \(x_i\)에 있으며, 초당 1단위의 속력으로 양의 방향 또는 음의 방향으로 이동하는데, 이는 \(1\) 또는 \(-1\)인 정수 \(d_i\)로 표현된다. 각 소는 \([1,10^3]\) 범위의 무게 \(w_i\)도 가진다. 모든 소는 다음 사건 중 하나가 일어날 때까지 항상 일정한 속도로 이동한다.
- 소 \(i\)가 외양간에 도착하면, 소 \(i\)는 이동을 멈춘다.
- 두 소 \(i\)와 \(j\)가 외양간이 아닌 같은 점을 차지하게 되면 만남이 발생한다. 이 경우 소 \(i\)는 소 \(j\)의 이전 속도를 부여받고, 그 반대도 마찬가지다. 소들이 정수가 아닌 점에서 만날 수도 있음에 유의하라.
(외양간 중 하나에 도착하여) 이동을 멈춘 소들의 무게 합이 모든 소의 무게 합의 절반 이상이 되는 가장 이른 시각을 \(T\)라고 하자. 시간 \(0 \ldots T\) 동안(시각 \(T\) 포함) 소 쌍들 사이에서 일어나는 만남의 총 횟수를 구하여라.
문제 제공: Benjamin Qi
점수 배점
- 테스트 케이스 2-4는 \(N\le 10^2\)이고 모든 \(i\)에 대해 \(w_i=1\)을 만족한다.
- 테스트 케이스 5-7은 \(N\le 10^2\)을 만족한다.
문제 제공: Benjamin Qi
첫째 줄에 공백으로 구분된 두 정수 \(N\)과 \(L\)이 주어진다.
다음 \(N\)개의 줄에는 각각 공백으로 구분된 세 정수 \(w_i\), \(x_i\), \(d_i\)가 주어진다. 모든 위치 \(x_i\)는 서로 다르며 \(0
답을 한 줄에 출력한다.
meetings.in · 출력을 쓸 파일 meetings.out3 5
1 1 1
2 2 -1
3 3 -12The cows in this example move as follows:
- The first and second cows meet at position 1.5 at time 0.5. The first cow now has velocity \(-1\) and the second has velocity \(1.\)
- The second and third cows meet at position 2 at time 1. The second cow now has velocity \(-1\) and the third has velocity \(1.\)
- The first cow reaches the left barn at time 2.
- The second cow reaches the left barn at time 3.
- The process now terminates since the sum of the weights of the cows that have reached a barn is at least half of the sum of the weights of all cows. The third cow would have reached the right barn at time 4.
Exactly two meetings occurred.
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > December > Silver