/home/toolbox/public_html/solutions/8/821/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /*
16 * Author: Isaac Traxler
17 * Date: 2015-04-21
18 * Purpose:
19 * Problem: 823
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26 #define MAX_SIZE 102
27 #define INFINITY 500
28
29 int a[MAX_SIZE][MAX_SIZE];
30 int mx;
31 int caseNum = 0;
32 double avg;
33 int cnt;
34
35 void init()
36 {
37 /* FUNCTION init */
38 int i;
39 int j;
40
41 mx = 0;
42 caseNum++;
43 for (i=0; i<MAX_SIZE; i++)
44 {
45 /* for i */
46 for (j=0; j<MAX_SIZE; j++)
47 {
48 /* for j */
49 a[i][j] = INFINITY;
50 } /* for j */
51 a[i][i] = 0; /* set digonal to distance 0 */
52 } /* for i */
53 } /* FUNCTION init */
54
55 void dump()
56 {
57 /* FUNCTION dump */
58 int i;
59 int j;
60
61 for (i=1; i<mx; i++)
62 {
63 /* for i */
64 printf("%2d:", i);
65 for (j=1; j<mx; j++)
66 {
67 /* for j */
68 printf("%4d", a[i][j]);
69 } /* for j */
70 printf("\n");
71 } /* for i */
72 } /* FUNCTION dump */
73
74 int getInput()
75 {
76 /* FUNCTION getInput */
77 int dataReadFlag;
78 int m;
79 int n;
80
81 scanf(" %d %d ", &m, &n);
82 dataReadFlag = (0 != m) && (0 != n);
83 if (dataReadFlag)
84 {
85 /* have another case */
86 init();
87 while ((0 != m) && (0 != n))
88 {
89 /* another edge */
90 a[m][n] = 1;
91 if (mx < m)
92 {
93 mx = m;
94 }
95 if (mx < n)
96 {
97 mx = n;
98 }
99 scanf(" %d %d ", &m, &n);
100 } /* another edge */
101 mx++; /* so if 4 is largest value, mx will be 5 */
102 } /* have another case */
103 return (dataReadFlag);
104 } /* FUNCTION getInput */
105
106 void fw()
107 {
108 /* FUNCTION fw */
109 int i;
110 int j;
111 int k;
112
113 for (k=1; k<mx; k++)
114 {
115 /* for k */
116 for (i=1; i<mx; i++)
117 {
118 /* for i */
119 for (j=1; j<mx; j++)
120 {
121 /* for j */
122 if ((a[i][k] + a[k][j]) < a[i][j])
123 {
124 /* k is a better way to get from i to j */
125 a[i][j] = a[i][k] + a[k][j];
126 } /* k is a better way to get from i to j */
127 } /* for j */
128 } /* for i */
129 } /* for k */
130 } /* FUNCTION fw */
131
132 int sum()
133 {
134 /* FUNCTION sum */
135 int total = 0;
136 int i;
137 int j;
138
139 cnt = 0;
140 for (i=1; i<mx; i++)
141 {
142 /* for i */
143 for (j=1; j<mx; j++)
144 {
145 /* for j */
146 if ((0 < a[i][j]) && (INFINITY > a[i][j]))
147 {
148 /* only process palces we could get to */
149 cnt++;
150 total = total + a[i][j];
151 } /* only process palces we could get to */
152 } /* for j */
153 } /* for i */
154 return total;
155 } /* FUNCTION sum */
156
157 void process()
158 {
159 /* FUNCTION process */
160 int total;
161
162 DEBUG printf("\nBefore fw \n");
163 DEBUG dump();
164 fw();
165 DEBUG printf("\nafter fw \n");
166 DEBUG dump();
167 total = sum();
168 DEBUG printf("total = %d cnt = %d \n", total, cnt);
169 avg = ((double) total) / ((double) cnt);
170 printf("Case %d: average length between pages = %.3f clicks\n", caseNum, avg);
171 } /* FUNCTION process */
172
173 int main()
174 {
175 /* main */
176 int moreToDo;
177
178 moreToDo = getInput();
179 while (moreToDo)
180 {
181 /* while */
182 process();
183 moreToDo = getInput();
184 } /* while */
185
186 return EXIT_SUCCESS;
187 } /* main */
188