Pagini recente » Cod sursa (job #602432) | Cod sursa (job #3316663) | Cod sursa (job #597725) | Cod sursa (job #2376394) | Cod sursa (job #3322676)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("zone.in");
ofstream cout ("zone.out");
int n;
long long int sume[10];
long long int a[515][515];
long long int sump[515][515];
long long int s[10];
int p1x,p1y,p2x,p2y;
bool amsolutie=0;
int lr1,lr2,cr1,cr2;
int cbin(long long x, int st, int dr) // ← tip corectat
{
while (st <= dr)
{
int mij = (st + dr) / 2;
if (sume[mij] == x)
return 1;
if (sume[mij] < x)
st = mij + 1;
else
dr = mij - 1;
}
return 0;
}
int verif(int &l1, int &l2, int &c1, int &c2)
{
for (int i = 1; i <= n-2; i++) // ← limite corectate
for (int j = 1; j <= n-2; j++) // ← limite corectate
{
p1x = i;
p1y = j;
long long saux = sump[p1x][p1y]; // ← tip corectat
if (cbin(saux, 1, 9) == 1)
{
for (int p = i+1; p <= n-1; p++) // ← limite corectate
{
bool gasit = 1;
for (int q = j+1; q <= n-1 && gasit == 1; q++) // ← limite corectate
{
p2x = p;
p2y = q;
s[1] = sump[i][j];
s[2] = sump[i][q] - sump[i][j];
s[3] = sump[i][n] - sump[i][q];
s[4] = sump[p][j] - sump[i][j];
s[5] = sump[p][q] - sump[i][q] - sump[p][j] + sump[i][j];
s[6] = sump[p][n] - sump[i][n] - sump[p][q] + sump[i][q];
s[7] = sump[n][j] - sump[p][j]; // ← zona 7 corectă
s[8] = sump[n][q] - sump[p][q] - sump[n][j] + sump[p][j];
s[9] = sump[n][n] - sump[p][n] - sump[n][q] + sump[p][q];
sort(s+1, s+10);
for (int f = 1; f <= 9; f++)
if (s[f] != sume[f])
{
gasit = 0;
break;
}
if (gasit == 1)
{
if (!amsolutie ||
i < lr1 ||
(i == lr1 && j < cr1) ||
(i == lr1 && j == cr1 && p < lr2) ||
(i == lr1 && j == cr1 && p == lr2 &&
i + p + j + q < lr1 + lr2 + cr1 + cr2))
{
lr1 = i;
lr2 = p;
cr1 = j;
cr2 = q;
amsolutie = 1;
}
}
}
}
}
}
return 0;
}
int main()
{
cin >> n;
for (int i = 1; i <= 9; i++)
cin >> sume[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
sump[i][j] = a[i][j] + sump[i-1][j] + sump[i][j-1] - sump[i-1][j-1];
}
sort(sume+1, sume+10);
int a=0,b=0,c=0,d=0;
verif(a,b,c,d);
cout << lr1 << ' ' << lr2 << ' ' << cr1 << ' ' << cr2;
return 0;
}