Pagini recente » Cod sursa (job #1882974) | Cod sursa (job #893313) | Cod sursa (job #2164444) | Profil Bita_Mihai_Valentin_322CB | Cod sursa (job #1909232)
#include <fstream>
#define DIM 515
using namespace std;
ifstream fin ("zone.in");
ofstream fout ("zone.out");
int n,i,j,v[10],a[DIM][DIM],s[DIM][DIM],x[10],OK;
int nr,nr2,nr3,nr4,nr5,nr6,p,u,pr,ul,mid,st,dr,mij,m;
int cont (int pas){
for (int i=1;i<pas;i++)
if (x[i] == x[pas])
return 0;
return 1;
}
void back (int pas){
if (pas > 9){
// fixam linia l1
for (int i=1;i<n;i++){
// cautam binar coloana c1
p = 1;
u = n-1;
while (p<=u){
m = (p+u)/2;
nr = s[i][m];
if (nr == v[x[1]])
break;
else
if (nr < v[x[1]])
p = m+1;
else
u = m-1;
}
if (p<=u){ // am putut fixa coloana 1 (m)
// cautam binar coloana 2;
st = m+1;
dr = n;
while (st <= dr){
mid = (st+dr)/2;
nr = s[i][mid]-s[i][m];
nr2 = s[i][n] - s[i][mid];
if (nr == v[x[2]] && nr2 == v[x[3]])
break;
else
if (nr < v[x[2]])
st = mid+1;
else
dr = mid-1;
}
if (st <= dr){ // am putut fixa coloana 2 (mid)
// cautam binar linia 2
pr = 2;
ul = n;
while (pr<=ul){
mij = (pr+ul)/2;
nr = s[mij][m] - s[i][m];
nr2 = s[mij][mid]-s[mij][m]-s[i][mid]+s[i][m];
nr3 = s[mij][n]-s[mij][mid]-s[i][n]+s[i][mid];
nr4 = s[n][m]-s[mij][m];
nr5 = s[n][mid]-s[n][m]-s[mij][mid]+s[mij][m];
nr6 = s[n][n]-s[n][mid]-s[mij][n]+s[mij][mid];
if (nr==v[x[4]]&&nr2==v[x[5]]&&nr3==v[x[6]]&&nr4==v[x[7]]&&nr5==v[x[8]]&&nr6==v[x[9]])
break;
else
if (nr < v[x[4]])
pr = mij+1;
else
ul = mij-1;
}
if (pr <= ul){
// am putut fixa si linia a doua
// deci am gasit solutia
fout<<i<<" "<<mij<<" "<<m<<" "<<mid;
OK = 1;
break;
//continue;
// return 0;
}
}
}
}
return;
}
if (OK==0){
for (int i=1;i<=9;i++){
x[pas] = i;
if (cont(pas))
back (pas+1);
}
}
}
int main (){
fin>>n;
for (i=1;i<=9;i++)
fin>>v[i]; // sumele
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
fin>>a[i][j];
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];
back (1);
return 0;
}