EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)


Approach 貪欲法 + 焼きなまし法を使いました。

  • 貪欲法
    • sub grid のパターンを繰り返す
  • 焼きなまし法
    • 点の数が0の状態から、無効な状態を許容する焼きなまし法をやってみたけど、有効な状態にするのが難しかった。sub grid のパターンを繰り返す貪欲法で有効な状態の初期解が作れることに気づいて、無効な状態を許容する焼きなまし法を諦めた。
    • 近傍1 : 点をフリップする(使う、使わないを入れ替える)
    • 近傍2 : 点をランダムに移動する(ある点を使わなくするのと同時に別の点を使う)
    • 近傍3 : 点を近くに移動する
      • sub grid で、使っている点の数が変化するものが減って、Kmin,Kmax の制約を違反することが少なくなって、探索空間がなだらかになります。
    • 温度管理、多スタート : ats さんの100回焼きなましても、1回の焼きなましの機能保つ手法を使いました。hakomo さんの多スタートの記事に期待。
    • 温度 : 2 -> 0 で線形に減少。Kmax-Kmin<=2 のときは 2.5 -> 0.2 で線形よりゆっくり減少させる。
    • 近傍選択の重み付け : (フリップ : ランダムに移動 : 近くに移動) = (1 : 1 : 1)。Kmax-Kmin<=2 のときは (1 : 1 : 10)。hakomo さんの近傍選択の重み付けの記事に期待。

感想 Kmax-Kmin>=3 のときは、最適解を出さないといけなくてきつかった。逆に Kmax-Kmin==1 のときは、999k以上の人でも、だいぶ差があると思う。例えば、H = 50, W = 50, h = 25, w = 25, Kmin = 311, Kmax = 312 のときは、私の焼きなまし法では、中央のほうが初期解から全く変化してなくて、もっと良くする余地がありました。
今回参加者が、100人を超えたのがよくわからなかった。
久しぶりに逆走するくらい余裕があった。





source code

pimport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class PointsOnGrid {
private int R;
private int C;
private int subR;
private int subC;
private int minK;
private int maxK;
private int[][] numbers;
private int[][] subGridToNumPoints;

private int numUsedPoints;

private boolean[][] used;
private double score;

private boolean[][] bestUsed;
private double bestScore;

static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();
private SAState sa = new SAState();

private int kR;
private int kC;

private int[] countAC = new int[10];
private int[] sumDeltaScore = new int[10];

private int n;

private IntSet usedPointSet;
private IntSet unusedPointSet;

public String[] findSolution(int H, int W, int h, int w, int Kmin, int Kmax, String[] grid) {
init(H, W, h, w, Kmin, Kmax, grid);
solve();
Utils.debug("countAC", countAC);
Utils.debug("sumDeltaScore", sumDeltaScore);
return makeSolution();
}

private void init(int H, int W, int h, int w, int Kmin, int Kmax, String[] grid) {
R = H;
C = W;
subR = h;
subC = w;
minK = Kmin;
maxK = Kmax;
numbers = new int[R][C];
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
numbers[r][c] = grid[r].charAt(c) - '0';
}
}
numUsedPoints = 0;
used = new boolean[R][C];
score = -1e9;
bestUsed = new boolean[R][C];
bestScore = -1e9;
kR = R - (subR - 1);
kC = C - (subC - 1);
subGridToNumPoints = new int[kR][kC];

usedPointSet = new IntSet(R * C);
unusedPointSet = new IntSet(R * C);
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
unusedPointSet.add(r * C + c);
}
}
}

private void solve() {
greedy();
if (maxK - minK <= 2) {
double numRestart = 100;
double startTemperature = 2.5;
double endTemperature = 0.2;
double startTime = watch.getSecond();
double endTime = 9.5;
sa.expTemperature = 0.25;
for (double restart = 0; restart < numRestart; restart++) {
sa.startTemperature = startTemperature + (endTemperature - startTemperature) * restart / numRestart;
sa.endTemperature = endTemperature;
sa.startTime = startTime + (endTime - startTime) * restart / numRestart;
sa.endTime = startTime + (endTime - startTime) * (restart + 1) / numRestart;
SA2();
loadBest();
}
} else {
double numRestart = 100;
double startTemperature = 2.0;
double endTemperature = 0;
double startTime = watch.getSecond();
double endTime = 9.5;
sa.expTemperature = 1;
for (double restart = 0; restart < numRestart; restart++) {
sa.startTemperature = startTemperature + (endTemperature - startTemperature) * restart / numRestart;
sa.endTemperature = endTemperature;
sa.startTime = startTime + (endTime - startTime) * restart / numRestart;
sa.endTime = startTime + (endTime - startTime) * (restart + 1) / numRestart;
SA();
loadBest();
}
}
Utils.debug("SA", "score", score, "time", watch.getSecondString());
}

private void greedy() {
PriorityQueue<Pair<Integer, Integer>> sumAndPointPairs = new PriorityQueue<>();
for (int r = 0; r < subR; r++) {
for (int c = 0; c < subC; c++) {
sumAndPointPairs.add(new Pair<Integer, Integer>(-sum(r, c), (r << 16) | (c)));
}
}

score = 0;
for (int i = 0; i < maxK; i++) {
Pair<Integer, Integer> pair = sumAndPointPairs.poll();
int v = pair.second.intValue();
int r0 = v >>> 16;
int c0 = v & ((1 << 16) - 1);
for (int r = r0; r < R; r += subR) {
for (int c = c0; c < C; c += subC) {
score += numbers[r][c];
used[r][c] = true;
updateK(r, c, 1);
numUsedPoints++;
addUsed(r, c);
}
}
}
saveBest();
Utils.debug("greedy", "score", score, "time", watch.getSecondString());
}

private int sum(int r0, int c0) {
int sum = 0;
for (int r = r0; r < R; r += subR) {
for (int c = c0; c < C; c += subC) {
sum += numbers[r][c];
}
}
return sum;
}

private void SA() {
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();
if (sa.isTLE()) {
break;
}
}
mutate();
}
}

private void mutate() {
double random = 3 * rng.nextDouble();
if (random < 1) {
flip(0);
} else if (random < 2) {
moveRandom(1);
} else if (random < 3) {
moveNearPoint(2);
}
}

private void SA2() {
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();
if (sa.isTLE()) {
break;
}
}
mutate2();
}
}

private void mutate2() {
double random = 12 * rng.nextDouble();
if (random < 1) {
flip(0);
} else if (random < 2) {
moveRandom(1);
} else if (random < 12) {
moveNearPoint(2);
}
}

private void moveRandom(int countIndex) {
if (numUsedPoints == 0) {
return;
}

int v = usedPointSet.get((int) (usedPointSet.size() * rng.nextDouble()));
int fromR = v / C;
int fromC = v % C;

v = unusedPointSet.get((int) (unusedPointSet.size() * rng.nextDouble()));
int toR = v / C;
int toC = v % C;

double deltaScore = numbers[toR][toC] - numbers[fromR][fromC];
if (sa.accept(deltaScore)) {

if (canAdd(toR, toC, fromR, fromC) && canRemove(fromR, fromC, toR, toC)) {
used[fromR][fromC] = false;
used[toR][toC] = true;

updateK(fromR, fromC, -1, toR, toC);
updateK(toR, toC, 1, fromR, fromC);

addUsed(toR, toC);
removeUsed(fromR, fromC);

score += deltaScore;

saveBest();

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaScore;
} else {
sa.validIterations--;
sa.acceptIterations--;
}

}
}

private void moveNearPoint(int countIndex) {
if (numUsedPoints == 0) {
return;
}

int fromR;
int fromC;
int toR;
int toC;
if (usedPointSet.size() <= unusedPointSet.size()) {
int v = usedPointSet.get((int) (usedPointSet.size() * rng.nextDouble()));
fromR = v / C;
fromC = v % C;

toR = Math.max(0, Math.min(R - 1, fromR - 1 + (int) (3 * rng.nextDouble())));
toC = Math.max(0, Math.min(C - 1, fromC - 1 + (int) (3 * rng.nextDouble())));
while (used[toR][toC]) {
toR = Math.max(0, Math.min(R - 1, toR - 1 + (int) (3 * rng.nextDouble())));
toC = Math.max(0, Math.min(C - 1, toC - 1 + (int) (3 * rng.nextDouble())));
}
} else {
int v = unusedPointSet.get((int) (unusedPointSet.size() * rng.nextDouble()));
toR = v / C;
toC = v % C;

fromR = Math.max(0, Math.min(R - 1, toR - 1 + (int) (3 * rng.nextDouble())));
fromC = Math.max(0, Math.min(C - 1, toC - 1 + (int) (3 * rng.nextDouble())));
while (!used[fromR][fromC]) {
fromR = Math.max(0, Math.min(R - 1, fromR - 1 + (int) (3 * rng.nextDouble())));
fromC = Math.max(0, Math.min(C - 1, fromC - 1 + (int) (3 * rng.nextDouble())));
}
}

double deltaScore = numbers[toR][toC] - numbers[fromR][fromC];
if (sa.accept(deltaScore)) {

if (canAdd(toR, toC, fromR, fromC) && canRemove(fromR, fromC, toR, toC)) {
used[fromR][fromC] = false;
used[toR][toC] = true;

updateK(fromR, fromC, -1, toR, toC);
updateK(toR, toC, 1, fromR, fromC);

addUsed(toR, toC);
removeUsed(fromR, fromC);

score += deltaScore;

saveBest();

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaScore;
} else {
sa.validIterations--;
sa.acceptIterations--;
}

}
}

private void flip(int countIndex) {
n++;
if (n >= R * C) {
n = 0;
}

int r = n / C;
int c = n % C;

double deltaScore = used[r][c] ? -numbers[r][c] : numbers[r][c];

if (sa.accept(deltaScore)) {
if ((used[r][c] && canRemove(r, c)) || (!used[r][c] && canAdd(r, c))) {
used[r][c] = !used[r][c];
updateK(r, c, used[r][c] ? 1 : -1);

numUsedPoints += used[r][c] ? 1 : -1;
if (used[r][c]) {
addUsed(r, c);
} else {
removeUsed(r, c);
}

score += deltaScore;

saveBest();

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaScore;

} else {
sa.validIterations--;
sa.acceptIterations--;
}
}
}

private void updateK(int r0, int c0, int value) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);
for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
subGridToNumPoints[r][c] += value;
}
}
}

private void updateK(int r0, int c0, int value, int r2, int c2) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);

int startR2 = Math.max(0, r2 - (subR - 1));
int startC2 = Math.max(0, c2 - (subC - 1));
int endR2 = Math.min(kR - 1, r2);
int endC2 = Math.min(kC - 1, c2);

for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (r >= startR2 && r <= endR2) {
if (c >= startC2 && c <= endC2) {
c = endC2;
continue;
}
}
subGridToNumPoints[r][c] += value;
}
}
}

private boolean canAdd(int r0, int c0) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);
for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (subGridToNumPoints[r][c] + 1 > maxK) {
return false;
}
}
}
return true;
}

private boolean canAdd(int r0, int c0, int r2, int c2) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);

int startR2 = Math.max(0, r2 - (subR - 1));
int startC2 = Math.max(0, c2 - (subC - 1));
int endR2 = Math.min(kR - 1, r2);
int endC2 = Math.min(kC - 1, c2);

for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (r >= startR2 && r <= endR2) {
if (c >= startC2 && c <= endC2) {
c = endC2;
continue;
}
}
if (subGridToNumPoints[r][c] + 1 > maxK) {
return false;
}
}
}
return true;
}

private boolean canRemove(int r0, int c0) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);
for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (subGridToNumPoints[r][c] - 1 < minK) {
return false;
}
}
}
return true;
}

private boolean canRemove(int r0, int c0, int r2, int c2) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);

int startR2 = Math.max(0, r2 - (subR - 1));
int startC2 = Math.max(0, c2 - (subC - 1));
int endR2 = Math.min(kR - 1, r2);
int endC2 = Math.min(kC - 1, c2);

for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (r >= startR2 && r <= endR2) {
if (c >= startC2 && c <= endC2) {
c = endC2;
continue;
}
}
if (subGridToNumPoints[r][c] - 1 < minK) {
return false;
}
}
}
return true;
}

private void saveBest() {
if (score > bestScore) {
bestScore = score;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
bestUsed[r][c] = used[r][c];
}
}
}

}

private void loadBest() {
score = bestScore;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (used[r][c] != bestUsed[r][c]) {
used[r][c] = bestUsed[r][c];
updateK(r, c, used[r][c] ? 1 : -1);

numUsedPoints += used[r][c] ? 1 : -1;
if (used[r][c]) {
addUsed(r, c);
} else {
removeUsed(r, c);
}
}
}
}
}

private void addUsed(int r, int c) {
int value = r * C + c;
usedPointSet.add(value);
unusedPointSet.removeValue(value);
}

private void removeUsed(int r, int c) {
int value = r * C + c;
usedPointSet.removeValue(value);
unusedPointSet.add(value);
}

private String[] makeSolution() {
String[] res = new String[R];
for (int r = 0; r < R; r++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < C; c++) {
sb.append(bestUsed[r][c] ? "x" : ".");
}
res[r] = sb.toString();
}
return res;
}

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

int H = Integer.parseInt(br.readLine());
int W = Integer.parseInt(br.readLine());
int h = Integer.parseInt(br.readLine());
int w = Integer.parseInt(br.readLine());
int Kmin = Integer.parseInt(br.readLine());
int Kmax = Integer.parseInt(br.readLine());

String[] grid = new String[H];
for (int i = 0; i < H; i++)
grid[i] = br.readLine();

PointsOnGrid pog = new PointsOnGrid();
String[] ret = pog.findSolution(H, W, h, w, Kmin, Kmax, grid);

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

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 1 * 9.5;
public double time = startTime;

public double startTemperature = 2;
public double endTemperature = 0;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;
public double expTemperature = 1;

public double startRange = 15;
public double endRange = 0;
public double range = startRange;

public int numIterations;
public int validIterations;
public int acceptIterations;

private static final double[] log = new double[32768];
static {
for (int i = 0; i < log.length; i++) {
log[i] = Math.log((i + 0.5) / log.length);
}
}

public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;

startTime = useTime ? PointsOnGrid.watch.getSecond() : numIterations;

update();
lastAcceptTemperature = inverseTemperature;
}

public void update() {
updateTime();
updateTemperature();
updateRange();
}

public void updateTemperature() {
inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), expTemperature));
}

public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateTime() {
time = useTime ? PointsOnGrid.watch.getSecond() : numIterations;
}

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double deltaScore) {
return acceptB(deltaScore);
}

public boolean acceptB(double deltaScore) {
validIterations++;

if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}

assert deltaScore < 0;
assert 1.0 / inverseTemperature >= 0;

if (deltaScore * inverseTemperature < -10) {
return false;
}

if (log[PointsOnGrid.rng.nextInt() & 32767] < deltaScore * inverseTemperature) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

public boolean acceptS(double deltaScore) {
validIterations++;

if (deltaScore < 1e-9) {
acceptIterations++;
return true;
}

assert deltaScore > 0;
assert 1.0 / inverseTemperature >= 0;

if (-deltaScore * inverseTemperature < -10) {
return false;
}

if (PointsOnGrid.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

}

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 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 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 double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

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

}

class IntSet {
private static final int EMPTY = -1;
private int size;
private int[] indexToValue;
private int[] valueToIndex;

public IntSet(int capacity) {
this.size = 0;
indexToValue = new int[capacity];
valueToIndex = new int[capacity];
Arrays.fill(valueToIndex, EMPTY);
}

public boolean add(int value) {
if (valueToIndex[value] != EMPTY) {
return false;
}
indexToValue[size] = value;
valueToIndex[indexToValue[size]] = size;
size++;
return true;
}

public boolean remove(int index) {
if (size == 0) {
return false;
}
assert index < size;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[size - 1];
indexToValue[size - 1] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[size - 1]] = EMPTY;

size--;
return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public void swap(int index, int index2) {
assert index < size;
assert index2 < size;

int swap = indexToValue[index];
indexToValue[index] = indexToValue[index2];
indexToValue[index2] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[index2]] = index2;

}

public int get(int index) {
assert index < size;
return indexToValue[index];
}

public int indexOf(int value) {
return valueToIndex[value];
}

public int size() {
return size;
}

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

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

}

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



Approach 貪欲法 + diff を減らすSA1 + diff を減らすSA2 + diff を減らすSA3 + score を減らすSA。

  • 貪欲法
    • diff が大きい領域を選んで、その中からdiff が大きい点を選ぶ。色は選んだ点の領域のRGBそれぞれ中央値を使う。
  • diff を減らすSA
    • diff を減らすSA1 : 画像を縦横それぞれ 9分の1 に縮小する。9x9ピクセルの中央値の色を使う。
    • diff を減らすSA2 : 画像を縦横それぞれ 3分の1 に縮小する。3x3ピクセルの中央値の色を使う。
    • diff を減らすSA3 : 画像は縮小しない。SAではなくてHC。
    • 近傍1 : ランダムに点を選んで、その点の周囲の8方向の中からランダムに1つ選んで移動する。
    • 近傍2 : ランダムに点を選んで、diff が大きい領域を選んで、その中からdiff が大きい点を選んんで移動する。
  • score を減らすSA
    • 領域は変化しない。各領域の色ごとの diff を事前に計算しておく。
    • SAの前に、点を頂点、コストを色の差にして、最小全域木で色の近い点を同じ色にしていって、score が最も良いものを初期解にした。
    • 近傍1 : ランダムに点を選んで、今使っている色でない、使われている色の中で、中央値の色に最も近い色に変える。
    • 近傍2 : 複数の領域で同じ色が使われていれば、中央値の色に変える。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Set;

public class StainedGlass {
private static final int EMPTY = -1;

private int scale = 3;

private int R;
private int C;
private int R1;
private int C1;
private int maxPoints;

private int[][] image9;
private int[][] image3;
private int[][] image1;
private int[][] image;
private int[] rs;
private int[] cs;
private int[] colors;

private double score;
private double sumDiff;

static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();
private SAState sa = new SAState();

private ColorCounter cc;
private PointChecker pc;

private IntSet[] pointIndexToNextPointIndexes;

private int[] pointIndexToSumDiff;
private int[] pointIndexToBestColor;

private int[] copyColors;

private IntSet2[] pointIndexToRxCs;
private int[][] RxCToPointIndex;

private static final int[] dr8 = new int[] { -1, -1, -1, 0, 0, 1, 1, 1, };
private static final int[] dc8 = new int[] { -1, 0, 1, -1, 1, -1, 0, 1, };

private int[] temp2 = new int[1 << 10];

private MedianCalculator256[][] mc;

private IntSet nextPointIndexes = new IntSet(1 << 10);

public int[] create(int H, int[] pixels, int N) {
init(H, pixels, N);
solve();

return makeSolution();
}

private void init(int H, int[] pixels, int N) {
R = H;
C = pixels.length / H;
maxPoints = N;

R1 = R;
C1 = C;

Utils.debug("R", R, "C", C, "maxPoints", maxPoints, "(R * C) / maxPoints", (R * C) / maxPoints);

rs = new int[maxPoints];
cs = new int[maxPoints];
colors = new int[maxPoints];

pc = new PointChecker();

pointIndexToRxCs = new IntSet2[maxPoints];
for (int i = 0; i < pointIndexToRxCs.length; i++) {
pointIndexToRxCs[i] = new IntSet2();
}

cc = new ColorCounter();

pointIndexToNextPointIndexes = new IntSet[maxPoints];
for (int i = 0; i < maxPoints; i++) {
pointIndexToNextPointIndexes[i] = new IntSet(maxPoints);
}

pointIndexToSumDiff = new int[maxPoints];
pointIndexToBestColor = new int[maxPoints];
copyColors = new int[maxPoints];

mc = new MedianCalculator256[maxPoints][3];
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
for (int color = 0; color < 3; color++) {
mc[pointIndex][color] = new MedianCalculator256();
}
}

precomputedSumDiff = new int[maxPoints][3][256];

intLists = new IntList[maxPoints];
for (int i = 0; i < maxPoints; i++) {
intLists[i] = new IntList(maxPoints);
}

used = new int[R][C];
pc.init(R, C);

RxCToPointIndex = new int[R][C];
for (int r = 0; r < R; r++) {
Arrays.fill(RxCToPointIndex[r], EMPTY);
}

scale = 9;
int R2 = (int) Math.ceil((double) R1 / scale);
int C2 = (int) Math.ceil((double) C1 / scale);
image9 = new int[R2][C2];
for (int r = 0; r < (R / scale) * scale; r += scale) {
for (int c = 0; c < (C / scale) * scale; c += scale) {
MedianCalculator256 red = new MedianCalculator256();
MedianCalculator256 green = new MedianCalculator256();
MedianCalculator256 blue = new MedianCalculator256();

for (int dr = 0; dr < scale; dr++) {
if (r + dr >= R) {
continue;
}
for (int dc = 0; dc < scale; dc++) {
if (c + dc >= C) {
continue;
}
int pixel = pixels[(r + dr) * C + (c + dc)];
red.add(getComponent(pixel, 2));
green.add(getComponent(pixel, 1));
blue.add(getComponent(pixel, 0));
}
}

int medianRed = red.calculateMedian();
int medianGreen = green.calculateMedian();
int medianBlue = blue.calculateMedian();

image9[r / scale][c / scale] = (medianRed << 16) | (medianGreen << 8) | (medianBlue);
}
}

scale = 3;
R2 = (int) Math.ceil((double) R1 / scale);
C2 = (int) Math.ceil((double) C1 / scale);
image3 = new int[R2][C2];
for (int r = 0; r < (R / scale) * scale; r += scale) {
for (int c = 0; c < (C / scale) * scale; c += scale) {
MedianCalculator256 red = new MedianCalculator256();
MedianCalculator256 green = new MedianCalculator256();
MedianCalculator256 blue = new MedianCalculator256();

for (int dr = 0; dr < scale; dr++) {
if (r + dr >= R) {
continue;
}
for (int dc = 0; dc < scale; dc++) {
if (c + dc >= C) {
continue;
}
int pixel = pixels[(r + dr) * C + (c + dc)];
red.add(getComponent(pixel, 2));
green.add(getComponent(pixel, 1));
blue.add(getComponent(pixel, 0));
}
}

int medianRed = red.calculateMedian();
int medianGreen = green.calculateMedian();
int medianBlue = blue.calculateMedian();

image3[r / scale][c / scale] = (medianRed << 16) | (medianGreen << 8) | (medianBlue);
}
}

scale = 1;
image1 = new int[R / scale][C / scale];
for (int r = 0; r < (R / scale) * scale; r += scale) {
for (int c = 0; c < (C / scale) * scale; c += scale) {
MedianCalculator256 red = new MedianCalculator256();
MedianCalculator256 green = new MedianCalculator256();
MedianCalculator256 blue = new MedianCalculator256();

for (int dr = 0; dr < scale; dr++) {
if (r + dr >= R) {
continue;
}
for (int dc = 0; dc < scale; dc++) {
if (c + dc >= C) {
continue;
}
int pixel = pixels[(r + dr) * C + (c + dc)];
red.add(getComponent(pixel, 2));
green.add(getComponent(pixel, 1));
blue.add(getComponent(pixel, 0));
}
}

int medianRed = red.calculateMedian();
int medianGreen = green.calculateMedian();
int medianBlue = blue.calculateMedian();

image1[r / scale][c / scale] = (medianRed << 16) | (medianGreen << 8) | (medianBlue);
}
}

}

private void solve() {
scale = 9;
init2(9);
greedy();

sa.startTemperature = 0.0005;
sa.endTime = 19.5 * 0.1;
SAForDiff();

init2(3);
sa.startTemperature = 0.0005;
sa.endTime = 19.5 * 0.4;
SAForDiff();

init2(1);
sa.startTemperature = 0.0;
sa.endTime = 19.5 * 0.7;
SAForDiff();

sa.startTemperature = 0.001;
SAForUsedColors();
}

private void init2(int newScale) {
int d = scale / newScale;

if (d > 1) {
for (int i = 0; i < maxPoints; i++) {
pc.removePoint(rs[i], cs[i]);
for (int j = pointIndexToRxCs[i].size() - 1; j >= 0; j--) {
int v = pointIndexToRxCs[i].get(j);
pointIndexToRxCs[i].remove(j);
int r = v / this.C1;
int c = v % this.C1;
RxCToPointIndex[r][c] = EMPTY;
}
mc[i][0].clear();
mc[i][1].clear();
mc[i][2].clear();
pointIndexToNextPointIndexes[i].clear();
}
}

R = (int) Math.ceil((double) R1 / newScale);
C = (int) Math.ceil((double) C1 / newScale);

if (newScale == 9) {
image = image9;
}
if (newScale == 3) {
image = image3;
}
if (newScale == 1) {
image = image1;
}

scale = newScale;

if (d > 1) {

for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
addAreaPoint(r, c, 0);
}
}

for (int i = 0; i < maxPoints; i++) {
rs[i] = d * rs[i] + d / 2;
cs[i] = d * cs[i] + d / 2;
if (rs[i] < 0 || rs[i] >= R) {
Utils.debug("" + rs[i] + " < 0 || " + rs[i] + " >= " + R);
rs[i] = Math.max(0, Math.min(R - 1, rs[i]));
}
if (cs[i] < 0 || cs[i] >= C) {
Utils.debug("" + cs[i] + " < 0 || " + cs[i] + " >= " + C);
cs[i] = Math.max(0, Math.min(C - 1, cs[i]));
}

if (i > 0) {
updateStrictAreaAdd(i);
assert RxCToPointIndex[rs[i]][cs[i]] == i;
assert pointIndexToRxCs[i].contains(rs[i] * C1 + cs[i]);
}
pc.addPoint(rs[i], cs[i]);
}
}

}

private void greedy() {

for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
rs[pointIndex] = 1000 + pointIndex;
cs[pointIndex] = 1000 + pointIndex;
}

{
int pointIndex = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
addAreaPoint(r, c, pointIndex);
}
}

setColor(pointIndex, calculateMedianColor(pointIndex));

int mostDiff = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
int diff = calculateDiffOfColor(image[r][c], colors[pointIndex]);
if (diff > mostDiff) {
mostDiff = diff;
rs[pointIndex] = r;
cs[pointIndex] = c;
}
}
}

pc.addPoint(rs[pointIndex], cs[pointIndex]);

pointIndexToSumDiff[pointIndex] = calculateSumDiff(pointIndex);

}

for (int pointIndex = 1; pointIndex < maxPoints; pointIndex++) {

int maxPointIndex = -1;
{
int maxDiff = -1;
for (int pointIndex2 = 0; pointIndex2 < pointIndex; pointIndex2++) {
int diff = pointIndexToSumDiff[pointIndex2];
if (diff > maxDiff) {
maxDiff = diff;
maxPointIndex = pointIndex2;
}
}
}

int maxR = -1;
int maxC = -1;
int maxDiff = (int) -1e9;
for (int i = 0; i < 10; i++) {
IntSet2 RxCs = pointIndexToRxCs[maxPointIndex];
int v = RxCs.get((int) (RxCs.size() * rng.nextDouble()));
int newR = v / C1;
int newC = v % C1;

if (pc.isUsedPoint(newR, newC)) {
continue;
}

int diff = calculateDiffOfColor(image[newR][newC], colors[RxCToPointIndex[newR][newC]]);
if (diff > maxDiff) {
maxDiff = diff;
maxR = newR;
maxC = newC;
}
}
if (maxR == -1) {
maxR = (int) (R * rng.nextDouble());
maxC = (int) (C * rng.nextDouble());
while (pc.isUsedPoint(maxR, maxC)) {
maxR = (int) (R * rng.nextDouble());
maxC = (int) (C * rng.nextDouble());
}
}

rs[pointIndex] = maxR;
cs[pointIndex] = maxC;

assert !pc.isUsedPoint(rs[pointIndex], cs[pointIndex]);
pc.addPoint(rs[pointIndex], cs[pointIndex]);

updateStrictAreaAdd(pointIndex);
assert RxCToPointIndex[rs[pointIndex]][cs[pointIndex]] == pointIndex;
assert pointIndexToRxCs[pointIndex].contains(rs[pointIndex] * C1 + cs[pointIndex]);

setColor(pointIndex, calculateMedianColor(pointIndex));
for (int i = 0; i < pointIndexToNextPointIndexes[pointIndex].size(); i++) {
int nextPointIndex = pointIndexToNextPointIndexes[pointIndex].get(i);
setColor(nextPointIndex, calculateMedianColor(nextPointIndex));
}

pointIndexToSumDiff[pointIndex] = calculateSumDiff(pointIndex);
for (int i = 0; i < pointIndexToNextPointIndexes[pointIndex].size(); i++) {
int nextPointIndex = pointIndexToNextPointIndexes[pointIndex].get(i);
pointIndexToSumDiff[nextPointIndex] = calculateSumDiff(nextPointIndex);
}

}

sumDiff = 0;
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
pointIndexToSumDiff[pointIndex] = calculateSumDiff(pointIndex);
sumDiff += pointIndexToSumDiff[pointIndex];
}
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;
score = sumDiff * e * e;

Utils.debug("score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e));
Utils.debug("score", score, "time", watch.getSecondString());
}

private void SAForDiff() {
double second = Math.ceil(watch.getSecond());

{
sumDiff = 0;
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
pointIndexToSumDiff[pointIndex] = calculateSumDiff(pointIndex);
sumDiff += pointIndexToSumDiff[pointIndex];
}
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;
score = sumDiff * e * e;
}

sa.startTime = watch.getSecond();

sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 7) - 1)) == 0) {
sa.update();

if (sa.isTLE()) {
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;

Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}

if (sa.time > second) {
second++;

double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;

Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}

mutateForDiff();
}

sumDiff = 0;
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
pointIndexToSumDiff[pointIndex] = calculateSumDiff(pointIndex);
sumDiff += pointIndexToSumDiff[pointIndex];
}
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;
score = sumDiff * e * e;

Utils.debug("SA", "time", watch.getSecondString());
Utils.debug("score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e));
Utils.debug("countAC", countAC);
Utils.debug("sumDelt", sumDeltaScore);
}

private int[][][] precomputedSumDiff;

private void SAForUsedColors() {
double second = Math.ceil(watch.getSecond());

for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
colors[pointIndex] = calculateMedianColor(pointIndex);
}
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
pointIndexToBestColor[pointIndex] = colors[pointIndex];
}

for (int i = 0; i < maxPoints; i++) {
for (int ci = 0; ci < 3; ci++) {
for (int j = 0; j < 256; j++) {
precomputedSumDiff[i][ci][j] = calculateSumDiff2(i, ci, j);
}
}
}
{
sumDiff = 0;
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
pointIndexToSumDiff[pointIndex] = calculateSumDiff(pointIndex);
sumDiff += pointIndexToSumDiff[pointIndex];
}
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;
score = sumDiff * e * e;
}

UnionFind unionFind = new UnionFind();
unionFind.init(maxPoints);

ArrayList<Edge> edges = new ArrayList<>();
for (int i = 0; i < maxPoints; i++) {
for (int j = i + 1; j < maxPoints; j++) {
edges.add(new Edge(i, j, calculateDiffOfColor(colors[i], colors[j])));
}
}
Collections.sort(edges);

sa.startTemperature = 0;
sa.endTemperature = 0;

int[] bestColors = new int[maxPoints];
double bestScore = 1e99;

for (int i = 0; i < edges.size(); i++) {
Edge edge2 = edges.get(i);
if (unionFind.isSame(edge2.from, edge2.to)) {
continue;
}
unionFind.unite(edge2.from, edge2.to);
setColor(edge2.from, colors[unionFind.getRoot(edge2.from)]);
setColor(edge2.to, colors[unionFind.getRoot(edge2.to)]);

changeColorMedianColorInSameColor(9);

sumDiff = 0;
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
pointIndexToSumDiff[pointIndex] = calculateSumDiff(pointIndex);
sumDiff += pointIndexToSumDiff[pointIndex];
}
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;
score = sumDiff * e * e;

if (score < bestScore) {
bestScore = score;
for (int j = 0; j < maxPoints; j++) {
bestColors[j] = colors[j];
}
}

}

for (int j = 0; j < maxPoints; j++) {
setColor(j, bestColors[j]);
}

{
sumDiff = 0;
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
pointIndexToSumDiff[pointIndex] = calculateSumDiff(pointIndex);
sumDiff += pointIndexToSumDiff[pointIndex];
}
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;
score = sumDiff * e * e;
}

sa.startTemperature = 0.001;
sa.endTemperature = 0;

sa.startTime = watch.getSecond();
sa.endTime = 1 * 19.5;
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();

if (sa.isTLE()) {
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;

Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}

if (sa.time > second) {
second++;

double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;

Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), "score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}

mutateForUsedColors();
}

sumDiff = 0;
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
pointIndexToSumDiff[pointIndex] = calculateSumDiff(pointIndex);
sumDiff += pointIndexToSumDiff[pointIndex];
}
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;
score = sumDiff * e * e;

Utils.debug("SA", "time", watch.getSecondString());
Utils.debug("score", (long) score, "diff", (long) sumDiff, "pow", String.format("%.3f", e * e));
Utils.debug("countAC", countAC);
Utils.debug("sumDelt", sumDeltaScore);
}

private int[] countAC = new int[10];
private double[] sumDeltaScore = new double[10];

private void mutateForDiff() {
double random = 2 * rng.nextDouble();
if (random < 1) {
movePointSmall(0);
} else if (random < 2) {
movePointDiffPointOfDiffArea(5, 5, 1);
}
}

private void mutateForUsedColors() {
double random = 1.0025 * rng.nextDouble();
if (random < 1) {
changeColorToBestUsedColorFromBestColor(8);
} else if (random < 2) {
changeColorMedianColorInSameColor(9);
}
}

private void movePointSmall(int countIndex) {

int index = (int) (maxPoints * rng.nextDouble());

int currentR = rs[index];
int currentC = cs[index];
int currentColor = colors[index];

int direction = (int) (dr8.length * rng.nextDouble());
int newR = currentR + dr8[direction];
newR = Math.min(R - 1, Math.max(0, newR));
int newC = currentC + dc8[direction];
newC = Math.min(C - 1, Math.max(0, newC));
while (pc.isUsedPoint(newR, newC)) {
if (rng.nextDouble() < 0.5) {
newR += rng.nextDouble() < 0.5 ? -1 : 1;
newR = Math.min(R - 1, Math.max(0, newR));
} else {
newC += rng.nextDouble() < 0.5 ? -1 : 1;
newC = Math.min(C - 1, Math.max(0, newC));
}
}

for (int i = 0; i < pointIndexToNextPointIndexes[index].size(); i++) {
nextPointIndexes.add(pointIndexToNextPointIndexes[index].get(i));
}

updateStrictAreaRemove(index);
assert !pc.isUsedPoint(newR, newC);
assert pointIndexToRxCs[index].size() == 0;
rs[index] = newR;
cs[index] = newC;
updateStrictAreaAdd(index);
assert RxCToPointIndex[rs[index]][cs[index]] == index;
assert pointIndexToRxCs[index].contains(rs[index] * C1 + cs[index]);

for (int i = 0; i < pointIndexToNextPointIndexes[index].size(); i++) {
nextPointIndexes.add(pointIndexToNextPointIndexes[index].get(i));
}

int[] deltas = temp2;
setColor(index, calculateMedianColor(index));
deltas[index] = calculateSumDiff(index) - pointIndexToSumDiff[index];
double deltaSumDiff = deltas[index];
for (int i = nextPointIndexes.size() - 1; i >= 0; i--) {
int nextPointIndex = nextPointIndexes.get(i);
copyColors[nextPointIndex] = colors[nextPointIndex];
setColor(nextPointIndex, calculateMedianColor(nextPointIndex));
deltas[nextPointIndex] = calculateSumDiff(nextPointIndex) - pointIndexToSumDiff[nextPointIndex];
deltaSumDiff += deltas[nextPointIndex];
}

if (sa.accept(deltaSumDiff / Math.abs(sumDiff))) {
sumDiff += deltaSumDiff;

pc.removePoint(currentR, currentC);
pc.addPoint(newR, newC);

pointIndexToSumDiff[index] += deltas[index];
for (int i = nextPointIndexes.size() - 1; i >= 0; i--) {
int nextPointIndex = nextPointIndexes.get(i);
nextPointIndexes.remove(i);
pointIndexToSumDiff[nextPointIndex] += deltas[nextPointIndex];
}

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaSumDiff;
} else {

updateStrictAreaRemove(index);
assert pointIndexToRxCs[index].size() == 0;
rs[index] = currentR;
cs[index] = currentC;
updateStrictAreaAdd(index);
assert RxCToPointIndex[rs[index]][cs[index]] == index;
assert pointIndexToRxCs[index].contains(rs[index] * C1 + cs[index]);

setColor(index, currentColor);
for (int i = nextPointIndexes.size() - 1; i >= 0; i--) {
int nextPointIndex = nextPointIndexes.get(i);
nextPointIndexes.remove(i);
setColor(nextPointIndex, copyColors[nextPointIndex]);
}

}
}

private void movePointDiffPointOfDiffArea(int n1, int n2, int countIndex) {
int index = (int) (maxPoints * rng.nextDouble());

int currentR = rs[index];
int currentC = cs[index];
int currentColor = colors[index];

int maxPointIndex = -1;
int maxSumDiff = (int) -1e9;
for (int i = 0; i < n1; i++) {
int pointIndex = (int) (maxPoints * rng.nextDouble());
if (pointIndex == index) {
continue;
}
if (pointIndex == maxPointIndex) {
continue;
}

if (pointIndexToSumDiff[pointIndex] > maxSumDiff) {
maxSumDiff = pointIndexToSumDiff[pointIndex];
maxPointIndex = pointIndex;
}
}
if (maxPointIndex == -1) {
return;
}

int maxR = -1;
int maxC = -1;
int maxDiff = (int) -1e9;
IntSet2 RxCs = pointIndexToRxCs[maxPointIndex];
for (int i = 0; i < n2; i++) {
int v = RxCs.get((int) (RxCs.size() * rng.nextDouble()));
int newR = v / C1;
int newC = v % C1;

if (newR == maxR && newC == maxC) {
continue;
}
if (pc.isUsedPoint(newR, newC)) {
continue;
}

int diff = calculateDiffOfColor(image[newR][newC], colors[maxPointIndex]);
if (diff > maxDiff) {
maxDiff = diff;
maxR = newR;
maxC = newC;
}
}
if (maxR == -1) {
return;
}

for (int i = 0; i < pointIndexToNextPointIndexes[index].size(); i++) {
nextPointIndexes.add(pointIndexToNextPointIndexes[index].get(i));
}

updateStrictAreaRemove(index);
assert !pc.isUsedPoint(maxR, maxC);
assert pointIndexToRxCs[index].size() == 0;
rs[index] = maxR;
cs[index] = maxC;
updateStrictAreaAdd(index);
assert RxCToPointIndex[rs[index]][cs[index]] == index;
assert pointIndexToRxCs[index].contains(rs[index] * C1 + cs[index]);

for (int i = 0; i < pointIndexToNextPointIndexes[index].size(); i++) {
nextPointIndexes.add(pointIndexToNextPointIndexes[index].get(i));
}

setColor(index, calculateMedianColor(index));

int[] deltas = temp2;
deltas[index] = calculateSumDiff(index) - pointIndexToSumDiff[index];
double deltaSumDiff = deltas[index];
for (int i = nextPointIndexes.size() - 1; i >= 0; i--) {
int nextPointIndex = nextPointIndexes.get(i);
copyColors[nextPointIndex] = colors[nextPointIndex];
setColor(nextPointIndex, calculateMedianColor(nextPointIndex));
deltas[nextPointIndex] = calculateSumDiff(nextPointIndex) - pointIndexToSumDiff[nextPointIndex];
deltaSumDiff += deltas[nextPointIndex];
}

if (sa.accept(deltaSumDiff / Math.abs(sumDiff))) {
sumDiff += deltaSumDiff;

pc.removePoint(currentR, currentC);
pc.addPoint(maxR, maxC);

pointIndexToSumDiff[index] += deltas[index];
for (int i = nextPointIndexes.size() - 1; i >= 0; i--) {
int nextPointIndex = nextPointIndexes.get(i);
nextPointIndexes.remove(i);
pointIndexToSumDiff[nextPointIndex] += deltas[nextPointIndex];
}

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaSumDiff;
} else {
updateStrictAreaRemove(index);
assert pointIndexToRxCs[index].size() == 0;
rs[index] = currentR;
cs[index] = currentC;
updateStrictAreaAdd(index);
assert RxCToPointIndex[rs[index]][cs[index]] == index;
assert pointIndexToRxCs[index].contains(rs[index] * C1 + cs[index]);

setColor(index, currentColor);

for (int i = nextPointIndexes.size() - 1; i >= 0; i--) {
int nextPointIndex = nextPointIndexes.get(i);
nextPointIndexes.remove(i);
setColor(nextPointIndex, copyColors[nextPointIndex]);
}
}
}

private void changeColorToBestUsedColorFromBestColor(int countIndex) {
int index = (int) (maxPoints * rng.nextDouble());

int currentColor = colors[index];

int size = 0;
int[] bestUsedColors = temp2;
int bestDiff = (int) 1e9;
for (Integer usedColor : cc.keySet()) {
if (usedColor.intValue() == currentColor) {
continue;
}
int diff = calculateDiffOfColor(usedColor.intValue(), pointIndexToBestColor[index]);
if (diff < bestDiff) {
bestDiff = diff;
size = 0;
bestUsedColors[size++] = usedColor.intValue();
} else if (diff == bestDiff) {
bestUsedColors[size++] = usedColor.intValue();
}
}

int bestUsedColor = bestUsedColors[(int) (size * rng.nextDouble())];
setColor(index, bestUsedColor);

double deltaSumDiff = (precomputedSumDiff[index][0][getComponent(bestUsedColor, 2)] + precomputedSumDiff[index][1][getComponent(bestUsedColor, 1)] + precomputedSumDiff[index][2][getComponent(bestUsedColor, 0)]) - pointIndexToSumDiff[index];

double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;
double deltaScore = (sumDiff + deltaSumDiff) * e * e - score;

if (sa.accept(deltaScore / Math.abs(score))) {
sumDiff += deltaSumDiff;
score += deltaScore;

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaScore;

pointIndexToSumDiff[index] += deltaSumDiff;
} else {
setColor(index, currentColor);
}
}

private HashMap<Integer, IntList> colorToPointIndexes = new HashMap<>();

private IntList[] intLists;

private void changeColorMedianColorInSameColor(int countIndex) {

for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
copyColors[pointIndex] = colors[pointIndex];
}

colorToPointIndexes.clear();
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
if (colorToPointIndexes.get(colors[pointIndex]) == null) {
intLists[colorToPointIndexes.size()].clear();
colorToPointIndexes.put(colors[pointIndex], intLists[colorToPointIndexes.size()]);
}
colorToPointIndexes.get(colors[pointIndex]).add(pointIndex);
}

int size = 0;
for (Integer color : colorToPointIndexes.keySet()) {
size = 0;
IntList pointIndexes = colorToPointIndexes.get(color);
for (int i = 0; i < pointIndexes.size(); i++) {
int pointIndex = pointIndexes.get(i);
size += mc[pointIndex][0].size();
}
int medianRed = calculateMedian(size, pointIndexes, 0);
int medianGreen = calculateMedian(size, pointIndexes, 1);
int medianBlue = calculateMedian(size, pointIndexes, 2);

int medianColor = (medianRed << 16) | (medianGreen << 8) | (medianBlue);

for (int i = 0; i < pointIndexes.size(); i++) {
int pointIndex = pointIndexes.get(i);
setColor(pointIndex, medianColor);
}
}

int[] temp = temp2;

double diff = 0;
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
temp[pointIndex] = (precomputedSumDiff[pointIndex][0][getComponent(colors[pointIndex], 2)] + precomputedSumDiff[pointIndex][1][getComponent(colors[pointIndex], 1)] + precomputedSumDiff[pointIndex][2][getComponent(colors[pointIndex], 0)]);
diff += temp[pointIndex];
}
double distinctColors = calculateUsedColors();
double d = distinctColors / maxPoints;
double e = 1 + d;

double newScore = diff * e * e;
double deltaScore = newScore - score;
if (sa.accept(deltaScore / Math.abs(score))) {
score = newScore;
sumDiff = diff;

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaScore;

for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
pointIndexToSumDiff[pointIndex] = temp[pointIndex];
}
} else {
for (int pointIndex = 0; pointIndex < maxPoints; pointIndex++) {
setColor(pointIndex, copyColors[pointIndex]);
}
}

}

private int calculateMedian(int size, IntList pointIndexes, int colorIndex) {
if (size == 0) {
return 0;
}
int center = size >>> 1;
if ((size & 1) == 0) {
int sum = 0;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < pointIndexes.size(); j++) {
int pointIndex = pointIndexes.get(j);
sum += mc[pointIndex][colorIndex].size(i);
}
if (sum >= center) {
if (sum == center) {
for (int i2 = i + 1; i2 < 256; i2++) {
for (int j = 0; j < pointIndexes.size(); j++) {
int pointIndex = pointIndexes.get(j);
sum += mc[pointIndex][colorIndex].size(i2);
}
if (sum > center) {
return (i + i2) >>> 1;
}
}
}
return i;
}
}
}
int sum = 0;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < pointIndexes.size(); j++) {
int pointIndex = pointIndexes.get(j);
sum += mc[pointIndex][colorIndex].size(i);
}
if (sum >= center + 1) {
return i;
}
}

throw new AssertionError();
}

private int calculateSumDiff(int pointIndex) {
return calculateSumDiff(pointIndex, colors[pointIndex]);
}

private int calculateSumDiff(int pointIndex, int color) {
return mc[pointIndex][0].calculateDiff(getComponent(color, 2)) + mc[pointIndex][1].calculateDiff(getComponent(color, 1)) + mc[pointIndex][2].calculateDiff(getComponent(color, 0));
}

private int calculateSumDiff2(int pointIndex, int colorIndex, int colorValue) {
int diff = 0;
for (int i = 0; i < pointIndexToRxCs[pointIndex].size(); i++) {
int v = pointIndexToRxCs[pointIndex].get(i);
int r = v / C1;
int c = v % C1;
diff += Math.abs(getComponent(image[r][c], 2 - colorIndex) - colorValue);
}
return diff;
}

private double calculateUsedColors() {
return cc.usedColors();
}

private int[] makeSolution() {
int[] res = new int[maxPoints * 3];
for (int i = 0; i < maxPoints; i++) {
res[i * 3 + 0] = scale * rs[i] + scale / 2;
res[i * 3 + 1] = scale * cs[i] + scale / 2;
res[i * 3 + 2] = colors[i];
}
return res;
}

private void setColor(int index, int color) {
cc.removeColor(colors[index]);
colors[index] = color;
cc.addColor(colors[index]);
}

private IntQueue queue = new IntQueue(1 << 20);
private int[][] used;
private int countInitPointIndexToRxCs = 0;

private void updateStrictAreaAdd(int pointIndex) {
countInitPointIndexToRxCs++;

queue.clear();
{
int r2 = rs[pointIndex];
int c2 = cs[pointIndex];
queue.add((pointIndex << 20) | (r2 << 10) | c2);
used[r2][c2] = countInitPointIndexToRxCs;
}
for (; !queue.isEmpty();) {
int v = queue.poll();
int index = (v >>> 20) & ((1 << 10) - 1);
int r = (v >>> 10) & ((1 << 10) - 1);
int c = (v >>> 0) & ((1 << 10) - 1);

int currentIndex = RxCToPointIndex[r][c];
assert currentIndex != EMPTY;
assert currentIndex != index;
int dist2 = dist2(r, c, rs[index], cs[index]);
int dist22 = dist2(r, c, rs[currentIndex], cs[currentIndex]);

if (dist2 == 0) {
if (dist2 < dist22 || (dist2 == dist22 && index < currentIndex)) {
} else {
Utils.debug(r, c, rs[index], cs[index], dist2);
Utils.debug(r, c, rs[currentIndex], cs[currentIndex], dist22);
Utils.debug(index, currentIndex);
}
}

if (dist2 < dist22 || (dist2 == dist22 && index < currentIndex)) {
removeAreaPoint(r, c, currentIndex);
addAreaPoint(r, c, index);
addLink(index, currentIndex);
} else {
addLink(index, currentIndex);
continue;
}

for (int i = 0; i < dr8.length; i++) {
int nr = r + dr8[i];
int nc = c + dc8[i];
if (nr < 0 || nr >= R) {
continue;
}
if (nc < 0 || nc >= C) {
continue;
}
if (used[nr][nc] == countInitPointIndexToRxCs) {
continue;
}
queue.add((index << 20) | (nr << 10) | (nc));
used[nr][nc] = countInitPointIndexToRxCs;
}
}
}

private void updateStrictAreaRemove(int pointIndex) {

for (int i = pointIndexToRxCs[pointIndex].size() - 1; i >= 0; i--) {
int v = pointIndexToRxCs[pointIndex].get(i);
int r = v / C1;
int c = v % C1;

removeAreaPoint(r, c, pointIndex);

assert pointIndexToNextPointIndexes[pointIndex].size() > 0;

int best = (int) 1e9;
int bestNextPointIndex = -1;
for (int j = pointIndexToNextPointIndexes[pointIndex].size() - 1; j >= 0; j--) {
int nextPointIndex = pointIndexToNextPointIndexes[pointIndex].get(j);

int dist2 = dist2(r, c, rs[nextPointIndex], cs[nextPointIndex]);
if (dist2 < best || (dist2 == best && nextPointIndex < bestNextPointIndex)) {
best = dist2;
bestNextPointIndex = nextPointIndex;
}
}

assert bestNextPointIndex != -1;

addAreaPoint(r, c, bestNextPointIndex);

for (int d = 0; d < dr8.length; d++) {
int nr = r + dr8[d];
int nc = c + dc8[d];
if (nr < 0 || nr >= R) {
continue;
}
if (nc < 0 || nc >= C) {
continue;
}

if (RxCToPointIndex[nr][nc] != EMPTY) {
if (RxCToPointIndex[nr][nc] != bestNextPointIndex) {
if (RxCToPointIndex[nr][nc] != pointIndex) {
addLink(RxCToPointIndex[nr][nc], bestNextPointIndex);
}
}
}
}
}

for (int j = pointIndexToNextPointIndexes[pointIndex].size() - 1; j >= 0; j--) {
int nextPointIndex = pointIndexToNextPointIndexes[pointIndex].get(j);
removeLink(pointIndex, nextPointIndex);
}
}

private void addLink(int index, int index2) {
pointIndexToNextPointIndexes[index].add(index2);
pointIndexToNextPointIndexes[index2].add(index);
}

private void removeLink(int index, int index2) {
pointIndexToNextPointIndexes[index].removeValue(index2);
pointIndexToNextPointIndexes[index2].removeValue(index);
}

private void addAreaPoint(int r, int c, int pointIndex) {
assert RxCToPointIndex[r][c] == EMPTY;
RxCToPointIndex[r][c] = pointIndex;
pointIndexToRxCs[pointIndex].add(r * this.C1 + c);
mc[pointIndex][0].add(getComponent(image[r][c], 2));
mc[pointIndex][1].add(getComponent(image[r][c], 1));
mc[pointIndex][2].add(getComponent(image[r][c], 0));
}

private void removeAreaPoint(int r, int c, int pointIndex) {
assert RxCToPointIndex[r][c] == pointIndex;
RxCToPointIndex[r][c] = EMPTY;
pointIndexToRxCs[pointIndex].removeValue(r * this.C1 + c);
mc[pointIndex][0].remove(getComponent(image[r][c], 2));
mc[pointIndex][1].remove(getComponent(image[r][c], 1));
mc[pointIndex][2].remove(getComponent(image[r][c], 0));
}

private int calculateMedianColor(int index) {
return (mc[index][0].calculateMedian() << 16) | (mc[index][1].calculateMedian() << 8) | (mc[index][2].calculateMedian());
}

private int getComponent(int color, int index) {
return (color >> (8 * index)) & 0xFF;
}

private int calculateDiffOfColor(int c1, int c2) {
return Math.abs(getComponent(c1, 0) - getComponent(c2, 0)) + Math.abs(getComponent(c1, 1) - getComponent(c2, 1)) + Math.abs(getComponent(c1, 2) - getComponent(c2, 2));
}

private int dist2(int r, int c, int r0, int c0) {
int dr = r - r0;
int dc = c - c0;
return dr * dr + dc * dc;
}

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

int H = Integer.parseInt(br.readLine());

int S = Integer.parseInt(br.readLine());
int[] pixels = new int[S];
for (int i = 0; i < S; ++i)
pixels[i] = Integer.parseInt(br.readLine());

int N = Integer.parseInt(br.readLine());

StainedGlass sg = new StainedGlass();
int[] ret = sg.create(H, pixels, N);

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

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 1 * 19.5;
public double time = startTime;

public double startTemperature = 1e-3;
public double endTemperature = 0;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 15;
public double endRange = 0;
public double range = startRange;

public int numIterations;
public int validIterations;
public int acceptIterations;

public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;

startTime = useTime ? StainedGlass.watch.getSecond() : numIterations;

update();
lastAcceptTemperature = inverseTemperature;
}

public void update() {
updateTime();
updateTemperature();
updateRange();
}

public void updateTemperature() {
inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0));
}

public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateTime() {
time = useTime ? StainedGlass.watch.getSecond() : numIterations;
}

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double deltaScore) {
return acceptS(deltaScore);
}

public boolean acceptB(double deltaScore) {
validIterations++;

if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}

assert deltaScore < 0;
assert 1.0 / inverseTemperature >= 0;

if (deltaScore * inverseTemperature < -10) {
return false;
}

if (StainedGlass.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

public boolean acceptS(double deltaScore) {
validIterations++;

if (deltaScore < 1e-9) {
acceptIterations++;
return true;
}

assert deltaScore > 0;
assert 1.0 / inverseTemperature >= 0;

if (-deltaScore * inverseTemperature < -10) {
return false;
}

if (StainedGlass.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

}

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 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 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 double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

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

}

class IntQueue {
private static final int EMPTY = -1;
private int[] values;
private int current;
private int size;

public IntQueue(int capacity) {
values = new int[capacity];
clear();
}

public void clear() {
current = 0;
size = 0;
}

public int size() {
return size - current;
}

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

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

public int indexOf(int value) {
for (int i = current; i < size; i++) {
if (values[i] == value) {
return i;
}
}
return EMPTY;
}

public int poll() {
return values[current++];
}

public boolean add(int value) {
values[size++] = value;
return true;
}

public boolean remove(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
for (int i = index; i < size; i++) {
values[i] = values[i + 1];
}
size--;
return true;
}
}

class ColorCounter {
private HashMap<Integer, Integer> colorToCount = new HashMap<>();

public Set<Integer> keySet() {
return colorToCount.keySet();
}

public void addColor(int color) {
Integer count = colorToCount.get(color);
colorToCount.put(color, 1 + (count == null ? 0 : count.intValue()));
}

public void removeColor(int color) {
Integer count = colorToCount.get(color);
if (count == null) {
return;
}
if (count.intValue() == 1) {
colorToCount.remove(color);
return;
}
colorToCount.put(color, -1 + count.intValue());
}

public int usedColors() {
return colorToCount.size();
}
}

class PointChecker {
private boolean[][] used;

public void init(int R, int C) {
used = new boolean[R][C];
}

public void addPoint(int r, int c) {
used[r][c] = true;
}

public void removePoint(int r, int c) {
used[r][c] = false;
}

public boolean isUsedPoint(int r, int c) {
return used[r][c];
}

}

class IntSet2 {
private static final int EMPTY = -1;
private ArrayList<Integer> indexToValue;
private HashMap<Integer, Integer> valueToIndex;

public IntSet2() {
indexToValue = new ArrayList<>();
valueToIndex = new HashMap<>();
}

public boolean add(int value) {
if (valueToIndex.get(value) != null) {
return false;
}
int size = indexToValue.size();
indexToValue.add(value);
valueToIndex.put(indexToValue.get(size), size);
return true;
}

public boolean remove(int index) {
if (size() == 0) {
return false;
}
assert index < size();
Integer swap = indexToValue.get(index);
indexToValue.set(index, indexToValue.get(size() - 1));
indexToValue.set(size() - 1, swap);

valueToIndex.put(indexToValue.get(index), index);
valueToIndex.remove(swap);
indexToValue.remove(size() - 1);

return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public int get(int index) {
assert index < size();
return indexToValue.get(index).intValue();
}

public int indexOf(int value) {
return valueToIndex.get(value) == null ? EMPTY : valueToIndex.get(value).intValue();
}

public int size() {
return indexToValue.size();
}

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

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

}

class MedianCalculator256 {
private int[] sizes;
private int size;

public MedianCalculator256() {
sizes = new int[256];
size = 0;
}

public int size(int i) {
return sizes[i];
}

public void clear() {
Arrays.fill(sizes, 0);
size = 0;
}

public void add(int value) {
sizes[value]++;
size++;
}

public void remove(int value) {
if (sizes[value] <= 0) {
return;
}
sizes[value]--;
size--;
}

public int calculateMedian() {
if (size == 0) {
return 0;
}
int center = size >>> 1;
if ((size & 1) == 0) {
int sum = 0;
for (int i = 0; i < 256; i++) {
sum += sizes[i];
if (sum >= center) {
if (sum == center) {
for (int i2 = i + 1; i2 < 256; i2++) {
sum += sizes[i2];
if (sum > center) {
return (i + i2) >>> 1;
}
}
}
return i;
}
}
}
int sum = 0;
for (int i = 0; i < 256; i++) {
sum += sizes[i];
if (sum >= center + 1) {
return i;
}
}

throw new AssertionError();
}

public int calculateDiff(int color) {
if (size == 0) {
return 0;
}

int sum = 0;
for (int i = 0; i < color; i++) {
sum += sizes[i] * (color - i);
}
for (int i = color + 1; i < 256; i++) {
sum += sizes[i] * (i - color);
}

return sum;
}

public int size() {
return size;
}

}

class IntList {
private static final int EMPTY = -1;
private int[] values;
private int size;

public IntList(int capacity) {
values = new int[capacity];
clear();
}

public void clear() {
size = 0;
}

public int size() {
return size;
}

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

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

public boolean add(int value) {
values[size++] = value;
return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public int remove(int index) {
int value = values[index];
for (int i = index; i + 1 < size; i++) {
values[i] = values[i + 1];
}
size--;
return value;
}

public int removeFast(int index) {
int value = values[index];
values[index] = values[size - 1];
size--;
return value;
}

public int get(int index) {
return values[index];
}

public int set(int index, int value) {
int oldValue = values[index];
values[index] = value;
return oldValue;
}

public void add(int index, int value) {
assert index <= size;
for (int i = size - 1; i >= index; i--) {
values[i + 1] = values[i];
}
size++;
values[index] = value;
}

public int indexOf(int value) {
for (int i = 0; i < size; i++) {
if (values[i] == value) {
return i;
}
}
return EMPTY;
}

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

}

class IntSet {
private static final int EMPTY = -1;
private int size;
private int[] indexToValue;
private int[] valueToIndex;

public IntSet(int capacity) {
this.size = 0;
indexToValue = new int[capacity];
valueToIndex = new int[capacity];
Arrays.fill(valueToIndex, EMPTY);
}

public boolean add(int value) {
if (valueToIndex[value] != EMPTY) {
return false;
}
indexToValue[size] = value;
valueToIndex[indexToValue[size]] = size;
size++;
return true;
}

public boolean remove(int index) {
if (size == 0) {
return false;
}
assert index < size;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[size - 1];
indexToValue[size - 1] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[size - 1]] = EMPTY;

size--;
return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public void swap(int index, int index2) {
assert index < size;
assert index2 < size;

int swap = indexToValue[index];
indexToValue[index] = indexToValue[index2];
indexToValue[index2] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[index2]] = index2;

}

public int get(int index) {
assert index < size;
return indexToValue[index];
}

public int indexOf(int value) {
return valueToIndex[value];
}

public int size() {
return size;
}

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

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

}

class Edge implements Comparable<Edge> {
int from;
int to;
int cost;

public Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}

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

class UnionFind {
private int[] par;
private int[] rank;

public void init(int n) {
par = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
par[i] = i;
rank[i] = 0;
}
}

public int getRoot(int x) {
if (par[x] == x) {
return x;
} else {
par[x] = getRoot(par[x]);
return par[x];
}
}

public void unite(int x, int y) {
x = getRoot(x);
y = getRoot(y);
if (x == y) {
return;
}
if (rank[x] < rank[y]) {
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y]) {
rank[x]++;
}
}
}

public boolean isSame(int x, int y) {
return getRoot(x) == getRoot(y);
}
}





Approach 注文の量を各アイテムごとに計算する。量は、max(全てのアイテムの平均 + 係数 * 全てのアイテムの標準偏差, sqrt(min(期限の上限, 期限)) * 平均 + 係数 * 標準偏差) - 在庫。もし売値が買値より小さければ、量を 0.5 * (売値-買値) 減らす。ここで、係数は day が 1 から 100 に変化するとき、 3 から 0  に線形に変化する。期限の上限は day が 1 から 100 に変化するとき、 3 から 1  に線形に変化する。

後3%なんだったんだろう?


source code

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class ProductInventory {
private int day = 0;
private int[] buyPrice;
private int[] sellPrice;
private int[] expires;
private int numItems;
private int[][] stock;

private MeanHelper[] helpers;
private MeanHelper helpersAll;

public int init(int[] buy, int[] sell, int[] expiration) {
numItems = buy.length;
buyPrice = buy;
sellPrice = sell;
expires = expiration;

Utils.debug("numItems", numItems);
Utils.debug("buy", buy);
Utils.debug("sell", sell);
Utils.debug("expiration", expiration);

stock = new int[16][numItems];

helpers = new MeanHelper[numItems];
for (int i = 0; i < numItems; i++) {
helpers[i] = new MeanHelper();
}
helpersAll = new MeanHelper();

return 0;
}

public int[] order(int[] yesterday) {

int[] copyYesterday = Arrays.copyOf(yesterday, numItems);

for (int i = 0; i < numItems; i++) {
if (copyYesterday[i] == 0) {
continue;
}
for (int d = 0; d < 16; d++) {
while (copyYesterday[i] > 0 && stock[d][i] > 0) {
stock[d][i]--;
copyYesterday[i]--;
}
}
if (day > 0 && copyYesterday[i] > 0) {
Utils.debug(copyYesterday[i]);
}
}

for (int i = 0; i < numItems; i++) {
for (int d = 0; d < 15; d++) {
stock[d][i] = stock[d + 1][i];
}
stock[15][i] = 0;
}
day++;

if (day == 1) {
copyYesterday = Arrays.copyOf(yesterday, numItems);
for (int i = 0; i < numItems; i++) {
int[] day10 = new int[10];

for (int d = 0; copyYesterday[i]-- > 0; d = (d + 1) % 10) {
day10[d]++;
}

for (int d = 0; d < 10; d++) {
helpers[i].add(day10[d]);
helpersAll.add(day10[d]);
}
}
} else {
for (int i = 0; i < numItems; i++) {
helpers[i].add(yesterday[i]);
helpersAll.add(yesterday[i]);
}
}

double[] means = new double[numItems];
for (int i = 0; i < numItems; i++) {
means[i] = helpers[i].mean(0);
}

double[] sds = new double[numItems];
for (int i = 0; i < numItems; i++) {
sds[i] = helpers[i].standardDeviation(0);
}

double meanAllItem = helpersAll.mean(0);
double sdAllItem = helpersAll.standardDeviation(0);

int[] sumStocks = new int[numItems];
for (int d = 0; d < 16; d++) {
for (int i = 0; i < numItems; i++) {
sumStocks[i] += stock[d][i];
}
}

double coefSD = 3.0 + (0.0 - 3.0) * (day / 100.0);
double coefSDAll = 3.0 + (0.0 - 3.0) * (day / 100.0);
double coefExpi = 3.0 + (1.0 - 3.0) * (day / 100.0);

int[] orders = new int[numItems];
for (int i = 0; i < numItems; i++) {
double d = Math.max(meanAllItem + coefSDAll * sdAllItem, Math.sqrt(Math.min(coefExpi, expires[i])) * means[i] + coefSD * sds[i]) - sumStocks[i];
if (sellPrice[i] - buyPrice[i] < 0) {
d += 0.5 * (sellPrice[i] - buyPrice[i]);
}
d = Math.round(d);
d = Math.min(100, Math.max(0, d));
if (d > 0) {
orders[i] += (int) d;
}
}
for (int i = 0; i < numItems; i++) {
stock[expires[i]][i] += orders[i];
}
return orders;
}

public static void main(String[] args) throws IOException {
int n;
int[] buy;
int[] sell;
int[] expiration;
int[] yesterday;
int[] res;

try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
n = Integer.parseInt(in.readLine());
buy = new int[n];
for (int i = 0; i < n; i++) {
buy[i] = Integer.parseInt(in.readLine());
}

n = Integer.parseInt(in.readLine());
sell = new int[n];
for (int i = 0; i < n; i++) {
sell[i] = Integer.parseInt(in.readLine());
}

n = Integer.parseInt(in.readLine());
expiration = new int[n];
for (int i = 0; i < n; i++) {
expiration[i] = Integer.parseInt(in.readLine());
}

ProductInventory sol = new ProductInventory();
System.out.printf("%d\n", sol.init(buy, sell, expiration));
System.out.flush();

for (int k = 0; k < 100; k++) {
n = Integer.parseInt(in.readLine());
yesterday = new int[n];
for (int i = 0; i < n; i++) {
yesterday[i] = Integer.parseInt(in.readLine());
}

res = sol.order(yesterday);

System.out.printf("%d\n", res.length);
for (int i = 0; i < res.length; i++) {
System.out.printf("%d\n", res[i]);
}
System.out.flush();
}
}
}
}

class MeanHelper {
private double max;
private double min;
private double sum;
private double sumSquared;
private double sumCubed;
private double sumFourth;
private int count;

public MeanHelper() {
clear();
}

public void add(double value) {
max = Math.max(max, value);
min = Math.min(min, value);
sum += value;
double valueSquared = value * value;
sumSquared += valueSquared;
sumCubed += valueSquared * value;
sumFourth += valueSquared * valueSquared;
count++;
}

public void add(double value, double number) {
max = Math.max(max, value);
min = Math.min(min, value);
sum += value * number;
double valueSquared = value * value;
sumSquared += valueSquared * number;
sumCubed += valueSquared * value * number;
sumFourth += valueSquared * valueSquared * number;
count += number;
}

public double kurtosis(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double sigma = standardDeviation(0);
if (sigma == 0) {
return 0;
}
double mu = mean(0);
return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
}

public double skewness(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double sigma = standardDeviation(0);
if (sigma == 0) {
return 0;
}
double mu = mean(0);
return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
}

public double mean() {
if (isEmpty()) {
throw new AssertionError();
}
return sum / count;
}

public double mean(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return sum / count;
}

public double sumOfSquaredError() {
if (isEmpty()) {
throw new AssertionError();
}
return sumSquared - sum * sum / count;
}

public double sumOfSquaredError(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return sumSquared - sum * sum / count;
}

public double variance() {
if (isEmpty()) {
throw new AssertionError();
}
double E_XX = sumSquared / count;
double E_X = sum / count;
return E_XX - E_X * E_X;
}

public double variance(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double E_XX = sumSquared / count;
double E_X = sum / count;
return E_XX - E_X * E_X;
}

public double unbiasedVariance() {
if (count - 1 == 0) {
throw new AssertionError();
}
return (count * variance()) / (count - 1);
}

private double unbiasedVariance(double defaultValue) {
if (count - 1 == 0) {
return defaultValue;
}
return (count * variance()) / (count - 1);
}

public double standardDeviation() {
return Math.sqrt(variance());
}

public double standardDeviation(double defaultValue) {
return Math.sqrt(variance(defaultValue));
}

public double unbiasedStandardDeviation() {
return Math.sqrt(unbiasedVariance());
}

public double unbiasedStandardDeviation(double defaultValue) {
return Math.sqrt(unbiasedVariance(defaultValue));
}

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

public void clear() {
max = Double.NEGATIVE_INFINITY;
min = Double.POSITIVE_INFINITY;
sum = 0;
sumSquared = 0;
sumCubed = 0;
sumFourth = 0;
count = 0;
}

public double max() {
if (isEmpty()) {
throw new AssertionError();
}
return max;
}

public double max(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return max;
}

public double min() {
if (isEmpty()) {
throw new AssertionError();
}
return min;
}

public double min(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return min;
}

public int count() {
return count;
}

public double sum() {
return sum;
}

public double sumSquared() {
return sumSquared;
}
}

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

}

このページのトップヘ