레이팅 미적용농부 존이 최근 농장의 크기를 넓혀서, 소들의 관점에서 농장은 사실상 무한히 크다! 소들은 농장의 방목 구역을 정사각형 "칸"들로 이루어진 무한한 2차원 격자로 생각하며, 각 칸은 맛있는 풀로 채워져 있다(각 칸을 무한한 체스판의 정사각형이라고 생각하자). 농부 존의 소 \(N\)마리(\(1\le N\le 1000\))는 각각 서로 다른 칸에서 출발하며, 일부는 북쪽을, 일부는 동쪽을 바라보고 시작한다.
매시간, 각 소는 다음 중 하나를 한다.
- 현재 칸의 풀이 이미 다른 소에게 먹혔다면 멈춘다(그리고 그때부터 계속 멈춰 있는다).
- 현재 칸의 풀을 모두 먹고 바라보는 방향으로 한 칸 앞으로 이동한다.
따라서 시간이 지나면 각 소는 자기 뒤에 빈 칸들로 이루어진 황량한 "홈(rut)"을 남긴다.
두 소가 같은 이동에서 풀이 있는 같은 칸으로 이동하면, 두 소는 그 칸을 공유하고 다음 시간에 각자의 방향으로 계속 이동한다.
농부 존은 풀 뜯기를 멈춘 소들을 보면 기분이 좋지 않아서, 멈춘 소들에 대해 누구를 탓해야 할지 알고 싶어 한다. 소 \(b\)가 소 \(a\)가 원래 풀을 먹었던 칸에서 멈추면, 소 \(a\)가 소 \(b\)를 멈추게 했다고 한다. 또한 소 \(a\)가 소 \(b\)를 멈추게 했고 소 \(b\)가 소 \(c\)를 멈추게 했다면, 소 \(a\)도 소 \(c\)를 멈추게 했다고 한다(즉, "멈추게 함" 관계는 추이적이다). 각 소는 자신이 멈추게 한 소의 수만큼 비난을 받는다. 각 소에게 돌아가는 비난의 양, 즉 그 소가 멈추게 한 소의 수를 계산하시오.
문제 제공: Brian Dean
배점
- 테스트 케이스 2-5에서는 모든 좌표가 최대 \(2000\)이다.
- 테스트 케이스 6-10에서는 추가 제약이 없다.
문제 제공: Brian Dean
첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄 각각에는 소의 시작 위치가 주어지는데, N(북쪽을 바라봄) 또는 E(동쪽을 바라봄)인 문자 하나와 칸의 좌표를 나타내는 두 음이 아닌 정수 \(x\), \(y\)(\(0\le x\le 10^9\), \(0\le y\le 10^9\))로 이루어진다. 모든 \(x\) 좌표는 서로 다르며, \(y\) 좌표도 마찬가지로 서로 다르다.
\(N\)개의 줄을 출력한다. 출력의 \(i\)번째 줄에는 입력의 \(i\)번째 소에게 돌아가는 비난의 양을 출력한다.
6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 1
E 9 20
0
1
2
1
0In this example, cow 3 stops cow 2, cow 4 stops cow 5, and cow 5 stops cow 6. By transitivity,
cow 4 also stops cow 6.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > December > Silver