원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
점프
원제: 점프
문제
이차원 좌표 평면에 번부터 번까지 번호가 부여된 개의 발판이 있다. 각 발판은 좌표 평면 위의 한 점으로 표현할 수 있고, ()번 발판의 위치 좌표는 이다.
두 정수 , ()에 대해, 아래의 두 조건을 모두 만족할 때에만 번 발판에서 번 발판으로 이동할 수 있다.
여기서, 는 주어지는 상수이며, 양의 정수 값을 가진다.
각 발판에 대하여, 그 발판에서 시작해서 다른 발판으로 이동하는 것을 번 이상 반복하여 도달할 수 있는 서로 다른 발판의 개수를 세는 프로그램을 작성하라. 이 개수에는 그 발판 자기 자신도 포함되어야 함에 유의하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 ()에 대하여
부분문제
- (12점)
- (32점)
- (9점)
- (23점) 정수 ()에 대하여
- (33점)
- (41점) 추가적인 제약 조건 없음.
입력 형식
첫 줄에 두 정수 , 가 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄에 개의 정수를 공백으로 구분하여 출력한다. 이 중 번째 정수는 번 발판에서 시작해서 다른 발판으로 이동하는 것을 번 이상 반복하여 도달할 수 있는 서로 다른 발판의 개수를 의미한다 ().
예제
예제 1
6 2 3 5 4 6 1 3
6 4 3 1 2 1
각 발판에 대하여 해당 발판에서 시작해서 도달할 수 있는 발판은 다음과 같다.
- 번 발판: 번 발판을 포함하여 모든 발판으로 도달 가능하다.
- 번 발판: , , , 번 발판으로 도달 가능하다.
- 번 발판: , , 번 발판으로 도달 가능하다.
- 번 발판: 번 발판을 제외하고 도달할 수 있는 발판이 없다.
- 번 발판: , 번 발판으로 도달 가능하다.
- 번 발판: 번 발판을 제외하고 도달할 수 있는 발판이 없다.
예제 2
6 3 1 4 8 9 10 15
2 1 3 2 1 1
예제 3
3 2 1 4 7
1 1 1