Mirko and Slavko are playing with toy animals. First, they choose one of three boards given in the figure below. Each board consists of cells (shown as circles in the figure) arranged into a one, two or three dimensional grid.
Mirko then places N little toy animals into the cells. The distance between two cells is the smallest number of moves that an animal would need in order to reach one cell from the other. In one move, the animal may step into one of the adjacent cells (connected by line segments in the figure). Two animals can hear each other if the distance between their cells is at most D. Slavko's task is to calculate how many pairs of animals there are such that one animal can hear the other.
입력 1 6 5 100 25 50 50 10 20 23 출력 4 입력 2 5 4 10 5 2 7 2 8 4 6 5 4 4 출력 8 입력 3 8 10 20 10 10 10 10 10 20 10 20 10 10 20 20 20 10 10 20 10 20 20 20 10 20 20 20 출력 12 Clarification for the leftmost example. Suppose the animals are numbered 1 through 6 in the order in which they are given. The four pairs are: · 1-5 (distance 5) · 1-6 (distance 2) · 2-3 (distance 0) · 5-6 (distance 3) Clarification for the middle example. The eight pairs are: · 1-2 (distance 2) · 1-4 (distance 4) · 1-5 (distance 3) · 2-3 (distance 3) · 2-4 (distance 4) · 3-4 (distance 3) · 3-5 (distance 4) · 4-5 (distance 3) 출력
출처: INTERNATIONAL OLYMPIAD IN INFORMATICS 2007