Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Created June 25, 2013 07:53
Show Gist options
  • Save hiroshi-cl/5856742 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/5856742 to your computer and use it in GitHub Desktop.
2011年 冬合宿4日目 Problem C : Fair Game [Licence: NYSL Version 0.9982]
import java.util.*;
import static java.lang.Math.*;
import static java.lang.Integer.*;
public class Main {
public static void main(String... args) {
new Main().run();
}
int n;
double w;
double[] c;
static final double EPS = 1e-9;
static final double INF = 1e20;
static final int REP = 35;
public void run() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
w = sc.nextDouble();
c = new double[n];
for (int i = 0; i < n; i++)
c[i] = sc.nextDouble();
double bd = max(PI, w * log(5.));
double lo = -bd, up = bd;
for (int i = 0; i < REP; i++) {
double x = avg(lo, up);
double s = calc(x) + handicap(x);
if (s > 0)
lo = x;
else
up = x;
}
System.out.println(avg(lo, up));
}
double calc(double x) {
double[] p = new double[1 << n];
for (int i = 1; i < 1 << n; i++) {
int t = n - bitCount(i) + 1;
p[i] = t % 2 == 1 ? -INF : INF;
}
for (int i = 1; i < 1 << n; i++) {
int t = n - bitCount(i) + 1;
if (t % 2 == 1) {
for (int j = 0; j < n; j++)
if ((i & (1 << j)) > 0)
p[i] = max(p[i], p[i ^ (1 << j)] + score(j, x, t));
} else {
for (int j = 0; j < n; j++)
if ((i & (1 << j)) > 0)
p[i] = min(p[i], p[i ^ (1 << j)] - score(j, x, t));
}
}
return p[(1 << n) - 1];
}
double score(int i, double x, double t) {
return sin(x + t + c[i]);
}
double handicap(double x) {
return (2 / (1 + exp(x / w)) - 1) * n;
}
double avg(double x, double y) {
return .5 * (x + y);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment