Instantly share code, notes, and snippets.

@abeaumont /C.pi
Last active May 1, 2017

Embed
What would you like to do?
GCJ 2017 Round 1C. Problem C. Core Training
import util, mip.
go(T, N, K, U, Xs) =>
X = new_array(N),
X :: 0.0..1.0,
foreach(I in 1..N)
X[I] #>= Xs[I],
X[I] #<= Xs[I] + U
end,
sum(X) #<= sum(Xs) + U,
S #= prod([1.0 - X[I] : I in 1..N]),
solve($[max(S)], [S, X]),
printf(stderr, "Case #%d: %f\n", T, S).
go2(T, N, K, U, Xs) =>
X = new_array(N),
X :: 0.0..1.0,
Y = new_array(N),
Y :: 0..1,
foreach(I in 1..N)
X[I] #>= Xs[I],
X[I] #<= Xs[I] + U
end,
sum(X) #<= sum(Xs) + U,
sum(Y) #= K,
S #= prod([1.0 - (X[I] * Y[I]) : I in 1..N]),
solve($[max(S)], [S, X, Y]),
printf(stderr, "Case #%d: %f\n", T, S).
go3(T, N, K, U, Xs) =>
X = new_array(N),
X :: 0.0..1.0,
foreach(I in 1..N)
X[I] #>= Xs[I],
X[I] #<= Xs[I] + U
end,
sum(X) #<= sum(Xs) + U,
Z = new_array(N+1),
Z :: 0.0..1.0,
Z[1] = 1.0,
foreach(I in 2..N+1)
Z[I] #= Z[I - 1] * (1.0 - X[I-1])
end,
S #= Z[N+1],
solve($[max(S)], [S, X, Z]),
printf(stderr, "Case #%d: %f\n", T, S).
main() =>
[T] = [X.to_number() : X in readln().split()],
foreach(I in 1..T)
[N, K] = [X.to_number() : X in readln().split()],
[U] = [X.to_number() : X in readln().split()],
Xs = [X.to_number() : X in readln().split()],
go3(I, N, K, U, Xs)
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment