원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
친구
원제: 친구
문제
KOI 마을에는 일직선 형태의 도로가 있다. 이 도로 위에는 개의 집이 있고, 번부터 번까지 번호가 부여된 명의 학생이 한 집에 한 명씩 살고 있다. ()번 학생이 살고 있는 집의 좌표는 이다. 같은 좌표에 여러 개의 집이 존재하지 않는다.
또한, KOI 마을에는 번부터 번까지 번호가 부여된 개의 학교들이 있다. ()번 학생은 번 학교에 다닌다.
번 학생과 번 학생에 대해 (), 아래의 조건 중 적어도 하나를 만족하면, 두 학생은 서로 친구라고 한다.
- 두 학생이 서로 같은 학교에 다니고, 두 학생의 집 사이의 거리가 이하이다.
- 두 학생이 서로 다른 학교에 다니고, 두 학생의 집 사이의 거리가 이하이다.
여기서, 두 집 사이의 거리는 두 집의 좌표 차이의 절댓값으로 정의한다. 즉, 번 학생과 번 학생의 집 사이의 거리는 이다.
각 학생에 대해, 그 학생의 친구가 몇 명인지 계산하는 프로그램을 작성하라. 자기 자신은 자신의 친구가 아님에 유의하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 ()에 대하여
- 정수 , ()에 대하여
- 정수 ()에 대하여
부분문제
- (20점)
- (14점)
- (25점) 정수 ()에 대하여 이고
- (21점)
- (10점) 정수 ()에 대하여
- (10점) 추가 제약 조건 없음.
입력 형식
첫 줄에 세 정수 , , 가 공백으로 구분되어 차례대로 주어진다.
이후 개의 줄에 걸쳐 각 학생의 정보가 주어진다. 이 중 번째 줄에는 두 정수 , 가 공백으로 구분되어 차례대로 주어진다 ().
출력 형식
첫 줄에 개의 정수를 공백으로 구분하여 출력한다. 이 중 번째 정수는 번 학생의 친구의 수를 의미한다 ().
예제
예제 1
7 3 5 9 2 1 1 14 3 6 2 17 3 4 1 8 1
4 2 2 4 1 3 2
예제 2
12 8 5 31 1 10 1 49 3 23 2 62 3 18 1 40 2 14 2 55 2 27 3 45 1 36 3
2 2 1 2 0 3 2 2 0 2 2 2