どの base からどれだけ troop を送るか決める問題で、Codingame の Ghost in the Cell と同じ問題だと思いました。


考えただけのアプローチ


ディープラーニングに任せて、自分は何もしない。
1場面づつ自分でやってみて、評価関数の教師あり学習。


やってみてダメだったアプローチ


SA+モンテカルロシミュレーション



 Approach

序盤


1個か2個の自分の base からできるだけ多く攻撃して、自分のにできたらする。


中盤


Troop の送り先 : 敵の base または自分の base でサイズが200(後で最適化したら300とかの方が良いとでた)以下のもの。
最小費用流で送り主と送り先をmax(2,ceil(送り主数 / 送り先数)):1にマッチングする。
最小費用流のコスト : 送るのにかかる時間 * その base を自分のにしたときの自分の全ての base の (attackT[owner]/2 * 敵から攻撃される確率 )の和


全滅させられそうな時


自分のサイズが 1500 未満の時は、最も近い troop との距離が2以下になったとき、最も遠い base に逃げる。
自分のサイズが 1500 以上の時は、最も近い troop との距離が2以下になったとき、
最も((現在の base )から(行き先の base )までの距離 + (行き先の base )から(行き先の base から最も近い base )までの距離)が大きい base に逃げる。



Approach in English(Google Translate) 



Early stage


I attack as much as possible from one or two my base and I can do it for myself.


Middle stage


Destination of Troop: Size of 200 or less on the base of the enemy or your base (below 300 if you optimized later) or less.
Match the sender and destination to max (2, ceil (number of senders / destinations)): 1 with minimum cost flow.
Cost of minimum cost flow: time to send * Sum of all your base (attackT [owner] * probability of being attacked by enemies) when you make that base yourself


When it is likely to be annihilated


When your size is less than 1500, escape to the furthest base when the distance to the nearest troop becomes 2 or less.
When your size is 1500 or more, when the distance to the nearest troop becomes 2 or less,
Escape to the base with the largest distance (distance from (current base) to (destination base) + (destination base) to (base closest to base of destination).


source code



import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;

//Example scores:
//0) 1657.7984865328203
//1) 90.5096600125314
//2) 1841.1329159343964
//3) 1910.5016049005667
//4) 1876.8965543368483
//5) 1454.4036603297495
//6) 1763.7071055495733
//7) 111.5825278448541
//8) 198.76179380610597
//9) 1747.8803320547408

public class AbstractWars {
private static final TimerManager timer = new TimerManager();
private int numBases;
private int speed;
private Base[] bases;
private double[][] distance;
private int myOwnerValue = 0;

public int init(int[] baseLocations, int speed) {
timer.start("init");
this.numBases = baseLocations.length / 2;
this.speed = speed;

Utils.debug("numBases", numBases, "speed", speed);

bases = new Base[numBases];
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
bases[baseIndex] = new Base();
bases[baseIndex].c = baseLocations[2 * baseIndex + 0];
bases[baseIndex].r = baseLocations[2 * baseIndex + 1];
bases[baseIndex].baseIndex = baseIndex;
}
this.distance = new double[numBases][numBases];
for (int baseIndexFrom = 0; baseIndexFrom < numBases; baseIndexFrom++) {
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
distance[baseIndexFrom][baseIndexTo] = distance(bases[baseIndexFrom], bases[baseIndexTo]);
}
}
timer.stop("init");
return 0;
}

private int getTime(double distance) {
return (int) Math.ceil(distance / speed);
}

ArrayList<Base> myBases = new ArrayList<>();
ArrayList<Base> othersBases = new ArrayList<>();

private int turn;
private int numAIs;

public int[] sendTroops(int[] bases, int[] troops) {
updateInformation(bases, troops);
return solve();
}

private int[][] usedCapacity = new int[102][3000];

private boolean first = true;

private int[] solve() {

if (first && (myBases.size() == 0 || myBases.size() == numBases)) {
Utils.debug("turn", turn, myBases.size() == 0, myBases.size() == numBases);
timer.print();
first = false;
}

if (isMyLastState()) {
return myLastStateHand();
}

if (isFirstTrun()) {
return firstHand();
}

if (isWin()) {
return sendFar();
}

timer.start("normal");

int maxShareOwner = getMaxShareOwnerWithOutMe();
double[] sumExpectedTroopSize = new double[numBases];
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
int currentOwner = bases[baseIndex].owner;
if (bases[baseIndex].owner == myOwnerValue) {
bases[baseIndex].owner = maxShareOwner;
} else {
bases[baseIndex].owner = myOwnerValue;
}

double[] expectedTroopSize = calculateExpectedTroopSize();
for (int baseIndex2 = 0; baseIndex2 < numBases; baseIndex2++) {
if (isMyBase(bases[baseIndex2])) {
sumExpectedTroopSize[baseIndex] += expectedTroopSize[baseIndex2];
}
}

bases[baseIndex].owner = currentOwner;

}

IntArray solution = new IntArray();
int[] baseIndexToMinCostBaseIndex = mincostflow(sumExpectedTroopSize);
for (Base my : myBases) {

int from = my.baseIndex;
int to = baseIndexToMinCostBaseIndex[from];
if (my.size >= 988) {
sendHalf(solution, from, to);
continue;
}

}

updateTurn();
timer.stop("normal");

return solution.toArray();

}

private int[] firstHand() {
timer.start("firstHand");
IntArray solution = new IntArray();
boolean[] used = new boolean[numBases];
for (Base my : myBases) {
if (used[my.baseIndex]) {
continue;
}
for (Base other : othersBases) {
if (canUse(other.baseIndex, turn) && canGetByAll(my, other)) {
sendAll(solution, my.baseIndex, other.baseIndex);
Utils.debug("firstHand", "turn", turn, "growthRate", my.growthRate, other.growthRate);
used[my.baseIndex] = true;
break;
}
}
}

for (Base my : myBases) {
if (used[my.baseIndex]) {
continue;
}
for (Base my2 : myBases) {
if (used[my.baseIndex]) {
continue;
}
if (used[my2.baseIndex]) {
continue;
}
if (my2.baseIndex == my.baseIndex) {
continue;
}
for (Base other : othersBases) {
if (canUse(other.baseIndex, turn) && canGetByAll(my, my2, other)) {
sendAll(solution, my.baseIndex, other.baseIndex);
sendAll(solution, my2.baseIndex, other.baseIndex);
Utils.debug("firstHand", "turn", turn, "growthRate", my.growthRate, my2.growthRate, other.growthRate);
used[my.baseIndex] = true;
used[my2.baseIndex] = true;
break;
}
}
}
}

updateTurn();

timer.stop("firstHand");
return solution.toArray();
}

private boolean canGet(Base my, Base other) {
int myTroopSize = my.size / 2;
int otherSize = other.size;
int maxTime = getTime(distance[my.baseIndex][other.baseIndex]);
for (int time = 1; time <= maxTime; time++) {
if (otherSize > 0) {
otherSize += (other.growthRate == 0 ? 3 : other.growthRate) + otherSize / 100;
}
if (otherSize > attackT[other.owner]) {
otherSize -= otherSize / 2;
}
}
return myTroopSize > 1 + 1.2 * otherSize;
}

private boolean canGetByAll(Base my, Base other) {
int myTroopSize = my.size - 1;
int otherSize = other.size;
int maxTime = getTime(distance[my.baseIndex][other.baseIndex]);

if (myTroopSize < 1 + 1.2 * otherSize + maxTime * (other.growthRate == 0 ? 3 : other.growthRate)) {
return false;
}

for (int time = 1; time <= maxTime; time++) {
if (otherSize > 0) {
otherSize += (other.growthRate == 0 ? 3 : other.growthRate) + otherSize / 100;
}
}
return myTroopSize > 1 + 1.2 * otherSize;
}

private boolean canGetByAll(Base my, Base my2, Base other) {
int myTroopSize = my.size - 1;
int my2TroopSize = my2.size - 1;
double otherSize = other.size;
int maxTime = getTime(distance[my.baseIndex][other.baseIndex]);
int maxTime2 = getTime(distance[my2.baseIndex][other.baseIndex]);
if (maxTime > maxTime2) {
{
int swap = maxTime;
maxTime = maxTime2;
maxTime2 = swap;
}
{
int swap = myTroopSize;
myTroopSize = my2TroopSize;
my2TroopSize = swap;
}
}

if (myTroopSize + my2TroopSize < 1 + 1.2 * otherSize + maxTime * (other.growthRate == 0 ? 3 : other.growthRate)) {
return false;
}

for (int time = 1; time <= maxTime; time++) {
if (otherSize > 0) {
otherSize += (other.growthRate == 0 ? 3 : other.growthRate) + otherSize / 100;
}
}
otherSize -= (1.0 / 1.2) * myTroopSize;
for (int time = maxTime + 1; time <= maxTime2; time++) {
if (otherSize > 0) {
otherSize += (other.growthRate == 0 ? 3 : other.growthRate) + otherSize / 100;
}
}
return my2TroopSize > 1 + 1.2 * otherSize;
}

private boolean isFirstTrun() {
return turn <= 28;
}

private void sendAll(IntArray solution, int from, int to) {
if (solution.length / 2 + 10 >= numBases) {
return;
}

int size = bases[from].size;
while (size >= 2) {
solution.add(from);
solution.add(to);
size -= size / 2;
}
int time2 = getTime(distance[from][to]);
for (int time = 0; time < time2; time++) {
updateCapacity(to, time);
}
}

private boolean canUse(int baseIndexTo, int turn) {
return usedCapacity[baseIndexTo][turn] == 0;
}

private void updateCapacity(int to, int time) {
usedCapacity[to][turn + time]++;
}

private void sendHalf(IntArray solution, int from, int to) {
solution.add(from);
solution.add(to);
int time2 = getTime(distance[from][to]);
for (int time = 0; time < time2; time++) {
updateCapacity(to, time);
}
}

private int[] mincostflow(double[] sumExpectedTroopSize) {
ArrayList<Base> toBases = new ArrayList<>();
for (int i = 0; i < bases.length; i++) {
if (isMyBase(bases[i])) {
continue;
}
toBases.add(bases[i]);
}

for (Base my : myBases) {
if (my.size < 200) {
toBases.add(my);
}
}

mcf.clear(2 * maxBases + 2);
int s = myBases.size() + toBases.size();
int t = s + 1;

for (int i = 0; i < myBases.size(); i++) {
mcf.addEdge(s, i, 1, 0);
}

for (int i = 0; i < myBases.size(); i++) {
for (int j = 0; j < toBases.size(); j++) {
long cost = (long) (1e2 * (getTime(distance[myBases.get(i).baseIndex][toBases.get(j).baseIndex]) * sumExpectedTroopSize[toBases.get(j).baseIndex]));
if (myBases.get(i).baseIndex == toBases.get(j).baseIndex) {
cost = mcf.INF;
}
if (cost > mcf.INF) {
cost = mcf.INF;
}
mcf.addEdge(i, myBases.size() + j, 1, cost);
}
}
for (int i = 0; i < toBases.size(); i++) {
mcf.addEdge(myBases.size() + i, t, Math.max(2, (int) Math.ceil((double) myBases.size() / toBases.size())), 0);
}
long c = mcf.minCostFlow(s, t, myBases.size());
int[] baseIndexToMinCostBaseIndex = new int[numBases];
Arrays.fill(baseIndexToMinCostBaseIndex, -1);
for (int myBaseIndex = 0; myBaseIndex < myBases.size(); myBaseIndex++) {
ArrayList<Edge> edges = mcf.G.get(myBaseIndex);
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);
if (e.cap != 0) {
continue;
}
if (e.to == s) {
continue;
}

int minCostBaseIndex = toBases.get(e.to - myBases.size()).baseIndex;
assert minCostBaseIndex >= 0;
assert minCostBaseIndex < numBases;

baseIndexToMinCostBaseIndex[myBases.get(myBaseIndex).baseIndex] = minCostBaseIndex;

}
}
return baseIndexToMinCostBaseIndex;
}

private int[] attackT = new int[] { 1000, 1000, 1000, 1000, 1000, };

private void updateAttackT() {
for (Troop troop : troops) {
attackT[troop.owner] = Math.min(attackT[troop.owner], 2 * troop.size + 0);
}
}

private double[] calculateExpectedTroopSize() {
double[] expectedTroopSize = new double[numBases];
for (int baseIndexFrom = 0; baseIndexFrom < numBases; baseIndexFrom++) {
if (isMyBase(bases[baseIndexFrom])) {
continue;
}
Base other = bases[baseIndexFrom];

double[] probability = calculateProbability(other);
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
expectedTroopSize[baseIndexTo] += (attackT[other.owner] / 2) * probability[baseIndexTo];
}
}
return expectedTroopSize;
}

private double[] calculateProbability(Base other) {
double[] probability = new double[numBases];
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
if (bases[baseIndexTo].owner == other.owner) {
continue;
}
double d = distance[other.baseIndex][baseIndexTo];
probability[baseIndexTo] += (1.0 / (d * d));
}
double sum = calculateSum(probability);
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
probability[baseIndexTo] /= sum;
}
return probability;
}

private double calculateSum(double[] values) {
double sum = 0;
for (double value : values) {
sum += value;
}
return sum;
}

private int getMaxShareOwnerWithOutMe() {
int[] sumSize = new int[5];
for (int i = 0; i < bases.length; i++) {
sumSize[bases[i].owner] += bases[i].size;
}
for (Troop troop : troops) {
sumSize[troop.owner] += troop.size;
}

int maxIndex = 1;
for (int i = 1; i < sumSize.length; i++) {
if (sumSize[i] > sumSize[maxIndex]) {
maxIndex = i;
}
}

return maxIndex;
}

private boolean isMyLastState() {
timer.start("isMyLastState");
int[] sumSize = new int[5];
for (int i = 0; i < bases.length; i++) {
sumSize[bases[i].owner] += bases[i].size;
}
for (Troop troop : troops) {
sumSize[troop.owner] += troop.size;
}

int sum = 0;
for (int i = 0; i < sumSize.length; i++) {
sum += sumSize[i];
}

for (int i = 1; i < sumSize.length; i++) {
if ((double) sumSize[i] / sum >= 0.7) {
timer.stop("isMyLastState");
return true;
}
}

if ((double) sumSize[myOwnerValue] / sum <= 0.05) {
timer.stop("isMyLastState");
return true;
}

timer.stop("isMyLastState");
return false;
}

private int[] sendFar() {
timer.start("sendFar");
IntArray solution = new IntArray();
for (Base my : myBases) {

if (my.size < 988) {
continue;
}

double maxDistance = -1e9;
int maxi = -1;
for (int baseIndexTo = 0; baseIndexTo < numBases; baseIndexTo++) {
if (distance[my.baseIndex][baseIndexTo] > maxDistance) {
maxDistance = distance[my.baseIndex][baseIndexTo];
maxi = baseIndexTo;
}
}
int from = my.baseIndex;
int to = maxi;
solution.add(from);
solution.add(to);
int time2 = getTime(distance[from][to]);
for (int time = 0; time < time2; time++) {
updateCapacity(to, time);
}

}

updateTurn();

timer.stop("sendFar");
return solution.toArray();
}

private boolean isWin() {
return othersBases.size() == 0;
}

private double getDistance(int baseIndexFrom, int baseIndexTo) {
if (distance == null) {
distance = new double[numBases][numBases];
for (int baseIndexFrom2 = 0; baseIndexFrom2 < numBases; baseIndexFrom2++) {
for (int baseIndexTo2 = 0; baseIndexTo2 < numBases; baseIndexTo2++) {
int dr = bases[baseIndexFrom2].r - bases[baseIndexTo2].r;
int dc = bases[baseIndexFrom2].c - bases[baseIndexTo2].c;
distance[baseIndexFrom2][baseIndexTo2] = Math.sqrt(dr * dr + dc * dc);
}
}
}
return distance[baseIndexFrom][baseIndexTo];
}

private int[] myLastStateHand() {
timer.start("myLastStateHand");
if (myBases.size() == 0) {
updateTurn();
timer.stop("myLastStateHand");
return new int[] {};
}

int sumMySize = 0;
for (int i = 0; i < bases.length; i++) {
if (bases[i].owner == myOwnerValue) {
sumMySize += bases[i].size;
}

}
for (Troop troop : troops) {
if (troop.owner == myOwnerValue) {
sumMySize += troop.size;
}
}

if (sumMySize > 1500) {

int maxFrom = -1;
int maxTo = -1;
{
double maxDistance = 0;
for (int from = 0; from < numBases; from++) {
for (int to = 0; to < numBases; to++) {
if (to == from) {
continue;
}

double distance = 2 * getDistance(from, to);

double minDistanceFromFrom = 1e9;
double minDistanceFromTo = 1e9;
for (int other = 0; other < numBases; other++) {
if (other != from) {
minDistanceFromFrom = Math.min(minDistanceFromFrom, getDistance(from, other));
}
if (other != to) {
minDistanceFromTo = Math.min(minDistanceFromTo, getDistance(to, other));
}
}
distance += minDistanceFromFrom + minDistanceFromTo;

if (distance > maxDistance) {
maxDistance = distance;
maxFrom = from;
maxTo = to;
}

}
}
}

IntArray solution = new IntArray();
for (Base my : myBases) {
if (isWait(my)) {
continue;
}

double maxDistance = 0;
int maxDistanceBaseIndex = -1;
if (distance[my.baseIndex][maxFrom] > maxDistance) {
maxDistance = distance[my.baseIndex][maxFrom];
maxDistanceBaseIndex = maxFrom;
}
if (distance[my.baseIndex][maxTo] > maxDistance) {
maxDistance = distance[my.baseIndex][maxTo];
maxDistanceBaseIndex = maxTo;
}

assert maxDistanceBaseIndex != -1;

int mySize = my.size;
while (solution.length / 2 < numBases && mySize >= 2) {
solution.add(my.baseIndex);
solution.add(maxDistanceBaseIndex);
int troopSize = mySize / 2;
mySize -= troopSize;
}
}

updateTurn();
timer.stop("myLastStateHand");
return solution.toArray();
} else {
IntArray solution = new IntArray();
for (Base my : myBases) {
if (isWait(my)) {
continue;
}

double maxDistance = 0;
int maxDistanceBaseIndex = -1;
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
if (distance[my.baseIndex][baseIndex] > maxDistance) {
maxDistance = distance[my.baseIndex][baseIndex];
maxDistanceBaseIndex = baseIndex;
}
}

assert maxDistanceBaseIndex != -1;

int mySize = my.size;
while (solution.length / 2 < numBases && mySize >= 2) {
solution.add(my.baseIndex);
solution.add(maxDistanceBaseIndex);
int troopSize = mySize / 2;
mySize -= troopSize;
}
}

updateTurn();
timer.stop("myLastStateHand");
return solution.toArray();
}
}

private boolean isWait(Base my) {
if (my.size >= 988) {
return false;
}

for (Base base : bases) {
if (base.owner == myOwnerValue) {
continue;
}

int dx = base.c - my.c;
int dy = base.r - my.r;
double distance = Math.sqrt(dx * dx + dy * dy);
if (getTime(distance) <= 2) {
return false;
}
}
for (Troop troop : troops) {
if (troop.owner == myOwnerValue) {
continue;
}

int dx = troop.c - my.c;
int dy = troop.r - my.r;
double distance = Math.sqrt(dx * dx + dy * dy);
if (getTime(distance) <= 2) {
return false;
}
}
return true;
}

private int maxBases = 100;
private MinCostFlow2 mcf = new MinCostFlow2(2 * maxBases + 2);

private double distance(int dx, int dy) {
return Math.sqrt(dx * dx + dy * dy);
}

private double distance(Base base0, Base base1) {
return Math.sqrt(squaredDistance(base0, base1));
}

private int squaredDistance(Base base0, Base base1) {
int dr = base0.r - base1.r;
int dc = base0.c - base1.c;
int a = dr * dr + dc * dc;
return a;
}

private void updateTurn() {
turn++;
}

private void updateInformation(int[] bases, int[] troops) {
timer.start("updateInformation");
updateBaseInformation(bases);
updateTroopInformation(troops);

{
HashSet<Integer> playerIndexSet = new HashSet<>();
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
playerIndexSet.add(this.bases[baseIndex].owner);
numAIs = Math.max(numAIs, this.bases[baseIndex].owner + 1);
}
}

myBases.clear();
othersBases.clear();
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
if (isMyBase(bases, baseIndex)) {
myBases.add(this.bases[baseIndex]);
} else {
othersBases.add(this.bases[baseIndex]);
}
}

updateAttackT();
timer.stop("updateInformation");
}

private int[][] baseOwner = new int[2000][100];
private int[][] baseSize = new int[2000][100];

private void updateBaseInformation(int[] bases) {
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
this.bases[baseIndex].owner = bases[2 * baseIndex + 0];
this.bases[baseIndex].size = bases[2 * baseIndex + 1];

baseOwner[turn][baseIndex] = this.bases[baseIndex].owner;
baseSize[turn][baseIndex] = this.bases[baseIndex].size;
}

if (turn - 1 >= 0) {
for (int baseIndex = 0; baseIndex < numBases; baseIndex++) {
if (baseOwner[turn][baseIndex] != baseOwner[turn - 1][baseIndex]) {
continue;
}
int growthRate = baseSize[turn][baseIndex] - baseSize[turn - 1][baseIndex] - baseSize[turn - 1][baseIndex] / 100;
if (!(growthRate >= 1 && growthRate <= 3)) {
continue;
}
this.bases[baseIndex].growthRate = growthRate;
}
}
}

private ArrayList<Troop> troops = new ArrayList<>();

private void updateTroopInformation(int[] troops) {
this.troops.clear();
int numTroops = troops.length / 4;
for (int troopIndex = 0; troopIndex < numTroops; troopIndex++) {
Troop troop = new Troop();
troop.owner = troops[4 * troopIndex + 0];
troop.size = troops[4 * troopIndex + 1];
troop.c = troops[4 * troopIndex + 2];
troop.r = troops[4 * troopIndex + 3];
this.troops.add(troop);
}
}

private boolean isMyBase(Base base) {
return base.owner == 0;
}

private boolean isMyBase(int[] bases, int i) {
return bases[2 * i] == 0;
}

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

int N = Integer.parseInt(reader.readLine());
int[] baseLocations = new int[N];
for (int i = 0; i < N; i++) {
baseLocations[i] = Integer.parseInt(reader.readLine());
}
int speed = Integer.parseInt(reader.readLine());
int retInit = aw.init(baseLocations, speed);
System.out.println(retInit);
System.out.flush();

for (int st = 0; st < 2000; st++) {
String line = reader.readLine();
if (line == null) {
break;
}
int B = Integer.parseInt(line);
int[] bases = new int[B];
for (int i = 0; i < B; i++) {
bases[i] = Integer.parseInt(reader.readLine());
}
int T = Integer.parseInt(reader.readLine());
int[] troops = new int[T];
for (int i = 0; i < T; i++) {
troops[i] = Integer.parseInt(reader.readLine());
}

int[] ret = aw.sendTroops(bases, troops);

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 Base {

public int growthRate;
public int owner;
public int size;
public int r;
public int c;
public int baseIndex;
}

class Troop {

public int owner;
public int size;
public int r;
public int c;

}

class RealAI {
SecureRandom rnd;
int attackT;
double locality;
int B;
int owner;
int[] baseX, baseY;

RealAI(long seed, int own) {
try {
rnd = SecureRandom.getInstance("SHA1PRNG");
} catch (Exception e) {
}
rnd.setSeed(seed);
owner = own;
attackT = 1000 / 2 + rnd.nextInt(1000 / 2);
locality = rnd.nextDouble() * 2 + 1;
}

int init(int[] baseLocations, int speed) {
B = baseLocations.length / 2;
baseX = new int[B];
baseY = new int[B];
for (int i = 0; i < B; ++i) {
baseX[i] = baseLocations[2 * i];
baseY[i] = baseLocations[2 * i + 1];
}
return 0;
}

ArrayList<Integer> others;

int getRandomBase(int sourceInd) {
double[] probs = new double[others.size()];
double sp = 0;
for (int i = 0; i < others.size(); ++i) {
int ind = others.get(i).intValue();
probs[i] = Math.pow(1.0 / (Math.pow(baseX[sourceInd] - baseX[ind], 2) + Math.pow(baseY[sourceInd] - baseY[ind], 2)), locality);
sp += probs[i];
}

double r = rnd.nextDouble() * sp;
double s = 0;
for (int i = 0; i < others.size(); ++i) {
s += probs[i];
if (s >= r)
return others.get(i).intValue();
}
return others.get(others.size() - 1).intValue();
}

int[] sendTroops(int[] bases, int[] troops) {
others = new ArrayList<Integer>();
for (int i = 0; i < B; ++i)
if (bases[2 * i] != owner)
others.add(i);
if (others.size() == 0) {
return new int[0];
}

ArrayList<Integer> att = new ArrayList<Integer>();
for (int i = 0; i < B; ++i) {
if (bases[2 * i] == owner && bases[2 * i + 1] > attackT) {
att.add(i);
att.add(getRandomBase(i));
}
}
int[] ret = new int[att.size()];
for (int i = 0; i < att.size(); ++i)
ret[i] = att.get(i).intValue();
return ret;
}
}

final class Utils {
private Utils() {
}

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

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

}

class IntArray {
public int[] values;
public int length;

public IntArray() {
this(new int[4], 0);
}

public IntArray(int capacity) {
this(new int[capacity], 0);
}

public IntArray(int[] values) {
this(values, values.length);
}

public IntArray(int[] values, int length) {
this.values = values;
this.length = length;
}

public void add(int value) {
if (length == values.length) {
values = Arrays.copyOf(values, values.length << 1);
}
values[length++] = value;
}

public int remove() {
return values[--length];
}

public boolean contains(int value) {
for (int i = 0; i < length; i++) {
if (values[i] == value) {
return true;
}
}
return false;
}

public void clear() {
length = 0;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < length; i++) {
sb.append(values[i] + ",");
}
sb.append("}");
return sb.toString();
}

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

public int remove(int index) {
if (index >= length) {
throw new AssertionError();
}

if (index == length - 1) {
return remove();
}

int res = values[index];
System.arraycopy(values, index + 1, values, index, length - (index + 1));
length--;

return res;
}

public void set(int index, int value) {
if (index >= length) {
throw new AssertionError();
}

if (length >= values.length - 1) {
values = Arrays.copyOf(values, values.length << 1);
}
System.arraycopy(values, index, values, index + 1, length - index);
length++;

values[index] = value;
}

public IntArray copy() {
return new IntArray(Arrays.copyOf(values, length), length);
}

public int[] toArray() {
return Arrays.copyOf(values, length);
}

}

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 MinCostFlow2 {
final long INF = (long) 1e15;
ArrayList<ArrayList<Edge>> G;

public MinCostFlow2(int v) {
G = new ArrayList<ArrayList<Edge>>();
for (int i = 0; i < v; i++) {
G.add(new ArrayList<Edge>());
}
dist = new long[v];
prevv = new int[v];
preve = new int[v];
}

public void clear(int v) {
G = new ArrayList<ArrayList<Edge>>();
for (int i = 0; i < v; i++) {
G.add(new ArrayList<Edge>());
}
dist = new long[v];
prevv = new int[v];
preve = new int[v];
}

public void addEdge(int from, int to, int cap, long cost) {
G.get(from).add(new Edge(to, cap, cost, G.get(to).size()));
G.get(to).add(new Edge(from, 0, -cost, G.get(from).size() - 1));
}

private long[] dist;
private int[] prevv;
private int[] preve;

public int minCostFlow(int s, int t, int f) {
int res = 0;
while (f > 0) {
Arrays.fill(dist, INF);
dist[s] = 0;

for (;;) {
boolean update = false;

for (int v = 0; v < dist.length; v++) {
if (dist[v] >= INF) {
continue;
}
for (int i = 0; i < G.get(v).size(); i++) {
Edge e = G.get(v).get(i);
if (e.cap > 0 && dist[v] + e.cost < dist[e.to]) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}

if (!update) {
break;
}
}
if (dist[t] >= INF) {
return -1;
}

int d = f;
for (int v = t; v != s; v = prevv[v]) {
d = Math.min(d, G.get(prevv[v]).get(preve[v]).cap);
}

f -= d;
res += d * dist[t];

for (int v = t; v != s; v = prevv[v]) {
Edge e = G.get(prevv[v]).get(preve[v]);
e.cap -= d;
G.get(v).get(e.rev).cap += d;
}

}

return res;
}
}

class Edge {
int to;
int cap;
int rev;
long cost;

public Edge(int to, int cap, long cost, int rev) {
this.to = to;
this.cap = cap;
this.rev = rev;
this.cost = cost;
}
}

class Point implements Comparable<Point> {

public int x;
public int y;

public Point() {
this(0, 0);
}

public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}

public Point add(Point point) {
return new Point(x + point.x, y + point.y);
}

public Point subtract(Point point) {
return new Point(x - point.x, y - point.y);
}

public Point multiply(int a) {
return new Point(a * x, a * y);
}

public Point divide(int a) {
return new Point(x / a, y / a);
}

public double cross(Point point) {
return x * point.y - y * point.x;
}

public Point operator(Point a) {
return new Point(x * a.x - y * a.y, x * a.y + y * a.x);
}

@Override
public int compareTo(Point o) {
if (x == o.x) {
if (y == o.y) {
return 0;
} else if (y < o.y) {
return -1;
} else {
return 1;
}
} else if (x < o.x) {
return -1;
} else {
return 1;
}
}

@Override
public String toString() {
return "(" + x + "," + y + ")";
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
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;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}

}

class GeometryUtils {
private GeometryUtils() {
}

private static final int grahamscanCcw(Point p1, Point p2, Point p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

public static final Point[] grahamscan(Point[] p) {
int N = p.length;
Point[] points = new Point[N + 1];
for (int i = 1; i < points.length; i++) {
points[i] = p[i - 1];
}
for (int i = 2; i < points.length; i++) {
if (points[i].y < points[1].y || (points[i].y == points[1].y && points[i].x > points[1].x)) {
Point swap = points[1];
points[1] = points[i];
points[i] = swap;
}
}
Arrays.sort(points, 2, points.length, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
double theta1 = Math.atan2(o1.y - points[1].y, o1.x - points[1].x);
double theta2 = Math.atan2(o2.y - points[1].y, o2.x - points[1].x);
if (theta1 < theta2) {
return -1;
}
if (theta1 > theta2) {
return 1;
}
double distance1 = MathUtils.euclideanDistance(o1.y - points[1].y, o1.x - points[1].x, 0, 0);
double distance2 = MathUtils.euclideanDistance(o2.y - points[1].y, o2.x - points[1].x, 0, 0);
if (distance1 < distance2) {
return -1;
}
if (distance1 > distance2) {
return 1;
}
return 0;
}
});
points[0] = points[N];
int M = 1;
for (int i = 2; i < points.length; i++) {
while (grahamscanCcw(points[M - 1], points[M], points[i]) <= 0) {
if (M > 1) {
M -= 1;
continue;
} else if (i == N) {
break;
} else {
i += 1;
}
}
M += 1;
{
Point swap = points[M];
points[M] = points[i];
points[i] = swap;
}
}

Point[] convexHull = new Point[M];
for (int i = 0; i < convexHull.length; i++) {
convexHull[i] = points[i];
}
return convexHull;
}

public static final boolean strictInsideConvexPolygon(Point p, Point[] ps) {
assert isConvexPolygon(ps);
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.length; i++) {
int j = (i + 1) % ps.length;

int ccw = ccw(ps[i], ps[j], p);
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min > 0) {
return true;
}
if (max < 0) {
return true;
}

return !true;
}

public static final boolean insideConvexPolygon(Point[] p, Point[] ps) {
for (int i = 0; i < p.length; i++) {
if (!insideConvexPolygon(p[i], ps)) {
return false;
}
}
return true;
}

public static final boolean insideConvexPolygon(Point p, Point[] ps) {
assert isConvexPolygon(ps);
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.length; i++) {
int j = (i + 1) % ps.length;

int ccw = ccw(ps[i], ps[j], p);
if (ccw == 0) {
return true;
}
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min >= 0) {
return true;
}
if (max <= 0) {
return true;
}

return !true;
}

public static final boolean insideConvexPolygon(Point p, ArrayList<Point> ps) {
assert isConvexPolygon(ps);
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.size(); i++) {
int j = (i + 1) % ps.size();

int ccw = ccw(ps.get(i), ps.get(j), p);
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min >= 0) {
return true;
}
if (max <= 0) {
return true;
}

return !true;
}

public static final boolean strictInsideConvexPolygon(Point p, ArrayList<Point> ps) {
assert isConvexPolygon(ps);
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.size(); i++) {
int j = (i + 1) % ps.size();

int ccw = ccw(ps.get(i), ps.get(j), p);
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min > 0) {
return true;
}
if (max < 0) {
return true;
}

return !true;
}

public static final boolean isConvexPolygon(Point[] ps) {
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.length; i++) {
int j = (i + 1) % ps.length;
int k = (i + 2) % ps.length;

int ccw = ccw(ps[i], ps[j], ps[k]);
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min > 0) {
return true;
}
if (max < 0) {
return true;
}

return !true;
}

public static final boolean isConvexPolygon(ArrayList<Point> ps) {
int min = (int) 1e9;
int max = (int) -1e9;
for (int i = 0; i < ps.size(); i++) {
int j = (i + 1) % ps.size();
int k = (i + 2) % ps.size();

int ccw = ccw(ps.get(i), ps.get(j), ps.get(k));
if (ccw < min) {
min = ccw;
}
if (ccw > max) {
max = ccw;
}
}
if (min > 0) {
return true;
}
if (max < 0) {
return true;
}

return !true;
}

public static final boolean inside(Point[] tests, Point[] points) {
for (int i = 0; i < tests.length; i++) {
if (!inside(tests[i], points)) {
Utils.debug("tests[i]", tests[i], "points", points);
return false;
}
}
return true;
}

public static final boolean inside(Point testPoint, Point[] points) {
if (onBorder(testPoint, points)) {
return true;
}

return inside0(testPoint, points);
}

public static final boolean strictInside(Point testPoint, Point[] points) {
if (onBorder(testPoint, points)) {
return false;
}

return inside0(testPoint, points);
}

private static boolean onBorder(Point testPoint, Point[] points) {
for (int i = 0; i < points.length; i++) {
if (ccw(points[i], points[(i + 1) % points.length], testPoint) == 0) {
return true;
}
}
return false;
}

private static final boolean inside0(Point testPoint, Point[] points0) {
Point[] points = new Point[points0.length];
{
int mini = 1;
for (int i = 0; i < points0.length; i++) {
if (points0[i].y < points0[mini].y) {
mini = i;
} else if (points0[i].y == points0[mini].y && points0[i].x < points0[mini].x) {
mini = i;
}
}
for (int i = 0; i < points.length; i++) {
points[(1 + i) % points.length] = points0[(mini + i) % points.length];
}
}

int i = 0;
int count = 0;
int j = 0;

Line testLine = new Line(new Point(testPoint.x, testPoint.y), new Point(testPoint.x, testPoint.y));
testLine.p2.x = (int) 1e5;

int n = points.length;
Point[] newps = new Point[n + 2];
for (int k = 0; k < n; k++) {
newps[k] = points[k];
}
newps[n] = newps[0];
newps[n + 1] = newps[1];

for (i = 1; i <= n; i++) {
if (ccw(testLine.p1, testLine.p2, newps[i]) == 0) {
continue;
}
if (i == j + 1) {
if (intersect(new Line(newps[i], newps[j]), testLine)) {
count++;
}
} else {
if (ccw(testLine.p1, testLine.p2, newps[i]) * ccw(testLine.p1, testLine.p2, newps[j]) < 0) {
count++;
}
}
j = i;
}
return (count & 1) == 1;
}

public static final boolean intersect(Line l1, Line l2) {
return (ccw(l1.p1, l1.p2, l2.p1) * ccw(l1.p1, l1.p2, l2.p2) <= 0) && (ccw(l2.p1, l2.p2, l1.p1) * ccw(l2.p1, l2.p2, l1.p2) <= 0);
}

public static final double thetaRobertSedgewick(Point p1, Point p2) {
int dx = p2.x - p1.x;
int ax = Math.abs(dx);
int dy = p2.y - p1.y;
int ay = Math.abs(dy);
double t = (ax + ay == 0) ? 0 : (double) dy / (double) (ax + ay);
if (dx < 0) {
t = 2 - t;
} else if (dy < 0) {
t = 4 + t;
}
return Math.toRadians(t * 90.0);
}

public static final int ccw(Point p0, Point p1, Point p2) {
int dx1 = p1.x - p0.x;
int dy1 = p1.y - p0.y;
int dx2 = p2.x - p0.x;
int dy2 = p2.y - p0.y;
if (dx1 * dy2 > dy1 * dx2) {
return 1;
}
if (dx1 * dy2 < dy1 * dx2) {
return -1;
}
if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) {
return -1;
}
if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) {
return 1;
}
return 0;
}
}

class Line {
public Point p1;
public Point p2;

public Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
}

class MathUtils {
private MathUtils() {
}

public static final double earthDistance(double latitude0, double longitude0, double latitude1, double longitude1, double earthRadius) {
double deltaLon = Math.abs(longitude0 - longitude1);
if (deltaLon > 180) {
deltaLon = 360 - deltaLon;
}
deltaLon = Math.toRadians(deltaLon);
longitude0 = Math.toRadians(longitude0);
longitude1 = Math.toRadians(longitude1);
latitude0 = Math.toRadians(latitude0);
latitude1 = Math.toRadians(latitude1);
double e = Math.cos(latitude0) * Math.sin(deltaLon);
double e2 = Math.cos(latitude1) * Math.sin(latitude0) - Math.sin(latitude1) * Math.cos(latitude0) * Math.cos(deltaLon);
return earthRadius * Math.atan2(Math.sqrt(e * e + e2 * e2), Math.sin(latitude1) * Math.sin(latitude0) + Math.cos(latitude1) * Math.cos(latitude0) * Math.cos(deltaLon));
}

public static final double transitTime(double latitude0, double longitude0, double latitude1, double longitude1, double earthRadius) {
double highSlope = 60.0 / 122.0;
double lowSlope = 53.3 / 120.0;
double meanSlope = 60.0 * (highSlope + lowSlope) / 2.0;
double earthCircumference = 2.0 * Math.PI * earthRadius;
double earthDistance = earthDistance(latitude0, longitude0, latitude1, longitude1, earthRadius);
return (earthDistance / earthCircumference) * 360.0 * meanSlope;
}

public static final int euclideanDistanceSquared(int x0, int y0, int x1, int y1) {
return MathUtils.euclideanDistanceSquared(x1 - x0, y1 - y0);
}

public static final int euclideanDistanceSquared(int dx, int dy) {
return dx * dx + dy * dy;
}

public static final long euclideanDistanceSquared(long dx, long dy) {
return dx * dx + dy * dy;
}

public static final double euclideanDistance(double r1, double c1, double r2, double c2) {
double deltaR = r2 - r1;
double deltaC = c2 - c1;
return Math.sqrt(deltaR * deltaR + deltaC * deltaC);
}

public static final double manhattanDistance(double r1, double c1, double r2, double c2) {
double deltaR = r2 - r1;
double deltaC = c2 - c1;
return Math.abs(deltaR) + Math.abs(deltaC);
}

public static final double euclideanDistance(double[] a, double[] b) {
assert a.length == b.length;

int n = a.length;

double sum = 0;
for (int i = 0; i < n; i++) {
double delta = a[i] - b[i];
sum += delta * delta;
}
return Math.sqrt(sum);
}

public static final double calculateEuclideanNorm(double[] a) {
double euclideanNorm = 0;
for (int i = 0; i < a.length; i++) {
euclideanNorm += a[i] * a[i];
}
euclideanNorm = Math.sqrt(euclideanNorm);
return euclideanNorm;
}

}

class TimerManager {
HashMap<String, Timer> map = new HashMap<>();

public void start(String id) {
if (map.get(id) == null) {
map.put(id, new Timer());
}
Timer timer = map.get(id);
timer.setDescription(id);
timer.start();
}

public void stop(String id) {
if (map.get(id) == null) {
map.put(id, new Timer());
}
Timer timer = map.get(id);
timer.setDescription(id);
timer.stop();
}

public void print() {
ArrayList<Timer> timers = new ArrayList<>();
timers.addAll(map.values());
Collections.sort(timers);
for (int i = 0; i < timers.size(); i++) {
timers.get(i).print();
}
}
}

class Timer implements Comparable<Timer> {
private double time;
private long start;
private long stop;
private int count;
private String description;
private boolean isRunning;

public Timer() {
reset();
}

@Override
public int compareTo(Timer o) {
if (time < o.time) {
return 1;
}
if (time > o.time) {
return -1;
}
return 0;
}

public int getCount() {
return count;
}

public String getDescription() {
return description;
}

public long getStart() {
return start;
}

public long getStop() {
return stop;
}

public double getTime() {
return time;
}

public boolean isRunning() {
return isRunning;
}

public void print() {
if (count > 0) {
Utils.debug(String.format("time, %10s, count, %10d, time/count, %12.9f, %s", TimeManager.toString(time), count, time / count, description));
}
}

public void reset() {
time = 0;
start = 0;
stop = 0;
count = 0;
isRunning = false;
}

public void setDescription(String description) {
assert this.description == null || this.description.equals(description);
if (this.description == null) {
this.description = description;
}
}

public void start() {
assert isRunning == false;
isRunning = true;
start = System.nanoTime();
}

public void stop() {
assert isRunning == true;
stop = System.nanoTime();
count++;
time += (stop - start) * 1e-9;
isRunning = false;
}
}

class TimeManager {
private long start;
private int count;

public TimeManager() {
init();
}

public int getCount() {
return count;
}

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

public long getTime() {
count++;
return System.nanoTime() - start;
}

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

public void init(long start) {
this.start = start;
count = 0;
}

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

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));
}
}

}