| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 512 MB | 133 | 34 | 25 | 29.070% |
You work for invention center as a part time programmer. This center researches movement of protein molecules. It needs how molecules make clusters, so it will calculate distance of all pair molecules and will make a histogram. Molecules’ positions are given by a N x N grid map. Value Cxy of cell (x,y) in a grid map means that Cxy molecules are in the position (x,y).
You are given a grid map, please calculate histogram of all pair molecules.
Input is formatted as follows.
N C11 C12 ... C1N C21 C22 ... C2N ... CN1 CN2 ... CNN
First line contains the grid map size N (1 ≤ N ≤ 1024). Each next N line contains N numbers. Each numbers Cxy (0 ≤ Cxy ≤ 9) means the number of molecule in position (x,y). There are at least 2 molecules.
Output is formatted as follows.
Dave d1 c1 d2 c2 ... dm cm
Print Dave which an average distance of all pair molecules on first line. Next, print histogram of all pair distance. Each line contains a distance di and the number of pair molecules ci(0 < ci). The distance di should be calculated by squared Euclidean distance and sorted as increasing order. If the number of different distance is more than 10,000, please show the first 10,000 lines. The answer may be printed with an arbitrary number of decimal digits, but may not contain an absolute or relative error greater than or equal to 10−8.
2 1 0 0 1
1.4142135624 2 1
3 1 1 1 1 1 1 1 1 1
1.6349751825 1 12 2 8 4 6 5 8 8 2
5 0 1 2 3 4 5 6 7 8 9 1 2 3 2 1 0 0 0 0 0 0 0 0 0 1
1.8589994382 0 125 1 379 2 232 4 186 5 200 8 27 9 111 10 98 13 21 16 50 17 37 18 6 20 7 25 6