Pagini recente » Cod sursa (job #2196853) | Cod sursa (job #956698) | Cod sursa (job #284281) | Cod sursa (job #2435798) | Cod sursa (job #355392)
Cod sursa(job #355392)
#include <stdio.h>
#include <algorithm>
#define DIM 520
using namespace std;
int A[DIM][DIM];
long long S[DIM][DIM], suma[12], T[12], viz[12];
long long n, i, j, t, p, u, m, ok, k;
int L1, L2, C1, C2;
int cautaC1() {
p = 1, u = n-2;
while (p <= u) {
m = (u-p)/2 + p;
if (S[L1][m] == suma[i]) {
C1 = m;
viz[i] = 1;
return 1;
}
else
if (S[L1][m] < suma[i])
p = m+1;
else
u = m-1;
}
return 0;
}
int cautaL2() {
p = L1+1, u = n-1;
while (p <= u) {
m = (u-p)/2 + p;
if (S[m][C1] - S[L1][C1] == suma[j]) {
L2 = m;
viz[j] = 1;
return 1;
}
else
if (S[m][C1] - S[L1][C1] < suma[j])
p = m+1;
else
u = m-1;
}
return 0;
}
int cautaC2() {
p = C1+1, u = n-1;
while (p <= u) {
m = (u-p)/2 + p;
if (S[L1][m] - S[L1][C1] == suma[t]) {
C2 = m;
viz[t] = 1;
return 1;
}
else
if (S[L1][m] - S[L1][C1] < suma[t])
p = m+1;
else
u = m-1;
}
return 0;
}
int verif() {
int i, ok;
ok = 1, k = 0;
T[1] = S[L1][n] - S[L1][C2];
T[2] = S[L2][C2] - S[L2][C1] - S[L1][C2] + S[L1][C1];
T[3] = S[L2][n] - S[L1][n] - S[L2][C2] + S[L1][C2];
T[4] = S[n][C1] - S[L2][C1];
T[5] = S[n][C2] - S[n][C1] - S[L2][C2] + S[L2][C1];
T[6] = S[n][n] - S[n][C2] - S[L2][n] + S[L2][C2];
sort(T+1, T+7);
for (i = 1; i <= 9; i++)
if (!viz[i])
if (suma[i] != T[++k])
ok = 0;
if (ok)
return 1;
else
return 0;
}
int main() {
FILE *f = fopen("zone.in", "r");
FILE *g = fopen("zone.out", "w");
fscanf(f, "%lld", &n);
for (i = 1; i <= 9; i++)
fscanf(f, "%lld", &suma[i]);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
fscanf(f, "%d", &A[i][j]);
sort(suma+1, suma+10);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];
for (L1 = 1; L1 <= n-2 && !ok; L1++) {
for (i = 1; i <= 9 && !ok; i++) {
if (cautaC1()) {
for (j = 1; j <= 9 && !ok; j++) {
if (!viz[j])
if (cautaL2()) {
for (t = 1; t <= 9 && !ok; t++) {
if (!viz[t])
if (cautaC2()) {
if (verif()) {
ok = 1;
fprintf(g, "%d %d %d %d", L1, L2, C1, C2);
}
viz[t] = 0;
}
}
viz[j] = 0;
}
}
viz[i] = 0;
}
}
}
fclose(f);
fclose(g);
return 0;
}