package gcj2013.template;
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import static java.
util.
Arrays.
deepToString;
public class Template2
implements Runnable { private static final char PROB = Template2.class.getSimpleName().charAt(0);
private static int DEFAULT_PARARELL
= Runtime.
getRuntime().
availableProcessors() + 1; private static File DIR
= new File("."); private static boolean TEST_ALL = false;
public static class Solver implements Callable<String> {
private static final double EPS = 1e-12;
private static final int INF = 1 << 20;
private static final int[] di = { -1, 0, 0, 1 };
private static final int[] dj = { 0, -1, 1, 0 };
// shared table
static {
// :TODO
}
// parse
public Solver(final Scanner sc) {
// :TODO
}
// solve
@Override
// :TODO
throw null;
}
}
// Template
@Override
public void run() {
final ExecutorService es = Executors.newFixedThreadPool(DEFAULT_PARARELL);
try (final Scanner sc
= new Scanner
(System.
in)) { final List<Future<String>> list = new ArrayList<>();
final int T = sc.nextInt();
for (int i = 0; i < T; i++)
list.add(es.submit(new Solver(sc)));
for (int t = 1; t <= T; t++) {
debugf("Case #%s%n", t);
System.
out.
printf("Case #%s: %s%n", t, list.
get(t
- 1).
get()); }
debug("done.");
e.printStackTrace();
}
es.shutdown();
}
if (TEST_ALL) {
for (final String input
: seekInputFiles
()) { debug("INPUT", input);
new Template2().run();
}
} else {
final String input
= seekInputFile
(); debug("INPUT", input);
if (input != null) {
} else
DEFAULT_PARARELL = 1;
new Template2().run();
}
}
private static String seekInputFile
() { final String[] names
= new String[] { PROB
+ "-large-practice-2.in", PROB
+ "-large-practice-1.in",
PROB + "-large-practice.in", PROB + "-large-2.in", PROB + "-large-1.in", PROB + "-large.in",
PROB + "-small-practice-2.in", PROB + "-small-practice-1.in", PROB + "-small-practice.in" };
if (new File(DIR, s
).
exists()) return s;
for (int k = 2; k >= 0; k--) {
int max = -1;
for (int i
= 0; new File(DIR, PROB
+ "-small" + (k
> 0 ? "-" + k
: "") + "-attempt" + i
+ ".in").
exists(); i
++) max = i;
if (max >= 0)
return PROB + "-small" + (k > 0 ? "-" + k : "") + "-attempt" + max + ".in";
}
return null;
}
private static List<String> seekInputFiles() {
final List<String> ret = new ArrayList<>();
final String[] names
= new String[] { PROB
+ "-large-practice-2.in", PROB
+ "-large-practice-1.in",
PROB + "-large-practice.in", PROB + "-large-2.in", PROB + "-large-1.in", PROB + "-large.in",
PROB + "-small-practice-2.in", PROB + "-small-practice-1.in", PROB + "-small-practice.in" };
if (new File(DIR, s
).
exists()) ret.add(s);
for (int k = 2; k >= 0; k--) {
int max = -1;
for (int i
= 0; new File(DIR, PROB
+ "-small" + (k
> 0 ? "-" + k
: "") + "-attempt" + i
+ ".in").
exists(); i
++) max = i;
if (max >= 0)
ret.add(PROB + "-small" + (k > 0 ? "-" + k : "") + "-attempt" + max + ".in");
}
return ret;
}
System.
err.
printf(format, os
); }
private static void debug
(Object...
os) { System.
err.
println(deepToString
(os
)); }
}
cGFja2FnZSBnY2oyMDEzLnRlbXBsYXRlOwoKaW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuTGlzdDsKaW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwppbXBvcnQgamF2YS51dGlsLmNvbmN1cnJlbnQuQ2FsbGFibGU7CmltcG9ydCBqYXZhLnV0aWwuY29uY3VycmVudC5FeGVjdXRvclNlcnZpY2U7CmltcG9ydCBqYXZhLnV0aWwuY29uY3VycmVudC5FeGVjdXRvcnM7CmltcG9ydCBqYXZhLnV0aWwuY29uY3VycmVudC5GdXR1cmU7CgppbXBvcnQgc3RhdGljIGphdmEudXRpbC5BcnJheXMuZGVlcFRvU3RyaW5nOwoKcHVibGljIGNsYXNzIFRlbXBsYXRlMiBpbXBsZW1lbnRzIFJ1bm5hYmxlIHsKCXByaXZhdGUgc3RhdGljIGZpbmFsIGNoYXIgUFJPQiA9IFRlbXBsYXRlMi5jbGFzcy5nZXRTaW1wbGVOYW1lKCkuY2hhckF0KDApOwoJcHJpdmF0ZSBzdGF0aWMgaW50IERFRkFVTFRfUEFSQVJFTEwgPSBSdW50aW1lLmdldFJ1bnRpbWUoKS5hdmFpbGFibGVQcm9jZXNzb3JzKCkgKyAxOwoJcHJpdmF0ZSBzdGF0aWMgRmlsZSBESVIgPSBuZXcgRmlsZSgiLiIpOwoJcHJpdmF0ZSBzdGF0aWMgYm9vbGVhbiBURVNUX0FMTCA9IGZhbHNlOwoKCXB1YmxpYyBzdGF0aWMgY2xhc3MgU29sdmVyIGltcGxlbWVudHMgQ2FsbGFibGU8U3RyaW5nPiB7CgkJcHJpdmF0ZSBzdGF0aWMgZmluYWwgZG91YmxlIEVQUyA9IDFlLTEyOwoJCXByaXZhdGUgc3RhdGljIGZpbmFsIGludCBJTkYgPSAxIDw8IDIwOwoJCXByaXZhdGUgc3RhdGljIGZpbmFsIGludFtdIGRpID0geyAtMSwgMCwgMCwgMSB9OwoJCXByaXZhdGUgc3RhdGljIGZpbmFsIGludFtdIGRqID0geyAwLCAtMSwgMSwgMCB9OwoKCQkvLyBzaGFyZWQgdGFibGUKCQlzdGF0aWMgewoJCQkvLyA6VE9ETwoJCX0KCgkJLy8gcGFyc2UKCQlwdWJsaWMgU29sdmVyKGZpbmFsIFNjYW5uZXIgc2MpIHsKCQkJLy8gOlRPRE8KCQl9CgoJCS8vIHNvbHZlCgkJQE92ZXJyaWRlCgkJcHVibGljIFN0cmluZyBjYWxsKCkgewoJCQkvLyA6VE9ETwoJCQl0aHJvdyBudWxsOwoJCX0KCX0KCgkvLyBUZW1wbGF0ZQoJQE92ZXJyaWRlCglwdWJsaWMgdm9pZCBydW4oKSB7CgkJZmluYWwgRXhlY3V0b3JTZXJ2aWNlIGVzID0gRXhlY3V0b3JzLm5ld0ZpeGVkVGhyZWFkUG9vbChERUZBVUxUX1BBUkFSRUxMKTsKCQl0cnkgKGZpbmFsIFNjYW5uZXIgc2MgPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pKSB7CgkJCWZpbmFsIExpc3Q8RnV0dXJlPFN0cmluZz4+IGxpc3QgPSBuZXcgQXJyYXlMaXN0PD4oKTsKCQkJZmluYWwgaW50IFQgPSBzYy5uZXh0SW50KCk7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgVDsgaSsrKQoJCQkJbGlzdC5hZGQoZXMuc3VibWl0KG5ldyBTb2x2ZXIoc2MpKSk7CgkJCWZvciAoaW50IHQgPSAxOyB0IDw9IFQ7IHQrKykgewoJCQkJZGVidWdmKCJDYXNlICMlcyVuIiwgdCk7CgkJCQlTeXN0ZW0ub3V0LnByaW50ZigiQ2FzZSAjJXM6ICVzJW4iLCB0LCBsaXN0LmdldCh0IC0gMSkuZ2V0KCkpOwoJCQkJU3lzdGVtLmdjKCk7CgkJCX0KCQkJZGVidWcoImRvbmUuIik7CgkJfSBjYXRjaCAoRXhjZXB0aW9uIGUpIHsKCQkJZS5wcmludFN0YWNrVHJhY2UoKTsKCQl9CgkJZXMuc2h1dGRvd24oKTsKCX0KCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmcuLi4gYXJncykgdGhyb3dzIElPRXhjZXB0aW9uIHsKCQlpZiAoVEVTVF9BTEwpIHsKCQkJZm9yIChmaW5hbCBTdHJpbmcgaW5wdXQgOiBzZWVrSW5wdXRGaWxlcygpKSB7CgkJCQlkZWJ1ZygiSU5QVVQiLCBpbnB1dCk7CgkJCQlTeXN0ZW0uc2V0SW4obmV3IEJ1ZmZlcmVkSW5wdXRTdHJlYW0obmV3IEZpbGVJbnB1dFN0cmVhbShuZXcgRmlsZShESVIsIGlucHV0KSkpKTsKCQkJCVN5c3RlbS5zZXRPdXQobmV3IFByaW50U3RyZWFtKGlucHV0ICsgIi5vdXQiKSk7CgkJCQluZXcgVGVtcGxhdGUyKCkucnVuKCk7CgkJCX0KCQl9IGVsc2UgewoJCQlmaW5hbCBTdHJpbmcgaW5wdXQgPSBzZWVrSW5wdXRGaWxlKCk7CgkJCWRlYnVnKCJJTlBVVCIsIGlucHV0KTsKCQkJaWYgKGlucHV0ICE9IG51bGwpIHsKCQkJCVN5c3RlbS5zZXRJbihuZXcgQnVmZmVyZWRJbnB1dFN0cmVhbShuZXcgRmlsZUlucHV0U3RyZWFtKG5ldyBGaWxlKERJUiwgaW5wdXQpKSkpOwoJCQkJU3lzdGVtLnNldE91dChuZXcgUHJpbnRTdHJlYW0oaW5wdXQgKyAiLm91dCIpKTsKCQkJfSBlbHNlCgkJCQlERUZBVUxUX1BBUkFSRUxMID0gMTsKCQkJbmV3IFRlbXBsYXRlMigpLnJ1bigpOwoJCX0KCX0KCglwcml2YXRlIHN0YXRpYyBTdHJpbmcgc2Vla0lucHV0RmlsZSgpIHsKCQlmaW5hbCBTdHJpbmdbXSBuYW1lcyA9IG5ldyBTdHJpbmdbXSB7IFBST0IgKyAiLWxhcmdlLXByYWN0aWNlLTIuaW4iLCBQUk9CICsgIi1sYXJnZS1wcmFjdGljZS0xLmluIiwKCQkJCVBST0IgKyAiLWxhcmdlLXByYWN0aWNlLmluIiwgUFJPQiArICItbGFyZ2UtMi5pbiIsIFBST0IgKyAiLWxhcmdlLTEuaW4iLCBQUk9CICsgIi1sYXJnZS5pbiIsCgkJCQlQUk9CICsgIi1zbWFsbC1wcmFjdGljZS0yLmluIiwgUFJPQiArICItc21hbGwtcHJhY3RpY2UtMS5pbiIsIFBST0IgKyAiLXNtYWxsLXByYWN0aWNlLmluIiB9OwoJCWZvciAoZmluYWwgU3RyaW5nIHMgOiBuYW1lcykKCQkJaWYgKG5ldyBGaWxlKERJUiwgcykuZXhpc3RzKCkpCgkJCQlyZXR1cm4gczsKCQlmb3IgKGludCBrID0gMjsgayA+PSAwOyBrLS0pIHsKCQkJaW50IG1heCA9IC0xOwoJCQlmb3IgKGludCBpID0gMDsgbmV3IEZpbGUoRElSLCBQUk9CICsgIi1zbWFsbCIgKyAoayA+IDAgPyAiLSIgKyBrIDogIiIpICsgIi1hdHRlbXB0IiArIGkgKyAiLmluIikuZXhpc3RzKCk7IGkrKykKCQkJCW1heCA9IGk7CgkJCWlmIChtYXggPj0gMCkKCQkJCXJldHVybiBQUk9CICsgIi1zbWFsbCIgKyAoayA+IDAgPyAiLSIgKyBrIDogIiIpICsgIi1hdHRlbXB0IiArIG1heCArICIuaW4iOwoJCX0KCQlyZXR1cm4gbnVsbDsKCX0KCglwcml2YXRlIHN0YXRpYyBMaXN0PFN0cmluZz4gc2Vla0lucHV0RmlsZXMoKSB7CgkJZmluYWwgTGlzdDxTdHJpbmc+IHJldCA9IG5ldyBBcnJheUxpc3Q8PigpOwoJCWZpbmFsIFN0cmluZ1tdIG5hbWVzID0gbmV3IFN0cmluZ1tdIHsgUFJPQiArICItbGFyZ2UtcHJhY3RpY2UtMi5pbiIsIFBST0IgKyAiLWxhcmdlLXByYWN0aWNlLTEuaW4iLAoJCQkJUFJPQiArICItbGFyZ2UtcHJhY3RpY2UuaW4iLCBQUk9CICsgIi1sYXJnZS0yLmluIiwgUFJPQiArICItbGFyZ2UtMS5pbiIsIFBST0IgKyAiLWxhcmdlLmluIiwKCQkJCVBST0IgKyAiLXNtYWxsLXByYWN0aWNlLTIuaW4iLCBQUk9CICsgIi1zbWFsbC1wcmFjdGljZS0xLmluIiwgUFJPQiArICItc21hbGwtcHJhY3RpY2UuaW4iIH07CgkJZm9yIChmaW5hbCBTdHJpbmcgcyA6IG5hbWVzKQoJCQlpZiAobmV3IEZpbGUoRElSLCBzKS5leGlzdHMoKSkKCQkJCXJldC5hZGQocyk7CgkJZm9yIChpbnQgayA9IDI7IGsgPj0gMDsgay0tKSB7CgkJCWludCBtYXggPSAtMTsKCQkJZm9yIChpbnQgaSA9IDA7IG5ldyBGaWxlKERJUiwgUFJPQiArICItc21hbGwiICsgKGsgPiAwID8gIi0iICsgayA6ICIiKSArICItYXR0ZW1wdCIgKyBpICsgIi5pbiIpLmV4aXN0cygpOyBpKyspCgkJCQltYXggPSBpOwoJCQlpZiAobWF4ID49IDApCgkJCQlyZXQuYWRkKFBST0IgKyAiLXNtYWxsIiArIChrID4gMCA/ICItIiArIGsgOiAiIikgKyAiLWF0dGVtcHQiICsgbWF4ICsgIi5pbiIpOwoJCX0KCQlyZXR1cm4gcmV0OwoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgZGVidWdmKFN0cmluZyBmb3JtYXQsIE9iamVjdC4uLiBvcykgewoJCVN5c3RlbS5lcnIucHJpbnRmKGZvcm1hdCwgb3MpOwoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgZGVidWcoT2JqZWN0Li4uIG9zKSB7CgkJU3lzdGVtLmVyci5wcmludGxuKGRlZXBUb1N0cmluZyhvcykpOwoJfQp9Cg==