5476번 - 장난감 동물 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 69 | 20 | 19 | 30.645% |
문제
상근이와 선영이는 장난감 동물을 가지고 재미있게 놀려고 한다. 먼저, 아래 세 가지 게임판 중 하나를 선택한다. 각 게임판은 여러 개의 칸(그림에는 동그라미)으로 이루어져 있고, 각 게임판은 일차원, 이차원, 삼차원 모양이다.
상근이는 N개의 작은 장난감 동물을 칸에 넣는다.
두 칸의 거리는 장난감 동물이 한 칸에서 출발해서 다른 칸으로 도착하는데 필요한 이동의 횟수이다. 장난감 동물은 자신이 있는 칸과 인접한 칸 중 하나로 이동할 수 있다. (각 칸과 인접한 칸은 그림에서 선분으로 이어져 있다)
두 장난감 동물이 서로의 소리를 들으려면 두 칸의 거리가 D보다 작거나 같아야 한다. 게임판의 종류와 각 장난감 동물의 위치, 그리고 D가 주어졌을 때, 서로의 소리를 들을 수 있는 장난감 동물의 쌍의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 네 정수 B, N, D, M이 주어진다.
B는 게임판의 종류이다. (1 ≤ B ≤ 3) 문제 설명의 왼쪽 그림이 1번 게임판, 중간 그림이 2번, 오른쪽 그림이 3번 게임판이다.
N은 장난감 동물의 수이다. (1 ≤ N ≤ 100,000)
D는 두 장난감 동물이 서로의 소리를 들을 수 있는 가장 먼 거리이다. (1 ≤ D ≤ 100,000,000)
M은 게임판의 크기이다. (입력으로 들어올 수 있는 가장 큰 좌표값) B가 1인 경우 M은 최대 75,000,000이고, 2인 경우에는 75,000, 3인 경우에는 75이다.
다음 N개의 줄에는 각 장난감 동물의 좌표가 주어진다. 모든 좌표는 1보다 크거나 같고, M보다 작거나 같은 자연수이다.
같은 칸에 장난감 동물 여러 개가 들어가 있을 수도 있다.
출력
첫째 줄에 서로의 소리를 들을 수 있는 장난감 동물의 쌍의 수를 출력한다.
예제 입력 1
2 5 4 10 5 2 7 2 8 4 6 5 4 4
예제 출력 1
8
힌트
1-2 (거리 2)
1-4 (거리 4)
1-5 (거리 3)
2-3 (거리 3)
2-4 (거리 4)
3-4 (거리 3)
3-5 (거리 4)
4-5 (거리 3)
출처
Olympiad > International Olympiad in Informatics > IOI 2007 > Day 2 5번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호