Pagini recente » Cod sursa (job #897054) | Cod sursa (job #1329432) | Borderou de evaluare (job #1036676) | Cod sursa (job #3120396) | Cod sursa (job #358425)
Cod sursa(job #358425)
#include <stdio.h>
#define Nmax 520
long long A[Nmax][Nmax], B[Nmax][Nmax], v[15], viz[15], v2[15];
long long n, i, j, l, k, L1, L2, C1, C2, aux, ok, aaa, bbb, ij;
FILE * g = fopen ("zone.out","w");
int binara(long long suma, int indice){
long long st=1;
long long dr=n;
long long mj, a, b, c, x;
if (indice==1)
while (st <= dr) {
mj = st+(dr-st)/2;
x = B[L1][mj];
if (x < suma)
st = mj+1;
else
if (x > suma)
dr = mj-1;
else
return mj;
}
if (indice==2)
while (st <= dr) {
mj = st+(dr-st)/2;
x = B[mj][C1] - B[L1][C1];
if (x < suma)
st = mj+1;
else
if (x > suma)
dr = mj-1;
else
return mj;
}
if (indice==3)
while (st <= dr) {
mj = st+(dr-st)/2;
x = B[L2][mj] - B[L2][C1] - B[L1][mj] + B[L1][C1];
if (x < suma)
st = mj+1;
else
if (x > suma)
dr = mj-1;
else
return mj;
}
return 0;
}
void preprocesare(){
for (i = 1 ; i <= n ; i++)
for (j = 1 ; j <= n ; j++)
B[i][j] = A[i][j] + B[i-1][j] + B[i][j-1] - B[i-1][j-1];
}
int impartire(){
for (i = 1 ; i <= n ; i++){
L1 = i;
for (j = 1 ; j <= 9 ; j++){
C1 = binara(v[j],1);
for (l = 1 ; l <= 9 ; l++){
L2 = binara(v[l],2);
for (k = 1 ; k <= n ; k++){
C2 = binara(v[k],3);
v2[1]=B[L1][C1];
v2[2]=B[L2][C1] - B[L1][C1];
v2[3]=B[L2][C2] - B[L2][C1] - B[L1][C2] + B[L1][C1];
v2[4]=B[L1][C2] - B[L1][C1];
v2[5]=B[L1][n] - B[L1][C2];
v2[6]=B[L2][n] - B[L2][C2] - B[L1][n] + B[L1][C2];
v2[7]=B[n][C1] - B[L2][C1];
v2[8]=B[n][C2] - B[n][C1] - B[L2][C2] + B[L2][C1];
v2[9]=B[n][n] - B[n][C2] - B[L2][n] + B[L2][C2];
for (aaa = 1 ; aaa < 9 ; aaa++)
for (bbb = aaa+1 ; bbb <= 9 ; bbb++)
if (v2[bbb]<v2[aaa]) {
aux=v2[aaa];
v2[aaa]=v2[bbb];
v2[bbb]=aux;
}
ok = 1;
for (ij = 1 ; ij <= 9 ; ij++)
if (v[ij] != v2[ij]) ok = 0;
if (ok==1) return 0;
}
}
}
}
return 0;
}
int main(){
FILE * f = fopen("zone.in","r");
fscanf (f, "%d" , &n);
for (i = 1 ; i <= 9 ; i++)
fscanf(f , "%d" , &v[i]);
for (i = 1 ; i < 9 ; i++)
for ( j = i + 1 ; j <= 9 ; j++)
if ( v[i] > v[j] ){
aux = v[i];
v[i] = v[j];
v[j] = aux;
}
for (i = 1 ; i <= n ; i++)
for (j = 1 ; j <= n ; j++)
fscanf (f, "%d", &A[i][j]);
preprocesare();
impartire();
fprintf(g , "%ld " , L1);
fprintf(g , "%ld " , L2);
fprintf(g , "%ld " , C1);
fprintf(g , "%ld" , C2);
fclose(f);
fclose(g);
return 0;
}