Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Created June 25, 2013 06:26
Show Gist options
  • Save hiroshi-cl/5856381 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/5856381 to your computer and use it in GitHub Desktop.
ACM-ICPC 模擬国内予選 2013 D: 沈みゆく島 [Licence: NYSL Version 0.9982]
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
private static final char[] nums = "0123456789".toCharArray();
private static final char[] opes = "+-*&^|".toCharArray();
private static final Map<String, Long> cache = new HashMap<>();
public static void main(String... args) {
try (final Scanner sc = new Scanner(System.in)) {
while (sc.hasNext()) {
final int N = sc.nextInt();
if (N == 0)
return;
final String s = sc.next();
final long ans = memoize(2 - (N & 1), s, 1);
System.out.println(ans);
cache.clear();
}
}
}
private static long memoize(final int N, final String s, final int sgn) {
if (cache.containsKey(s))
return cache.get(s);
final long ret = solve(N, s, sgn);
cache.put(s, ret);
return ret;
}
private static long solve(final int N, final String s, final int sgn) {
final String t = s.trim();
final long v = evaluate(t);
if (v == -Long.MAX_VALUE)
return Long.MAX_VALUE;
if (N == 0)
return sgn * v;
final int l = t.length();
long max = -Long.MAX_VALUE;
// insert
for (int i = 0; i <= l; i++) {
for (final char c : nums)
max = Math.max(max, -memoize(N - 1, new StringBuilder(s).insert(i, c).toString(), -sgn));
for (final char c : opes)
max = Math.max(max, -memoize(N - 1, new StringBuilder(s).insert(i, c).toString(), -sgn));
}
// remove
for (int i = 0; i < l; i++)
if (s.charAt(i) != '(' && s.charAt(i) != ')')
max = Math.max(max, -memoize(N - 1, s.substring(0, i) + s.substring(i + 1) + " ", -sgn));
return max;
}
private static long evaluate(final String s) {
return new Evaluator(s).evaluate();
}
private static void debug(Object... os) {
System.err.println(Arrays.deepToString(os));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment