Pagini recente » Cod sursa (job #690587) | Cod sursa (job #103508) | Cod sursa (job #2291815) | Cod sursa (job #672365) | Cod sursa (job #935624)
Cod sursa(job #935624)
#include <stdio.h>
const int nmax = 514;
void bkt(int k);
long long n, used[11], sz[11], mat[nmax][nmax], s[nmax][nmax], suma[11], sl1 = 10000, sc1 = 10000, sl2 = 10000, sc2 = 10000;
int main()
{
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
int i, j;
scanf("%lld", &n);
for(i = 1; i < 10; ++i)
{
scanf("%lld", &suma[i]);
}
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= n; ++j)
{
scanf("%lld", &mat[i][j]);
s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + mat[i][j];
}
}
bkt(1);
printf("%lld %lld %lld %lld\n", sl1, sl2, sc1, sc2);
return 0;
}
void bkt(int k)
{
int i;
if(k == 10)
{
int min = 1, mid, max = n - 1, l1, l2, c1, c2, found = 0;
long long x;
x = suma[sz[1]] + suma[sz[2]] + suma[sz[3]];
while(min <= max)
{
mid = (min + max) >> 1;
if(s[mid][n] == x)
{
found = 1;
break;
}
else if(s[mid][n] < x)
{
min = mid + 1;
}
else
{
max = mid - 1;
}
}
if(!found)
return;
l1 = mid;
min = l1 + 1;
max = n - 1;
x = suma[sz[4]] + suma[sz[5]] + suma[sz[6]];
found = 0;
while(min <= max)
{
mid = (min + max) >> 1;
if(s[mid][n] - s[l1][n] == x)
{
found = 1;
break;
}
else if(s[mid][n] - s[l1][n] < x)
{
min = mid + 1;
}
else
{
max = mid - 1;
}
}
if(!found)
return;
l2 = mid;
min = 1;
max = n - 1;
x = suma[sz[1]];
found = 0;
while(min <= max)
{
mid = (min + max) >> 1;
if(x == s[l1][mid])
{
found = 1;
break;
}
else if(x > s[l1][mid])
{
min = mid + 1;
}
else
{
max = mid - 1;
}
}
if(!found || s[l2][mid] - s[l1][mid] != suma[sz[4]] || s[n][mid] - s[l2][mid] != suma[sz[7]])
return;
c1 = mid;
found = 0;
min = c1 + 1;
max = n - 1;
x = suma[sz[2]];
while(min <= max)
{
mid = (min + max) >> 1;
if(x == s[l1][mid] - s[l1][c1])
{
found = 1;
break;
}
else if(x > s[l1][mid] - s[l1][c1])
{
min = mid + 1;
}
else
{
max = mid - 1;
}
}
if(!found || s[l2][mid] - s[l2][c1] - s[l1][mid] + s[l1][c1] != suma[sz[5]] || suma[sz[8]] != s[n][mid] - s[n][c1] - s[l2][mid] + s[l2][c1])
return;
if(s[l1][n] - s[l1][mid] != suma[sz[3]] || s[l2][n] - s[l2][mid] - s[l1][n] + s[l1][mid] != suma[sz[6]] || s[n][n] - s[n][mid] - s[l2][n] + s[l2][mid] != suma[sz[9]])
return;
c2 = mid;
if(l1 < sl1 || (l1 == sl1 && c1 < sc1) || (l1 == sl1 && c1 == sc1 && l2 < sl2) || (l1 + l2 + c1 + c2 < sl1 + sl2 + sc1 + sc2))
{
sl1 = l1;
sl2 = l2;
sc1 = c1;
sc2 = c2;
}
}
else
{
for(i = 1; i < 10; ++i)
{
if(!used[i])
{
sz[k] = i;
used[i] = 1;
bkt(k + 1);
used[i] = 0;
}
}
}
}