Mai intai trebuie sa te autentifici.
Cod sursa(job #20696)
Utilizator | Data | 21 februarie 2007 22:03:14 | |
---|---|---|---|
Problema | Zone | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.79 kb |
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N_MAX = 550;
int a[N_MAX][N_MAX], N;
int sm[12], st[12], aux[12], viz[12], sol[8], slin[N_MAX][N_MAX], scol[N_MAX][N_MAX];
int S, s, l1, l2, c1, c2, i, j;
void bag(int x, int y, int z, int w)
{
sol[1] = x, sol[2] = y, sol[3] = z, sol[4] = w;
}
int g;
int back(int k)
{
if (k == 4) {
g = 1;
S = st[1] + st[2] + st[3], s = 0;
//prima linie
for (i = 1; i <= N; i ++) {
s += slin[i][N];
if (s == S) {
l1 = i;
break;
}
if (s > S) {
g = 0;
break;
}
}
if (i == N + 1) {
g = 0;
}
//prima coloana
s = 0;
for (i = 1; i <= N && g; i ++) {
s += scol[l1][i];
if (s == st[1]) {
c1 = i;
break;
}
if (s > st[1]) {
g = 0;
break;
}
}
if (i == N + 1) {
g = 0;
}
//a doua coloana
s = 0;
for (i = c1 + 1; i <= N && g; i ++) {
s += scol[l1][i];
if (s == st[2]) {
c2 = i;
break;
}
if (S > st[2]) {
g = 0;
}
}
if (i == N + 1) {
g = 0;
}
//a doua linie
if (g) {
st[7] = st[8] = st[9] = 0;
for (i = 1; i <= N; i ++) {
if (i <= c1) {
st[7] += (scol[N][i] - scol[l1][i]);
continue;
}
if (i <= c2) {
st[8] += (scol[N][i] - scol[l1][i]);
continue;
}
st[9] += (scol[N][i] - scol[l1][i]);
}
st[4] = st[5] = st[6] = 0;
for (i = l1 + 1; i <= N; i ++) {
l2 = i;
st[4] += slin[i][c1];
st[7] -= slin[i][c1];
st[5] += (slin[i][c2] - slin[i][c1]);
st[8] -= (slin[i][c2] - slin[i][c1]);
st[6] += (slin[i][N] - slin[i][c2]);
st[9] -= (slin[i][N] - slin[i][c2]);
memcpy(aux, st, sizeof(st));
sort(aux + 1, aux + 10);
for (j = 1; j <= 9; j ++) {
if (aux[j] != sm[j]) {
break;
}
}
if (j == 10) {
if (l1 < sol[1]) {
bag(l1, c1, l2, c2);
continue;
}
if (l1 == sol[1] && c1 < sol[2]) {
bag(l1, c1, l2, c2);
continue;
}
if (l1 == sol[1] && c1 == sol[2] && l2 < sol[3]) {
bag(l1, c1, l2, c2);
continue;
}
if (l1 == sol[1] && c1 == sol[2] && l2 == sol[3] && c2 < sol[4]) {
bag(l1, c1, l2, c2);
continue;
}
}
}
}
} else {
for (int c = 1; c <= 9; c ++) {
if (!viz[c]) {
st[k] = sm[c];
viz[c] = 1;
back(k + 1);
viz[c] = 0;
}
}
}
return 1;
}
int main()
{
freopen("zone.in", "r", stdin);
freopen("zone.out", "w", stdout);
scanf("%d\n", &N);
for (i = 1; i <= 9; i ++) {
scanf("%d ", &sm[i]);
}
sort(sm + 1, sm + 10);
for (i = 1; i <= N; i ++) {
for (j = 1; j <= N; j ++) {
scanf("%d ", &a[i][j]);
slin[i][j] = slin[i][j - 1] + a[i][j];
scol[i][j] = scol[i - 1][j] + a[i][j];
}
}
sol[1] = sol[2] = sol[3] = sol[4] = 1000;
back(1);
printf("%d %d %d %d\n", sol[1], sol[3], sol[2], sol[4]);
return 0;
}