ALADDIN - Aladdin
Tác giả: khuc_tuan
Ngôn ngữ: Java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] res;
public static void main(String[] args) throws Exception {
BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(kb.readLine());
int[][] sum = new int[n - 1][n - 1];
for (int i = 0; i + 1 < n; ++i) {
StringTokenizer st = new StringTokenizer(kb.readLine());
for (int j = 0; j + 1 < n; ++j)
sum[i][j] = Integer.parseInt(st.nextToken());
}
int[][] a = new int[n][n];
res = null;
go(0, sum, a);
if (res == null)
System.out.println("No solution");
else
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
System.out.print(res[i][j] + " ");
System.out.println();
}
}
static void go(int pos, int[][] sum, int[][] a) {
if (res != null)
return;
int n = a.length;
if (pos >= n) {
res = new int[n][];
for (int i = 0; i < n; ++i)
res[i] = a[i].clone();
return;
}
if (pos == 0) {
a[0][0] = 0;
go(pos + 1, sum, a);
a[0][0] = 1;
go(pos + 1, sum, a);
return;
}
for (a[0][pos] = 0; a[0][pos] <= 1; ++a[0][pos]) {
for (a[pos][0] = 0; a[pos][0] <= 1; ++a[pos][0]) {
boolean ok = true;
for (int i = 1; i <= pos; ++i) {
a[i][pos] = sum[i - 1][pos - 1] - a[i - 1][pos] - a[i][pos - 1] - a[i - 1][pos - 1];
if (a[i][pos] < 0 || a[i][pos] > 1) {
ok = false;
break;
}
a[pos][i] = sum[pos - 1][i - 1] - a[pos][i - 1] - a[pos - 1][i] - a[pos - 1][i - 1];
if (a[pos][i] < 0 || a[pos][i] > 1) {
ok = false;
break;
}
}
if (ok) {
go(pos + 1, sum, a);
}
}
}
}
}