ダメだったアプローチ


 * 事前計算されたDP
  
各試験紙に同じ数のボトルを割り当てると仮定して、
   DP[毒の数][試験紙の数][残りラウンド数] = 期待値が最大になるようなボトルの割合。
   TLE。

 * 各試験紙に同じ数のボトルを割り当てると仮定して、SA, 深さ制限dfs with 黄金分割探索。


使ったアプローチ


 * 試験紙が毒の数より圧倒的に多いとき、
   二分探索のようにして、毒の範囲をしぼる。

 * 試験紙>=毒の数のとき、
   試験紙の補集合も一枚の試験紙のように使える。
   残りのラウンドを見て、試験紙にボトルを等分する。

 * その他
   毎ラウンド、シミュレーションして (再利用できる試験紙の数 ^ 残りラウンド数) * ボトルの数 が最大になるように、試験紙にボトルを割り当てる。




source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Calendar;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Objects;
import java.util.TimeZone;

public class PoisonedWine {
private static final int unknown = 0;
private static final int good = -1;
private static final int bad = -2;

public static final Watch watch = new Watch();
public static final XorShift rng = new XorShift(System.nanoTime());

private int numBottles;
private int numRounds;
private int numPoisonedBottles;
private int numPapers;

private int numGoods;
private int numBads;
private int availablePapers;
private int[] states;

public int[] testWine(int numBottles, int numPapers, int numRounds, int numPoisonedBottles) {
CalendarUtils.printDate(Constants.currentTime, Constants.endTime);

if (numPoisonedBottles > numPapers + 5) {
return new PoisonedWineSubmission3().testWine(numBottles, numPapers, numRounds, numPoisonedBottles);
}

init(numBottles, numPapers, numRounds, numPoisonedBottles);

solve();

int[] makeSolution = makeSolution(states);

Utils.debug("time", watch.getSecondString(), "score", calculateScore(numBottles, numPoisonedBottles, numGoods), "numGoods", numGoods);
return makeSolution;
}

private int nextRestartRound = 0;

private void solve() {
Bottles unknownBottles = restart(numBottles, numPoisonedBottles, states);

Utils.debug("round", "numBottles", "score", "numGoods", "Papers", "size", "prob", "ev");

for (int round = 0; round < numRounds; round++) {

if (availablePapers == 0) {
break;
}
ArrayList<Group> groups = makeGroup(unknownBottles, round);

test(groups);

update(groups);

{
ArrayList<Integer> sizes = new ArrayList<>();
for (Group group : groups) {
sizes.add(group.bottles.get(0).indexes2.size());
}

if (!sizes.isEmpty()) {
Utils.debug(round, unknownBottles.indexes2.size(), (int) calculateScore(numBottles, numPoisonedBottles, numGoods), numGoods, availablePapers, sizes);
} else {
Utils.debug(round, unknownBottles.indexes2.size(), (int) calculateScore(numBottles, numPoisonedBottles, numGoods), numGoods, availablePapers);
}
}

if (groups.size() == 1) {
unknownBottles.indexes2 = groups.get(0).complement.indexes2;
unknownBottles.infBads = groups.get(0).complement.supBads;
unknownBottles.supBads = groups.get(0).complement.supBads;

if (unknownBottles.isAllGood()) {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
} else if (round + 1 == nextRestartRound) {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
} else {
}
} else {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
}
}

}

private void update(ArrayList<Group> groups) {
for (Group group : groups) {
for (Bottles bottles : group.bottles) {
if (bottles.isAllGood()) {
updateStateGood(bottles.indexes2);
}
if (bottles.isAllBad()) {
updateStateBad(bottles.indexes2);
}
updateExpectedProbability(bottles.indexes2, (double) bottles.infBads / bottles.indexes2.size());
}
{
if (group.complement.isAllGood()) {
updateStateGood(group.complement.indexes2);
}
if (group.complement.isAllBad()) {
updateStateBad(group.complement.indexes2);
}
updateExpectedProbability(group.complement.indexes2, (double) group.complement.supBads / group.complement.indexes2.size());
}
}
}

private Bottles restart(int numBottles, int numPoisonedBottles, int[] states) {
Bottles bottles = new Bottles();

for (int i = 0; i < numBottles; i++) {
if (states[i] == bad) {
} else if (states[i] == good) {
} else {
bottles.indexes2.add(i);
}
}

bottles.infBads = numPoisonedBottles;
bottles.supBads = numPoisonedBottles;

updateExpectedProbability(bottles.indexes2, (double) bottles.supBads / bottles.indexes2.size());

ArrayList<Pair<Double, Integer>> countAndIndexPairs = new ArrayList<>();
for (int i = 0; i < bottles.indexes2.size(); i++) {
int index = bottles.indexes2.get(i).intValue();
countAndIndexPairs.add(new Pair<Double, Integer>(maxExpectedProbability[index] + 1e-6 * rng.nextDouble(), index));
}
Collections.sort(countAndIndexPairs);

bottles.indexes2.clear();
for (int i = 0; i < countAndIndexPairs.size(); i++) {
bottles.indexes2.add(countAndIndexPairs.get(i).second.intValue());
}

numBottlesAtRestart = bottles.indexes2.size();

double paperPerPoison = (double) numPapers / numPoisonedBottles;
int restartRounds = (int) Math.ceil(numRounds / paperPerPoison);
nextRestartRound += restartRounds;

Utils.debug("restart", "unknowns.size()", bottles.indexes2.size(), "numPoisonedBottles - numBads", numPoisonedBottles + " - " + numBads + " = " + (numPoisonedBottles - numBads));

return bottles;
}

private int numBottlesAtRestart;
private double[] maxExpectedProbability;
private double[] minExpectedProbability;

private void updateExpectedProbability(ArrayList<Integer> indexes, double p) {
for (Integer index : indexes) {
maxExpectedProbability[index.intValue()] = Math.max(maxExpectedProbability[index.intValue()], p);
minExpectedProbability[index.intValue()] = Math.min(maxExpectedProbability[index.intValue()], p);
}
}

private void updateStateBad(ArrayList<Integer> indexes) {
for (Integer index : indexes) {
if (states[index.intValue()] == unknown) {
states[index.intValue()] = bad;
numBads++;
}
}
}

private void updateStateGood(ArrayList<Integer> indexes2) {
for (Integer index : indexes2) {
if (states[index.intValue()] == unknown) {
states[index.intValue()] = good;
numGoods++;
}
}
}

private void test(ArrayList<Group> groups) {
ArrayList<Bottles> bottles = new ArrayList<>();
ArrayList<Group> groups2 = new ArrayList<>();
for (Group group : groups) {
for (int j = 0; j < group.bottles.size(); j++) {
if (group.bottles.get(j).indexes2.size() == 0) {
continue;
}

bottles.add(group.bottles.get(j));
groups2.add(group);
}
}

boolean[] isPoisoned = useTestStrips(bottles);
assert isPoisoned.length == bottles.size();

for (int i = 0; i < isPoisoned.length; i++) {
if (isPoisoned[i]) {
bottles.get(i).supBads = groups2.get(i).supBads;
bottles.get(i).infBads = 1;

groups2.get(i).complement.supBads--;
groups2.get(i).complement.infBads = 0;
availablePapers--;
} else {
bottles.get(i).supBads = 0;
bottles.get(i).infBads = 0;
}
}

for (Group group : groups) {
int sumInfBads = 0;
for (Bottles bottles2 : group.bottles) {
sumInfBads += bottles2.infBads;
}
for (Bottles bottles2 : group.bottles) {
bottles2.supBads = Math.min(bottles2.supBads, group.supBads - (sumInfBads - bottles2.infBads));
}
}

}

private ArrayList<Group> makeGroup(Bottles bottles0, int round) {
if (bottles0.isAllGood() || bottles0.isAllBad()) {
return new ArrayList<>();
}

ArrayList<Group> groups2 = new ArrayList<>();

int numGroups = availablePapers / (2 * bottles0.supBads - 1);
numGroups /= numRounds - round;
if (numGroups == 0) {
numGroups = 1;
}

for (int i = 0; i < numGroups; i++) {
groups2.add(new Group(bottles0.infBads, bottles0.supBads));
}

int[] groupPapers = new int[numGroups];
for (int paper = 0; paper < availablePapers; paper++) {
groupPapers[paper % groups2.size()]++;
}

for (int i = 0; i < numGroups; i++) {
Group group = groups2.get(i);

Result bestResult = new Result();
double paperPerPoison = (double) numPapers / numPoisonedBottles;
int restartRounds = (int) Math.ceil(numRounds / paperPerPoison);
double eachRoundBottles = (double) numBottlesAtRestart / restartRounds;
int complement = (round + 1 == nextRestartRound) ? 1 : 0;
double size = eachRoundBottles / (groupPapers[i] + complement);

bestResult.bestSize = (int) Math.round(size);
if (bestResult.bestSize == 0) {
bestResult.bestSize = 1;
}

for (int paper = 0; paper < groupPapers[i]; paper++) {
group.bottles.add(new Bottles());
}

for (int sizeIndex = 0; sizeIndex < bottles0.indexes2.size(); sizeIndex++) {
int toIndex = sizeIndex;
for (int j = 0; j < i; j++) {
toIndex /= (group.bottles.size() + 1);
}
toIndex = toIndex % (group.bottles.size() + 1);
int value = bottles0.indexes2.get(sizeIndex).intValue();

if (toIndex >= 0 && toIndex < group.bottles.size() && group.bottles.get(toIndex).indexes2.size() < bestResult.bestSize) {
group.bottles.get(toIndex).indexes2.add(value);
} else {
group.complement.indexes2.add(value);
}
}

}
return groups2;
}

private void init(int numBottles, int numPapers, int numRounds, int numPoisonedBottles) {
Utils.debug("numBottles", numBottles, "numPapers", numPapers, "numRounds", numRounds, "numPoisonedBottles", numPoisonedBottles);

this.numBottles = numBottles;
this.numPapers = numPapers;
this.numRounds = numRounds;
this.numPoisonedBottles = numPoisonedBottles;

this.states = new int[numBottles];
Arrays.fill(states, unknown);
this.maxExpectedProbability = new double[numBottles];
Arrays.fill(maxExpectedProbability, 0);
this.minExpectedProbability = new double[numBottles];
Arrays.fill(minExpectedProbability, 1);

this.numGoods = 0;
this.numBads = 0;

this.availablePapers = numPapers;
}

private double calculateScore(int numBottles, int numPoisonedBottles, int numGoods) {
double d = (double) numGoods / (numBottles - numPoisonedBottles);
double score = 1e6 * d * d;
return score;
}

private int[] makeSolution(int[] states) {
ArrayList<Integer> unknownAndBad = new ArrayList<>();
for (int i = 0; i < states.length; i++) {
if (states[i] != good) {
unknownAndBad.add(i);
}
}
int[] ret = new int[unknownAndBad.size()];
for (int i = 0; i < unknownAndBad.size(); i++) {
ret[i] = unknownAndBad.get(i).intValue();
}
return ret;
}

private boolean[] useTestStrips(ArrayList<Bottles> bottles) {
String[] tests = new String[bottles.size()];
for (int i = 0; i < bottles.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < bottles.get(i).indexes2.size(); j++) {
if (j > 0) {
sb.append(",");
}
sb.append(bottles.get(i).indexes2.get(j));
}
tests[i] = sb.toString();
}

int[] testResults = PoisonTest.useTestStrips(tests);

boolean[] isPoisoned = new boolean[testResults.length];
for (int i = 0; i < isPoisoned.length; i++) {
isPoisoned[i] = testResults[i] == 1;
}
return isPoisoned;
}

public static void main(String[] args) {
try {
BR.br = new BufferedReader(new InputStreamReader(System.in));

int numBottles = BR.readInt();
int testPapers = BR.readInt();
int testRounds = BR.readInt();
int numPoison = BR.readInt();

PoisonedWine pw = new PoisonedWine();
int[] ret = pw.testWine(numBottles, testPapers, testRounds, numPoison);

System.out.println(ret.length);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

class Group {
ArrayList<Bottles> bottles;
Bottles complement;
int supBads;
int infBads;

public Group(int infBads, int supBads) {
bottles = new ArrayList<>();

this.supBads = supBads;
this.infBads = infBads;

complement = new Bottles();
complement.infBads = infBads;
complement.supBads = supBads;
}
}

class Bottles {
public boolean isComplement;
ArrayList<Integer> indexes2;
int supBads;
int infBads;

public Bottles() {
indexes2 = new ArrayList<>();
}

public boolean isAllGood() {
return supBads == 0;
}

public boolean isAllBad() {
return infBads >= indexes2.size();
}

@Override
public String toString() {
return Utils.toString("isComplement", isComplement, "supBads", supBads, "infBads", infBads, "size", indexes2.size());
}

}

class ArrayListInt {
private static final int DEFAULT_CAPACITY = 10;

private static final int[] EMPTY_ELEMENTDATA = {};

private static final int[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient int[] elementData;

private int size;

public ArrayListInt(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new int[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}

public ArrayListInt() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayListInt(ArrayListInt c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
elementData = Arrays.copyOf(elementData, size);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}

public void trimToSize() {
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}

public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}

private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

public boolean contains(int o) {
return indexOf(o) >= 0;
}

public int indexOf(int o) {
for (int i = 0; i < size; i++)
if (o == elementData[i])
return i;
return -1;
}

public int lastIndexOf(int o) {
for (int i = size - 1; i >= 0; i--)
if (o == elementData[i])
return i;
return -1;
}

public Object clone() {
try {
ArrayListInt v = (ArrayListInt) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}

public int[] toArray() {
return Arrays.copyOf(elementData, size);
}

int elementData(int index) {
return elementData[index];
}

public int get(int index) {
rangeCheck(index);

return elementData(index);
}

public int set(int index, int element) {
rangeCheck(index);

int oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

public boolean add(int e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}

public void add(int index, int element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}

public int removeByIndex(int index) {
rangeCheck(index);
int oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = 0;
return oldValue;
}

public boolean remove(int o) {
for (int index = 0; index < size; index++)
if (o == elementData[index]) {
fastRemove(index);
return true;
}
return false;
}

private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = 0;
}

public void clear() {
for (int i = 0; i < size; i++)
elementData[i] = 0;

size = 0;
}

public boolean addAll(ArrayListInt c) {
int[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

public boolean addAll(int index, ArrayListInt c) {
rangeCheckForAdd(index);

int[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);

System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

protected void removeRange(int fromIndex, int toIndex) {
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
int newSize = size - (toIndex - fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = 0;
}
size = newSize;
}

private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}

public boolean removeAll(ArrayListInt c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}

public boolean retainAll(ArrayListInt c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}

private boolean batchRemove(ArrayListInt c, boolean complement) {
final int[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
if (r != size) {
System.arraycopy(elementData, r, elementData, w, size - r);
w += size - r;
}
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = 0;
size = w;
modified = true;
}
}
return modified;
}
}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
System.err.flush();
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

final class Constants {
public static final boolean TIMER = true;
public static final boolean LOCAL = true;
public static final boolean DEBUG = true;
public static final boolean ASSERTION = true;

private static final String id = "GMT-4:00";
public static final Calendar currentTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
}

public static final Calendar startTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
startTime.set(2017, 7 - 1, 5, 21, 0, 0);
}

public static final Calendar endTime = Calendar.getInstance(TimeZone.getTimeZone(id));

static {
endTime.set(2017, 7 - 1, 19, 21, 0, 0);
}

private Constants() {
}
}

class Result {
int bestSize;
double bestExpectedValue;
}

class CalendarUtils {
private CalendarUtils() {
}

public static final void printDate(Calendar currentTime, Calendar endTime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;

long end = endTime.getTimeInMillis();

long current = currentTime.getTimeInMillis();

long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);

int year = currentTime.get(Calendar.YEAR);
int month = 1 + currentTime.get(Calendar.MONTH);
int day = currentTime.get(Calendar.DAY_OF_MONTH);
int hour = currentTime.get(Calendar.HOUR_OF_DAY);
int minute = currentTime.get(Calendar.MINUTE);
int second = currentTime.get(Calendar.SECOND);

Utils.debug(String.format("%02d/%02d/%02d %02d:%02d:%02d Time Left %d Hrs %d Mins", year, month, day, hour, minute, second, numHours, numMinutes));
}

public static final String toStringDateAndTimeLeft(Calendar currenttime, Calendar endtime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;
long end = endtime.getTimeInMillis();
long current = currenttime.getTimeInMillis();
long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);
int year = currenttime.get(Calendar.YEAR);
int month = 1 + currenttime.get(Calendar.MONTH);
int day = currenttime.get(Calendar.DAY_OF_MONTH);
int hour = currenttime.get(Calendar.HOUR_OF_DAY);
int minute = currenttime.get(Calendar.MINUTE);
int second = currenttime.get(Calendar.SECOND);
return String.format("%02d/%02d/%02d %02d:%02d:%02d Time Left %d Hrs %d Mins", year, month, day, hour, minute, second, numHours, numMinutes);
}

public static final String toStringDate(Calendar currenttime, Calendar endtime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;
long end = endtime.getTimeInMillis();
long current = currenttime.getTimeInMillis();
long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);
int year = currenttime.get(Calendar.YEAR);
int month = 1 + currenttime.get(Calendar.MONTH);
int day = currenttime.get(Calendar.DAY_OF_MONTH);
int hour = currenttime.get(Calendar.HOUR_OF_DAY);
int minute = currenttime.get(Calendar.MINUTE);
int second = currenttime.get(Calendar.SECOND);
return String.format("%02d/%02d/%02d %02d:%02d:%02d", year, month, day, hour, minute, second);
}

public static final String toStringTimeLeft(Calendar currenttime, Calendar endtime) {
int oneSecond = 1000;
int oneMinute = 60 * oneSecond;
int oneHour = 60 * oneMinute;
long end = endtime.getTimeInMillis();
long current = currenttime.getTimeInMillis();
long numMinutes = Math.max(0, ((end - current) % oneHour) / oneMinute);
long numHours = Math.max(0, (end - current) / oneHour);
int year = currenttime.get(Calendar.YEAR);
int month = 1 + currenttime.get(Calendar.MONTH);
int day = currenttime.get(Calendar.DAY_OF_MONTH);
int hour = currenttime.get(Calendar.HOUR_OF_DAY);
int minute = currenttime.get(Calendar.MINUTE);
int second = currenttime.get(Calendar.SECOND);
return String.format("Time Left %d Hrs %d Mins", numHours, numMinutes);
}

}

class Watch {
private long start;

public Watch() {
init();
}

public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}

public void init() {
init(System.nanoTime());
}

private void init(long start) {
this.start = start;
}

public String getSecondString() {
return toString(getSecond());
}

public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}

class PoisonedWineSubmission3 {
private static final int unknown = 0;
private static final int good = -1;
private static final int bad = -2;

private XorShift rng = new XorShift(System.nanoTime());

public int[] testWine(int numBottles, int numStrips, int numRounds, int numPoisonedBottles) {
Utils.debug("numBottles", numBottles, "numStrips", numStrips, "numRounds", numRounds, "numPoisonedBottles", numPoisonedBottles);

int[] states = new int[numBottles];
Arrays.fill(states, unknown);

int numGoods = 0;
int numBads = 0;

int availableStrips = numStrips;
ArrayListInt all = new ArrayListInt();
for (int i = 0; i < numBottles; i++) {
all.add(i);
}
int[] array = all.toArray();
shuffle(array, rng);
BottlesSubmission3 unknownBottles = new BottlesSubmission3(array, numPoisonedBottles, false);
for (int round = 0; round < numRounds; round++) {

if (availableStrips == 0) {
break;
}

if (unknownBottles.indexes.length == 0) {
unknownBottles = restart(numBottles, numPoisonedBottles, states);
}

if (unknownBottles.isAllBad() || unknownBottles.isAllGood()) {
if (unknownBottles.isAllGood()) {
for (int index : unknownBottles.indexes) {
states[index] = good;
numGoods++;
}
}
unknownBottles = restart(numBottles, numPoisonedBottles, states);
if (unknownBottles.isAllBad() || unknownBottles.isAllGood()) {
break;
}
}
boolean[] simpleModel = getSimpleModel(unknownBottles.indexes.length, unknownBottles.numBads);

int maxBatchSize = (int) (Math.ceil((double) unknownBottles.indexes.length / (availableStrips)));

double bestBatchSize2 = -1;
double bestNumGoods = -1;

for (int batchSize = 1; batchSize <= maxBatchSize; batchSize++) {

int nextStrips = 0;
for (int strip = 0; strip < availableStrips; strip++) {
if (isGood(simpleModel, batchSize, strip)) {
nextStrips++;
}
}

if (Math.pow(nextStrips, numRounds - round) * batchSize > bestNumGoods) {
bestNumGoods = Math.pow(nextStrips, numRounds - round) * batchSize;
bestBatchSize2 = batchSize;
}

}
int bestBatchSize = (int) bestBatchSize2;
LinkedList<Integer> availableIndexes = new LinkedList<>();
for (int index : unknownBottles.indexes) {
availableIndexes.addLast(index);
}

ArrayList<BottlesSubmission3> bottleSets = new ArrayList<>();
for (int stripIndex = 0; stripIndex < availableStrips; stripIndex++) {
ArrayListInt indexes2 = new ArrayListInt();
for (int i = 0; i < bestBatchSize; i++) {
if (availableIndexes.size() > 0) {
indexes2.add(availableIndexes.pollFirst().intValue());
}
}

if (indexes2.size() > 0) {
bottleSets.add(new BottlesSubmission3(indexes2.toArray(), 0, true));
}
}

boolean[] isPoisoned = test((BottlesSubmission3[]) bottleSets.toArray(new BottlesSubmission3[bottleSets.size()]));
int nextBads = unknownBottles.numBads;

assert isPoisoned.length == bottleSets.size();

for (int i = 0; i < isPoisoned.length; i++) {
if (isPoisoned[i]) {
bottleSets.get(i).numBads = 1;
nextBads--;

if (bottleSets.get(i).indexes.length == 1) {
for (int index : bottleSets.get(i).indexes) {
states[index] = bad;
numBads++;
}
} else {
}
availableStrips--;
} else {
for (int index : bottleSets.get(i).indexes) {
states[index] = good;
numGoods++;
}
}
}
int[] toArray = new int[availableIndexes.size()];
for (int i = 0; i < toArray.length; i++) {
toArray[i] = availableIndexes.pollFirst().intValue();
}
unknownBottles = new BottlesSubmission3(toArray, nextBads, false);

Utils.debug("round", round, "score", (int) calculateScore(numBottles, numPoisonedBottles, numGoods), "numGoods", numGoods, "Strips", availableStrips, "size", bestBatchSize);
}
int[] makeSolution = makeSolution(states);
Utils.debug("time", PoisonedWine.watch.getSecondString(), "score", calculateScore(numBottles, numPoisonedBottles, numGoods), "numGoods", numGoods);

return makeSolution;

}

public static final void shuffle(int[] a, XorShift rng) {
for (int i = a.length - 1; i >= 0; i--) {
int j = (int) ((i + 1) * rng.nextDouble());
{
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
}

private boolean[] getSimpleModel(int numBottles, int numPoisonedBottles) {
boolean[] simpleModel = new boolean[numBottles];
{
double badProbability = (double) numPoisonedBottles / numBottles;
double sumBadProbability = 1e-9;
for (int i = 0; i < simpleModel.length; i++) {
sumBadProbability += badProbability;
if (sumBadProbability >= 1) {
sumBadProbability -= 1;
simpleModel[i] = true;
}
}

int count = 0;
for (int i = 0; i < simpleModel.length; i++) {
if (simpleModel[i]) {
count++;
}
}
assert count == numPoisonedBottles : Utils.toString(count, numPoisonedBottles, numBottles);
}
return simpleModel;
}

private boolean isGood(boolean[] simpleModel, int batchSize, int strip) {
for (int i = 0; i < batchSize; i++) {
if (strip * batchSize + i < simpleModel.length && simpleModel[strip * batchSize + i]) {
return false;
}
}
return true;
}

private double calculateScore(int numBottles, int numPoisonedBottles, int numGoods) {
double d = (double) numGoods / (numBottles - numPoisonedBottles);
double score = 1e6 * d * d;
return score;
}

private BottlesSubmission3 restart(int numBottles, int numPoisonedBottles, int[] states) {
int numBads = 0;
ArrayListInt unknowns = new ArrayListInt();
for (int i = 0; i < numBottles; i++) {
if (states[i] == bad) {
numBads++;
} else if (states[i] == good) {
} else {
unknowns.add(i);
}
}
Utils.debug("restart", "unknowns.size()", unknowns.size(), "numPoisonedBottles - numBads", numPoisonedBottles + " - " + numBads + " = " + (numPoisonedBottles - numBads));
int[] array = unknowns.toArray();
shuffle(array, rng);
return new BottlesSubmission3(array, numPoisonedBottles - numBads, false);
}

private int[] makeSolution(int[] states) {
ArrayList<Integer> unknownAndBad = new ArrayList<>();
for (int i = 0; i < states.length; i++) {
if (states[i] != good) {
unknownAndBad.add(i);
}
}
int[] ret = new int[unknownAndBad.size()];
for (int i = 0; i < unknownAndBad.size(); i++) {
ret[i] = unknownAndBad.get(i).intValue();
}
return ret;
}

private boolean[] test(BottlesSubmission3[] bottleSets) {
String[] tests = new String[bottleSets.length];
for (int i = 0; i < bottleSets.length; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < bottleSets[i].indexes.length; j++) {
if (j > 0) {
sb.append(",");
}
sb.append(bottleSets[i].indexes[j]);
}
tests[i] = sb.toString();
}
int[] testRes = PoisonTest.useTestStrips(tests);
boolean[] isPoisoned = new boolean[testRes.length];
for (int i = 0; i < isPoisoned.length; i++) {
isPoisoned[i] = testRes[i] == 1;
}
return isPoisoned;
}
}

class BottlesSubmission3 {
int[] indexes;
int numBads;

public BottlesSubmission3(int[] indexes, int numBads, boolean isChecked) {
super();
this.indexes = indexes;
this.numBads = numBads;
}

public boolean isAllGood() {
return numBads <= 0;
}

public boolean isAllBad() {
return numBads >= indexes.length;
}

public double getGoodProbability() {
return 1 - getBadProbability();
}

public double getBadProbability() {
return (double) numBads / indexes.length;
}

}