425 lines
10 KiB
Java
425 lines
10 KiB
Java
package chelper;
|
|
|
|
import java.io.FileWriter;
|
|
import java.io.IOException;
|
|
import java.io.StringWriter;
|
|
import java.util.ArrayList;
|
|
import java.util.Collections;
|
|
import java.util.HashMap;
|
|
import java.util.LinkedList;
|
|
import java.util.List;
|
|
import java.util.Map;
|
|
import java.util.Random;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
|
|
public class Pizza {
|
|
|
|
class Cut implements Comparable<Cut> {
|
|
public final int x, y, xs, ys, size;
|
|
|
|
public Cut(int x, int y, int xs, int ys) {
|
|
this.x = x;
|
|
this.y = y;
|
|
this.xs = xs;
|
|
this.ys = ys;
|
|
size = xs * ys;
|
|
}
|
|
|
|
boolean okay(Solution solution) {
|
|
if (x + xs > n || y + ys > m) {
|
|
return false;
|
|
}
|
|
|
|
int size = xs * ys;
|
|
if (size > maxSize) {
|
|
return false;
|
|
}
|
|
|
|
int tomatoCount = prefixSum[x + xs - 1][y + ys - 1];
|
|
if (x > 0) {
|
|
tomatoCount -= prefixSum[x - 1][y + ys - 1];
|
|
}
|
|
if (y > 0) {
|
|
tomatoCount -= prefixSum[x + xs - 1][y - 1];
|
|
}
|
|
if (x > 0 && y > 0) {
|
|
tomatoCount += prefixSum[x - 1][y - 1];
|
|
}
|
|
|
|
if (tomatoCount < minEach) {
|
|
return false;
|
|
}
|
|
if (size - tomatoCount < minEach) {
|
|
return false;
|
|
}
|
|
|
|
for (int i = 0; i < xs; i++) {
|
|
for (int j = 0; j < ys; j++) {
|
|
if (solution.occupied[x + i][y + j]) {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
@Override
|
|
public String toString() {
|
|
return "Cut{" +
|
|
"x=" + x +
|
|
", y=" + y +
|
|
", xs=" + xs +
|
|
", ys=" + ys +
|
|
'}';
|
|
}
|
|
|
|
@Override
|
|
public int compareTo(Cut o) {
|
|
int t = Integer.compare(x, o.x);
|
|
if (t != 0) {
|
|
return t;
|
|
}
|
|
return Integer.compare(y, o.y);
|
|
}
|
|
}
|
|
|
|
int randInt(int from, int to) {
|
|
return from + random.nextInt(to - from);
|
|
}
|
|
|
|
class Solution {
|
|
final List<Cut> cuts;
|
|
boolean[][] occupied = new boolean[n][m];
|
|
boolean[][] starts = new boolean[n][m];
|
|
LinkedList<Integer> available = new LinkedList<>();
|
|
int size = 0;
|
|
|
|
Solution() {
|
|
cuts = new ArrayList<>();
|
|
updateFree();
|
|
}
|
|
|
|
Solution(Solution other) {
|
|
cuts = new ArrayList<>(other.cuts);
|
|
size = other.size;
|
|
for (int i = 0; i < n; i++) {
|
|
for (int j = 0; j < m; j++) {
|
|
occupied[i][j] = other.occupied[i][j];
|
|
}
|
|
}
|
|
updateFree();
|
|
}
|
|
|
|
@Override
|
|
public String toString() {
|
|
List<Cut> sorted = new ArrayList<>(cuts);
|
|
Collections.sort(sorted);
|
|
|
|
StringWriter sw = new StringWriter();
|
|
OutputWriter out = new OutputWriter(sw);
|
|
|
|
out.println(cuts.size());
|
|
for (Cut cut : sorted) {
|
|
out.printf("%d %d %d %d\n", cut.x, cut.y, cut.x + cut.xs - 1, cut.y + cut.ys - 1);
|
|
}
|
|
sw.flush();
|
|
|
|
return sw.toString();
|
|
}
|
|
|
|
void updateFree() {
|
|
available.clear();
|
|
for (int i = 0; i < n; i++) {
|
|
for (int j = 0; j < m; j++) {
|
|
if (!occupied[i][j]) {
|
|
available.add(i * m + j);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
Cut makeRandomCut() {
|
|
int tries = 0;
|
|
while (tries < maxTries && !available.isEmpty()) {
|
|
int x = available.getFirst() / m;
|
|
int y = available.getFirst() % m;
|
|
available.removeFirst();
|
|
|
|
/*int x = random.nextInt(n);
|
|
int y = random.nextInt(m);*/
|
|
|
|
if (occupied[x][y]) {
|
|
tries++;
|
|
continue;
|
|
}
|
|
|
|
/*int xs = random.nextInt(maxSize - 1) + 1;
|
|
int maxYs = maxSize / xs;
|
|
int ys = maxYs == 1 ? 1 : (random.nextInt(maxYs - 1) + 1);
|
|
|
|
if (Math.random() < 0.5) {
|
|
int t = xs;
|
|
xs = ys;
|
|
ys = t;
|
|
}*/
|
|
|
|
int xs = randInt(1, sizeVariation);
|
|
int ys = randInt(2 * minEach / xs, maxSize / xs + 1);
|
|
|
|
if (Math.random() < 0.5) {
|
|
int t = xs;
|
|
xs = ys;
|
|
ys = t;
|
|
}
|
|
|
|
Cut cut = new Cut(x, y, xs, ys);
|
|
if (!cut.okay(this)) {
|
|
tries++;
|
|
continue;
|
|
}
|
|
|
|
return cut;
|
|
}
|
|
return null;
|
|
}
|
|
|
|
void add(Cut cut) {
|
|
cuts.add(cut);
|
|
|
|
starts[cut.x][cut.y] = true;
|
|
starts[cut.x][cut.y + cut.ys - 1] = true;
|
|
starts[cut.x + cut.xs - 1][cut.y] = true;
|
|
starts[cut.x + cut.xs - 1][cut.y + cut.ys - 1] = true;
|
|
|
|
for (int i = 0; i < cut.xs; i++) {
|
|
for (int j = 0; j < cut.ys; j++) {
|
|
occupied[cut.x + i][cut.y + j] = true;
|
|
}
|
|
}
|
|
|
|
size += cut.size;
|
|
}
|
|
|
|
void remove(int removeIndex) {
|
|
Cut cut = cuts.get(removeIndex);
|
|
|
|
cuts.remove(removeIndex);
|
|
|
|
for (int i = 0; i < cut.xs; i++) {
|
|
for (int j = 0; j < cut.ys; j++) {
|
|
occupied[cut.x + i][cut.y + j] = false;
|
|
// available.add((cut.x + i) * m + cut.y + j);
|
|
}
|
|
}
|
|
|
|
size -= cut.size;
|
|
}
|
|
|
|
void greedy() {
|
|
for (int i = 0; i < n; i++) {
|
|
for (int j = 0; j < m; j++) {
|
|
if (occupied[i][j]) {
|
|
continue;
|
|
}
|
|
for (int ys = maxSize; ys >= 1; ys--) {
|
|
for (int xs = maxSize / ys + 1; xs >= 1; xs--) {
|
|
if (xs * ys < minEach * 2) {
|
|
break;
|
|
}
|
|
Cut cut = new Cut(i, j, xs, ys);
|
|
if (cut.okay(this)) {
|
|
add(cut);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
Solution tryProb() {
|
|
Solution solution = new Solution();
|
|
solution.greedy();
|
|
return solution;
|
|
}
|
|
|
|
int n, m, minEach, maxSize;
|
|
boolean[][] map;
|
|
int[][] prefixSum;
|
|
Random random = new Random();
|
|
|
|
int iterations = 1000000;
|
|
int printEach = 100000;
|
|
// int updateAvailableEach = 1000;
|
|
double maxTemp = 1;
|
|
double scoreModifier = 1e0;
|
|
int sizeVariation = 8;
|
|
int maxTries = 10;
|
|
double dropProbability = 0.5;
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
String name = in.nextString();
|
|
n = in.nextInt();
|
|
m = in.nextInt();
|
|
minEach = in.nextInt();
|
|
maxSize = in.nextInt();
|
|
|
|
// n = 100;
|
|
// m = 100;
|
|
|
|
map = new boolean[n][m];
|
|
prefixSum = new int[n][m];
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
String s = in.nextLine();
|
|
for (int j = 0; j < m; j++) {
|
|
map[i][j] = s.charAt(j) == 'T';
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
for (int j = 0; j < m; j++) {
|
|
if (map[i][j]) {
|
|
prefixSum[i][j]++;
|
|
}
|
|
|
|
if (i > 0) {
|
|
prefixSum[i][j] += prefixSum[i - 1][j];
|
|
}
|
|
if (j > 0) {
|
|
prefixSum[i][j] += prefixSum[i][j - 1];
|
|
}
|
|
if (i > 0 && j > 0) {
|
|
prefixSum[i][j] -= prefixSum[i - 1][j - 1];
|
|
}
|
|
}
|
|
}
|
|
|
|
Solution solution = new Solution();
|
|
int globalMax = 0;
|
|
Solution bestSolution = null;
|
|
int skips = 0;
|
|
|
|
|
|
|
|
/*for (int i = 0; i < iterations; i++) {
|
|
int newSize;
|
|
boolean remove;
|
|
int removeIndex = 0;
|
|
Cut newCut = null;
|
|
|
|
if (!solution.cuts.isEmpty() && Math.random() < dropProbability) {
|
|
remove = true;
|
|
removeIndex = random.nextInt(solution.cuts.size());
|
|
newSize = solution.size - solution.cuts.get(removeIndex).size;
|
|
} else {
|
|
newCut = solution.makeRandomCut();
|
|
if (newCut == null) {
|
|
i--;
|
|
skips++;
|
|
continue;
|
|
} else {
|
|
remove = false;
|
|
newSize = solution.size + newCut.size;
|
|
}
|
|
}
|
|
|
|
if (solution.available.size() == 0) {
|
|
solution.updateFree();
|
|
}
|
|
|
|
double temp = maxTemp * (1 - (double)i / iterations);
|
|
|
|
double prob = Math.exp(((double)newSize - solution.size) * scoreModifier / temp);
|
|
|
|
if (newSize > solution.size || Math.random() < prob) {
|
|
if (remove) {
|
|
solution.remove(removeIndex);
|
|
} else {
|
|
solution.add(newCut);
|
|
}
|
|
}
|
|
|
|
if (solution.size > globalMax) {
|
|
globalMax = solution.size;
|
|
// bestSolution = new Solution(solution);
|
|
}
|
|
if (i % printEach == 0) {
|
|
System.out.println("---");
|
|
System.out.printf("Temp %.2f\n", temp);
|
|
System.out.printf("Count %d\n", solution.cuts.size());
|
|
System.out.printf("Size %d\n", solution.size);
|
|
System.out.printf("TSize %d\n", n * m);
|
|
System.out.printf("%% %.4f\n", (double)solution.size / n / m);
|
|
System.out.printf("Max %d\n", globalMax);
|
|
System.out.printf("Avail %d\n", solution.available.size());
|
|
System.out.printf("Skips %d\n", skips);
|
|
System.out.printf("Iters %d\n", i);
|
|
System.out.println("---");
|
|
}
|
|
}*/
|
|
|
|
|
|
solution = tryProb();
|
|
|
|
if (bestSolution != null) {
|
|
solution = bestSolution;
|
|
}
|
|
System.out.println(solution.size);
|
|
|
|
try {
|
|
FileWriter fileWriter = new FileWriter(name + ".txt");
|
|
fileWriter.write(solution.toString());
|
|
fileWriter.close();
|
|
} catch (IOException e) {
|
|
throw new RuntimeException(e);
|
|
}
|
|
|
|
try {
|
|
FileWriter fileWriter = new FileWriter("map.txt");
|
|
OutputWriter out2 = new OutputWriter(fileWriter);
|
|
for (int i = 0; i < n; i++) {
|
|
for (int j = 0; j < m; j++) {
|
|
if (map[i][j] && solution.occupied[i][j] && solution.starts[i][j]) {
|
|
out2.print('T');
|
|
}
|
|
if (!map[i][j] && solution.occupied[i][j] && solution.starts[i][j]) {
|
|
out2.print('M');
|
|
}
|
|
if (map[i][j] && solution.occupied[i][j] && !solution.starts[i][j]) {
|
|
out2.print('t');
|
|
}
|
|
if (!map[i][j] && solution.occupied[i][j] && !solution.starts[i][j]) {
|
|
out2.print('m');
|
|
}
|
|
if (map[i][j] && !solution.occupied[i][j]) {
|
|
out2.print(',');
|
|
}
|
|
if (!map[i][j] && !solution.occupied[i][j]) {
|
|
out2.print('.');
|
|
}
|
|
}
|
|
out2.println();
|
|
}
|
|
out2.flush();
|
|
fileWriter.close();
|
|
} catch (IOException e) {
|
|
throw new RuntimeException(e);
|
|
}
|
|
|
|
Map<String, Integer> stats = new HashMap<>();
|
|
for (Cut cut : solution.cuts) {
|
|
String s = cut.xs + "x" + cut.ys;
|
|
stats.putIfAbsent(s, 0);
|
|
stats.put(s, stats.get(s) + 1);
|
|
}
|
|
|
|
for (Map.Entry<String, Integer> entry : stats.entrySet()) {
|
|
System.out.println(entry.getKey() + " " + entry.getValue());
|
|
}
|
|
}
|
|
}
|