Pagini recente » Cod sursa (job #2293344) | Cod sursa (job #426820) | Cod sursa (job #358792) | Cod sursa (job #2774784) | Cod sursa (job #2078077)
#include <fstream>
#define DIM 515
using namespace std;
ifstream fin ("zone.in");
ofstream fout ("zone.out");
int n,i,j,a[DIM][DIM],s[DIM][DIM],v[11],x[11],OK;
int verif (int pas){
for (int i=1;i<pas;i++)
if (x[i] == x[pas])
return 0;
return 1;
}
void back (int pas){
if (OK == 1)
return;
if (pas == 10){
/// fixam prima linie
int c1,c2,l1,l2,mid,st,dr;
for (int i=1;i<n-1;i++){
/// cautam binar coloana 1
int ok = 0;
st = 1;
dr = n-2;
while (st <= dr){
mid = (st+dr)/2;
if (s[i][mid] == v[x[1]]){
c1 = mid;
break;
}
else{
if (s[i][mid] < v[x[1]])
st = mid+1;
else
dr = mid-1;
}
}
if (st > dr){ /// nu am putut fixa coloana 1
ok = 1;
continue;
}
//if (st <= dr){/// inseamna ca am gasit suma 1
// int c1 = mid;
/// cautam binar coloana 2
st = c1+1;
dr = n-1;
while (st <=dr){
mid = (st+dr)/2;
if (s[i][mid] - s[i][c1] == v[x[2]])
break;
else
if (s[i][mid] - s[i][c1] < v[x[2]])
st = mid+1;
else
dr = mid-1;
}
if (st > dr){
ok = 1;
continue;
}
else{
if (s[i][n] - s[i][mid] == v[x[3]]){
/// am putut fixa coloana a doua
c2 = mid;
}
else{
ok = 1;
continue;
}
}
/// cautam binar linia a doua
st = i+1;
dr = n-1;
while (st <= dr){
mid = (st+dr)/2;
int sum = s[mid][c1] - s[i][c1];
if (sum == v[x[4]]){
l2 = mid;
break;
}
else{
if (sum < v[x[4]])
st = mid+1;
else
dr = mid-1;
}
}
if (st > dr){ /// nu am putut fixa linia 2
ok = 1;
continue;
}
//int l2 = mid;
int sum5 = s[mid][c2] - s[mid][c1] - s[i][c2] + s[i][c1];
int sum6 = s[mid][n] - s[mid][c2] - s[i][n] + s[i][c2];
int sum7 = s[n][c1] - s[l2][c1];
int sum8 = s[n][c2] - s[n][c1] - s[l2][c2] + s[l2][c1];
int sum9 = s[n][n] - s[n][c2] - s[l2][n] + s[l2][c2];
if (!(sum5 == v[x[5]] && sum6 == v[x[6]] && sum7 == v[x[7]] && sum8 == v[x[8]] && sum9 == v[x[9]]) ){
ok = 1;
continue;
}
/// am gasit o solutie;
fout<<i<<" "<<l2<<" "<<c1<<" "<<c2;
OK = 1;
return;
}
}
for (int i=1;i<=9;i++){
x[pas] = i;
if (verif(pas))
back (pas+1);
}
}
int main (){
fin>>n;
for (i=1;i<=9;i++)
fin>>v[i];
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
fin>>a[i][j];
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
}
back (1);
return 0;
}