Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Created June 25, 2013 06:59
Show Gist options
  • Save hiroshi-cl/5856517 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/5856517 to your computer and use it in GitHub Desktop.
ACM-ICPC 模擬地区予選 2012 J: Ancient Scrolls [Licence: NYSL Version 0.9982
import java.util.*;
import static java.lang.Math.*;
public class Main {
private static final int n = 3; // future work n != 3
public static void main(String... args) {
final Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
final int l = sc.nextInt();
final int d = sc.nextInt();
if (l == 0 && d == 0)
break;
final char[][] strs = new char[n + 1][];
for (int i = 0; i < n; i++)
strs[i] = sc.next().toCharArray();
strs[n] = new char[l];
for (int i = 0; i < l; i++)
strs[n][i] = 'A';
System.out.println(new Main(d, l, strs).solve());
}
}
private final int d, l;
private final char[][] strs;
private Main(int d, int l, char[][] strs) {
this.d = d;
this.l = l;
this.strs = new char[l][n + 1];
for (int i = 0; i < l; i++)
for (int j = 0; j <= n; j++)
this.strs[i][j] = strs[j][i];
}
private String solve() {
final int[] type = new int[l];
for (int i = 0; i < l; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < j; k++)
type[i] |= strs[i][j] == strs[i][k] ? 1 << j | 1 << k : 0;
final int[] cnt = new int[1 << n];
for (int i = 0; i < l; i++)
cnt[type[i]]++;
final int[] dd = new int[n];
Arrays.fill(dd, d);
if (!check(cnt, dd))
return "-1";
final char[] ret = new char[l];
for (int i = 0; i < l; i++) {
cnt[type[i]]--;
ret[i] = assign(cnt, dd, strs[i]);
}
return new String(ret);
}
private char assign(final int[] cnt, final int[] dd, final char[] cs) {
char min = '~';
for (int i = 0; i <= n; i++)
if (cs[i] < min) {
for (int j = 0; j < n; j++)
if (cs[j] != cs[i])
dd[j]--;
if (check(cnt, dd))
min = cs[i];
for (int j = 0; j < n; j++)
if (cs[j] != cs[i])
dd[j]++;
}
if (min == '~')
throw null;
for (int i = 0; i < n; i++)
if (cs[i] != min)
dd[i]--;
return min;
}
private boolean check(final int[] cnt, final int[] dd) {
for (int i = 0; i < n; i++)
if (dd[i] < 0)
return false;
final int[] greedy = new int[n];
for (int i = 0; i < n; i++)
greedy[i] = max(0, cnt[0] - dd[i] + cnt[(1 << n) - 1 ^ 1 << i]);
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += greedy[i];
if (sum <= cnt[0])
return true;
}
{
int nonzero = -1;
for (int i = 0; i < n; i++)
if (greedy[i] > 0)
if (nonzero >= 0)
return false;
else
nonzero = i;
final int extrusion = greedy[nonzero] - cnt[0];
int margin = cnt[(1 << n) - 1 ^ 1 << nonzero];
for (int i = 0; i < n; i++)
if (greedy[i] == 0)
margin = min(margin, dd[i] - cnt[0] - cnt[(1 << n) - 1 ^ 1 << i]);
return margin >= extrusion;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment