Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Created June 25, 2013 06:36
Show Gist options
  • Save hiroshi-cl/5856441 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/5856441 to your computer and use it in GitHub Desktop.
ACM-ICPC 模擬国内予選 2013 E: 小野小町の編集合戦 [Licence: NYSL Version 0.9982]
public class Evaluator {
private static final int RADIX = 10;
private final Tokenizer tokenizer;
public Evaluator(String s) {
this.tokenizer = new Tokenizer(s);
}
public long evaluate() {
try {
final long ans = or();
if(tokenizer.hasNext())
return -Long.MAX_VALUE;
return ans;
} catch (ParsingException| TokenizingException e) {
return -Long.MAX_VALUE;
}
}
private long or() throws ParsingException, TokenizingException {
long ans = xor();
while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
&& tokenizer.peek() == '|') {
tokenizer.poll();
ans |= xor();
}
return ans;
}
private long xor() throws ParsingException, TokenizingException {
long ans = and();
while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
&& tokenizer.peek() == '^') {
tokenizer.poll();
ans ^= and();
}
return ans;
}
private long and() throws ParsingException, TokenizingException {
long ans = plusMinus();
while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
&& tokenizer.peek() == '&') {
tokenizer.poll();
ans &= plusMinus();
}
return ans;
}
private long plusMinus() throws ParsingException, TokenizingException {
long ans = times();
while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
&& (tokenizer.peek() == '+' || tokenizer.peek() == '-')) {
if (tokenizer.poll() == '+')
ans += times();
else
ans -= times();
}
return ans;
}
private long times() throws ParsingException, TokenizingException {
long ans = factor();
while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
&& tokenizer.peek() == '*') {
tokenizer.poll();
ans *= factor();
}
return ans;
}
private long factor() throws ParsingException, TokenizingException {
switch (tokenizer.nextType()) {
case LeftParenthesis: {
tokenizer.poll();
final long ans = or();
if (tokenizer.nextType() != Tokenizer.TokenType.RightParenthesis)
throw new ParsingException();
tokenizer.poll();
return ans;
}
case Number:
return tokenizer.pollLong();
default:
throw new ParsingException();
}
}
private static class ParsingException extends Exception {
private ParsingException() {
}
private ParsingException(String message) {
super(message);
}
private ParsingException(String message, Throwable cause) {
super(message, cause);
}
private ParsingException(Throwable cause) {
super(cause);
}
private ParsingException(String message, Throwable cause,
boolean enableSuppression, boolean writableStackTrace) {
super(message, cause, enableSuppression, writableStackTrace);
}
}
private static class Tokenizer {
private final char[] cs;
private int cursor = 0;
public Tokenizer(final String s) {
cs = s.toCharArray();
}
public boolean hasNext() {
return cursor < cs.length;
}
public TokenType nextType() throws TokenizingException {
if(!hasNext())
throw new TokenizingException();
// except 0
if ('0' < cs[cursor] && cs[cursor] <= '9')
return TokenType.Number;
switch (cs[cursor]) {
case '+':
case '-':
case '*':
case '&':
case '^':
case '|':
return TokenType.Operator;
case '(':
return TokenType.LeftParenthesis;
case ')':
return TokenType.RightParenthesis;
default:
return TokenType.Invalid;
}
}
public long pollLong() throws TokenizingException {
if(!hasNext())
throw new TokenizingException();
long ans = 0;
while (cursor < cs.length && Character.isDigit(cs[cursor]))
ans = ans * RADIX + cs[cursor++] - '0';
return ans;
}
public char poll() throws TokenizingException {
if(!hasNext())
throw new TokenizingException();
return cs[cursor++];
}
public long peekLong() throws TokenizingException {
if(!hasNext())
throw new TokenizingException();
int tmp = cursor;
long ans = 0;
while (tmp < cs.length && Character.isDigit(cs[tmp]))
ans = ans * RADIX + cs[tmp++] - '0';
return ans;
}
public char peek() throws TokenizingException {
if(!hasNext())
throw new TokenizingException();
return cs[cursor];
}
public static enum TokenType {
Number, Operator, LeftParenthesis, RightParenthesis, Invalid
}
}
private static class TokenizingException extends Exception {
private TokenizingException() {
}
private TokenizingException(String message) {
super(message);
}
private TokenizingException(String message, Throwable cause) {
super(message, cause);
}
private TokenizingException(Throwable cause) {
super(cause);
}
private TokenizingException(String message, Throwable cause,
boolean enableSuppression, boolean writableStackTrace) {
super(message, cause, enableSuppression, writableStackTrace);
}
}
}
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