?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Adding some more judges, here and there.
[and.git] / NEERC / inspection / tests / doall.java
blobf7a6eff00d916e8800f24e107bbca44f688cac20
1 import java.io.PrintWriter;
2 import java.io.FileNotFoundException;
3 import java.util.*;
4
5 public class doall {
6
7 int tn = 0;
8 private static final int MAXN = 100;
9
10 void printTest(String comment, List<List<Integer>> edges) throws FileNotFoundException {
11 tn++;
12 System.out.println("Test " + String.format("%02d", tn) + ": " + comment);
13 PrintWriter out = new PrintWriter(String.format("%02d", tn));
14 out.println(edges.size());
15 for (List<Integer> list : edges) {
16 out.print(list.size());
17 for (int i : list) {
18 out.print(" ");
19 out.print(i + 1);
20 }
21 out.println();
22 }
23 out.close();
24 }
25
26 Random random = new Random(124234234);
27
28 void printShuffledTest(String comment, int[][] a) throws FileNotFoundException {
29 int n = a.length;
30 List<Integer> p = new ArrayList<Integer>();
31 for (int i = 0; i < n; i++) p.add(i);
32 Collections.shuffle(p, random);
33 List<List<Integer>> e = new ArrayList<List<Integer>>();
34 for (int i = 0; i < n; i++) {
35 List<Integer> list = new ArrayList<Integer>();
36 for (int j = 0; j < n; j++) {
37 if (a[p.get(i)][p.get(j)] > 0) {
38 list.add(j);
39 }
40 }
41 Collections.shuffle(list, random);
42 e.add(list);
43 }
44 printTest(comment, e);
45 }
46
47 public static void main(String[] args) {
48 try {
49 new doall().run();
50 } catch (Exception e) {
51 e.printStackTrace();
52 System.exit(1);
53 }
54 }
55
56 private void run() throws Exception {
57 printTest("Sample test",
58 Arrays.asList(
59 Arrays.asList(2),
60 Arrays.asList(6),
61 Arrays.asList(3, 4),
62 Arrays.asList(7),
63 Arrays.asList(7),
64 Arrays.<Integer>asList(),
65 Arrays.asList(5, 4),
66 Arrays.<Integer>asList()
67 )
68 );
69 printShuffledTest("Square",
70 new int[][]
71 {{0, 1, 1, 0},
72 {0, 0, 0, 1},
73 {0, 0, 0, 1},
74 {0, 0, 0, 0}}
75 );
76 printShuffledTest("Full 4 graph",
77 new int[][]
78 {{0, 1, 1, 1},
79 {0, 0, 1, 1},
80 {0, 0, 0, 1},
81 {0, 0, 0, 0}}
82 );
83 printShuffledTest("Square and two edges",
84 new int[][]
85 {{0, 1, 1, 0, 0, 0},
86 {0, 0, 0, 1, 0, 0},
87 {0, 0, 0, 1, 0, 0},
88 {0, 0, 0, 0, 1, 0},
89 {0, 0, 0, 0, 0, 0},
90 {1, 0, 0, 0, 0, 0}}
91 );
92 printShuffledTest("One edge",
93 new int[][]
94 {{0, 1},
95 {0, 0}}
96 );
97
98 for (int i = 0; i < 10; i++) {
99 int n = 5 + random.nextInt(10);
100 int[][] a = new int[n][n];
101 int m = random.nextInt(n * (n - 1) / 2 + 1);
102 for (int k = 0; k < m; k++) {
103 int x, y;
104 do {
105 x = random.nextInt(n);
106 y = random.nextInt(n);
107 } while (y <= x || a[x][y] > 0);
108 a[x][y] = 1;
109 }
110 for (int j = 0; j < n; j++) {
111 boolean ok = false;
112 for (int k = 0; k < n; k++) {
113 if (a[j][k] == 1 || a[k][j] == 1) ok = true;
114 }
115 if (!ok) a[j][(j + 1) % n] = 1;
116 }
117 printShuffledTest("Small random test, n = " + n + " m = " + m, a);
118 }
119
120 {
121 for (int zzz = 0; zzz < 10; zzz++) {
122 int[] d = new int[MAXN];
123 int[][] a = new int[MAXN][MAXN];
124 boolean[][] b = new boolean[MAXN][MAXN];
125 for (int i = 0; i < MAXN / 2 - 1; i++) {
126 int x, y;
127 do {
128 x = random.nextInt(MAXN / 4);
129 y = MAXN / 4 + random.nextInt(MAXN / 4);
130 } while (b[x][y]);
131 a[x][y] = 1;
132 d[x]++;
133 d[y]++;
134 b[x][y] = true;
135 b[y][x] = true;
136 for (int z = 0; z < MAXN / 2; z++) {
137 if (b[z][x]) {
138 b[z][y] = true;
139 b[y][z] = true;
140 }
141 if (b[z][y]) {
142 b[z][x] = true;
143 b[x][z] = true;
144 }
145 }
146 }
147 for (int i = 0; i < MAXN / 4; i++) {
148 for (int j = 0; j < d[i] + 1; j++) {
149 a[MAXN / 2 + j][i] = 1;
150 }
151 }
152 for (int i = MAXN / 4; i < MAXN / 2; i++) {
153 for (int j = 0; j < d[i] + 1; j++) {
154 a[i][MAXN / 4 * 3 + j] = 1;
155 }
156 }
157 printShuffledTest("Bipartite matching test", a);
158 }
159 }
160
161 {
162 int n = MAXN;
163 int[][] a = new int[n][n];
164 for (int i = 0; i < MAXN - 1; i++) a[i][i + 1] = 1;
165 printShuffledTest("One long line", a);
166 }
167
168 {
169 int n = MAXN;
170 int[][] a = new int[n][n];
171 for (int i = 0; i < MAXN; i++)
172 for (int j = i + 1; j < MAXN && j < i + 5; j++) {
173 a[i][j] = 1;
174 }
175 printShuffledTest("Each node connected with next 5 nodes", a);
176 }
177
178 {
179 int n = MAXN;
180 int[][] a = new int[n][n];
181 int k = 0;
182 while ((k + 1) * (k + 1) <= n) k++;
183 for (int i = 0; i < k; i++) {
184 for (int j = 0; j < k; j++) {
185 if (j < k - 1) a[i * k + j][i * k + j + 1] = 1;
186 if (i < k - 1) a[i * k + j][i * k + j + k] = 1;
187 }
188 }
189 for (int i = k * k; i < n - 1; i++) {
190 a[i][i + 1] = 1;
191 }
192 printShuffledTest("Grid", a);
193 }
194
195 {
196 int n = MAXN;
197 int[][] a = new int[n][n];
198 int m = 0;
199 while ((m + 1) * (m + 1) <= n) m++;
200 for (int i = 0; i < m; i++) {
201 for (int j = 0; j < m; j++) {
202 if (j < m - 1 && random.nextBoolean()) a[i * m + j][i * m + j + 1] = 1;
203 if (i < m - 1 && random.nextBoolean()) a[i * m + j][i * m + j + m] = 1;
204 }
205 }
206 for (int j = 0; j < n; j++) {
207 boolean ok = false;
208 for (int k = 0; k < n; k++) {
209 if (a[j][k] == 1 || a[k][j] == 1) ok = true;
210 }
211 if (!ok) a[j][(j + 1) % n] = 1;
212 }
213 printShuffledTest("Broken grid", a);
214 }
215
216 {
217 int n = MAXN;
218 int[][] a = new int[n][n];
219 for (int i = 0; i < MAXN; i++) {
220 for (int j = i + 1; j < MAXN; j++) {
221 a[i][j] = 1;
222 }
223 }
224 printShuffledTest("Full graph", a);
225 }
226
227 {
228 int n = MAXN;
229 int[][] a = new int[n][n];
230 for (int i = 0; i < MAXN / 2; i++) {
231 for (int j = i + 1; j < MAXN / 2; j++) {
232 a[i][j] = 1;
233 }
234 }
235 a[MAXN / 2 - 1][MAXN / 2] = 1;
236 for (int i = MAXN / 2; i < MAXN; i++) {
237 for (int j = i + 1; j < MAXN; j++) {
238 a[i][j] = 1;
239 }
240 }
241 printShuffledTest("Two connected full graphs", a);
242 }
243
244 {
245 int n = MAXN;
246 int[][] a = new int[n][n];
247 for (int i = 0; i < MAXN / 4; i++) {
248 for (int j = MAXN / 4; j < MAXN / 2; j++) {
249 a[i][j] = 1;
250 }
251 }
252 for (int i = MAXN / 4; i < MAXN / 2; i++) {
253 a[i][i + MAXN / 4] = 1;
254 }
255 for (int i = MAXN / 2; i < MAXN / 4 * 3; i++) {
256 for (int j = MAXN / 4 * 3; j < MAXN; j++) {
257 a[i][j] = 1;
258 }
259 }
260 printShuffledTest("Two connected bipartite full graphs", a);
261 }
262
263 {
264 int n = MAXN;
265 int[][] a = new int[n][n];
266 for (int k = 0; k < MAXN / 10; k++) {
267 for (int i = 0; i < 10; i++) {
268 for (int j = i + 1; j < 10; j++) {
269 a[k * 10 + i][k * 10 + j] = 1;
270 }
271 }
272 if (k > 0) {
273 int j = random.nextInt(k);
274 a[j * 10 + 9][k * 10] = 1;
275 }
276 }
277 printShuffledTest("10 connected full graphs", a);
278 }
279
280 {
281 int n = MAXN;
282 int[][] a = new int[n][n];
283 for (int i = 0; i < MAXN / 2; i++) {
284 for (int j = MAXN / 2; j < MAXN; j++) {
285 a[i][j] = 1;
286 }
287 }
288 printShuffledTest("Full bipartite graph", a);
289 }
290
291 {
292 int m = 0;
293 while ((m + 1) * (m + 1) <= MAXN) m++;
294 int n = m * m;
295 int[][] a = new int[n][n];
296 for (int i = 0; i < m - 1; i++) {
297 for (int j = 0; j < m; j++) {
298 for (int k = 0; j < m; j++) {
299 a[i * m + j][i * m + k + m] = 1;
300 }
301 }
302 }
303 printShuffledTest("Full layered graph", a);
304 }
305
306 {
307 int n = MAXN;
308 while (n % 5 > 0) n--;
309 int m = n / 5;
310 int[][] a = new int[n][n];
311 for (int i = 0; i < m; i++) {
312 for (int j = m; j < 2 * m; j++) {
313 a[i][j] = 1;
314 }
315 }
316 for (int j = m; j < 2 * m; j++) {
317 a[j][2 * m] = 1;
318 }
319 for (int i = 2 * m; i < 3 * m - 1; i++) {
320 a[i][i + 1] = 1;
321 }
322 for (int j = 4 * m; j < 5 * m; j++) {
323 a[3 * m - 1][j] = 1;
324 }
325 for (int i = 3 * m; i < 4 * m; i++) {
326 for (int j = 4 * m; j < 5 * m; j++) {
327 a[i][j] = 1;
328 }
329 }
330 printShuffledTest("Many long paths", a);
331 }
332
333 for (int i = 0; i < 10; i++) {
334 int n = MAXN - random.nextInt(5);
335 int[][] a = new int[n][n];
336 for (int j = 1; j < n; j++) {
337 int k = random.nextInt(j);
338 a[k][j] = 1;
339 }
340 printShuffledTest("Random tree", a);
341 }
342
343 for (int i = 0; i < 20; i++) {
344 int n = MAXN - random.nextInt(5);
345 int[][] a = new int[n][n];
346 int m = random.nextInt(n * (n - 1) / 2 + 1);
347 for (int k = 0; k < m; k++) {
348 int x, y;
349 do {
350 x = random.nextInt(n);
351 y = random.nextInt(n);
352 } while (y <= x || a[x][y] > 0);
353 a[x][y] = 1;
354 }
355 for (int j = 0; j < n; j++) {
356 boolean ok = false;
357 for (int k = 0; k < n; k++) {
358 if (a[j][k] == 1 || a[k][j] == 1) ok = true;
359 }
360 if (!ok) a[j][(j + 1) % n] = 1;
361 }
362 printShuffledTest("Random test, n = " + n + " m = " + m, a);
363 }
364 //To change body of created methods use File | Settings | File Templates.
365 }
366
367 }