Pagini recente » Cod sursa (job #2950487) | Cod sursa (job #1650144) | Cod sursa (job #1134664) | Cod sursa (job #582753) | Cod sursa (job #18878)
Cod sursa(job #18878)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 515
int N;
long long S[10]; int uS[10];
int l1, c1, l2, c2;
int sl1, sc1, sl2, sc2;
int x[MAXN][MAXN];
long long s[MAXN][MAXN];
int st[10];
int bin_search( long long S, int f )
{
int step = 256, i;
for (i = f; step; step >>= 1)
if (i + step <= N && s[l1][i + step] - s[l1][f] < S)
i += step;
i++;
if (i > N || s[l1][i] - s[l1][f] != S)
return -1;
return i;
}
int find( long long val )
{
int i;
for (i = 0; i < 9; i++)
if (!uS[i] && S[i] == val)
return i;
return -1;
}
int ok( long long S2[10] )
{
int i, st[10];
for (i = 3; i < 9; i++)
{
st[i] = find( S2[i] );
if (st[i] == -1)
{
for (i--; i >= 4; i--)
uS[ st[i] ] = 0;
return 0;
}
uS[ st[i] ] = 1;
}
for (i = 3; i < 9; i++)
uS[ st[i] ] = 0;
return 1;
}
void newsol( int l1, int l2, int c1, int c2 )
{
sl1 = l1;
sl2 = l2;
sc1 = c1;
sc2 = c2;
}
void getotherlines()
{
c1 = bin_search( S[ st[0] ], 0 ); // taietura 1..c1; c1 + 1 .. c2; c2 + 1 .. N
if (c1 == -1)
return;
c2 = bin_search( S[ st[1] ], c1 );
if (c2 == -1)
return;
if (s[l1][N] - s[l1][c2] != S[ st[2] ])
return;
//mai ramane de terminat l2
long long S2[10];
S2[0] = S[ st[0] ];
S2[1] = S[ st[1] ];
S2[2] = S[ st[2] ];
for (l2 = l1 + 1; l2 <= N; l2++)
{
S2[3] = s[l2][c1] - s[l1][c1];
S2[4] = s[l2][c2] - s[l1][c2] - S2[3];
S2[5] = s[l2][N] - s[l1][N] - S2[3] - S2[4];
S2[6] = s[N][c1] - s[l2][c1];
S2[7] = s[N][c2] - s[l2][c2] - S2[6];
S2[8] = s[N][N] - s[l2][N] - S2[6] - S2[7];
if (!ok( S2 ))
continue;
//avem solutie <:-P
if (sl1 == 0)
newsol( l1, l2, c1, c2 );
else
{
if (c1 < sc1)
newsol( l1, l2, c1, c2 );
else
if (c1 > sc1)
continue;
if (l2 < sc2)
newsol( l1, l2, c1, c2 );
else
if (l2 > sc2)
continue;
if (c2 < sc2)
newsol( l1, l2, c1, c2);
}
}
}
void picksums(int k)
{
if (k == 3)
{
getotherlines();
return;
}
int i;
for (i = 0; i < 9; i++)
{
if (uS[i])
continue;
st[k] = i;
uS[i] = 1;
picksums(k + 1);
uS[i] = 0;
}
}
int main()
{
freopen("zone.in", "rt", stdin);
freopen("zone.out", "wt", stdout);
scanf("%d", &N);
int i, j;
for (i = 0; i < 9; i++)
scanf("%lld", S + i);
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
{
scanf("%d", x[i] + j);
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (long long)x[i][j];
}
for (l1 = 1; l1 <= N - 1; l1++) //tai intre 1..l1 si l1+1..N
{
//determini c1 si c2 pentru orice alegere a primelor 3 sume
picksums(0);
if (sl1 != 0)
{
printf("%d %d %d %d\n", sl1, sl2, sc1, sc2);
return 0;
}
}
return 0;
}