Pagini recente » Cod sursa (job #347348) | Cod sursa (job #183995) | Cod sursa (job #298908) | Cod sursa (job #2939031) | Cod sursa (job #1636531)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define DIM 515
long long Suma[15], Mat[DIM][DIM];
int N;
int Try(int l1, int l2, int c1, int c2);
int bin_search(long long x);
int main() {
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
scanf("%d\n", &N);
for(int i = 1; i <= 9; ++i) {
scanf("%lld", &Suma[i]);
}
sort(Suma + 1, Suma + 10);
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= N; ++j) {
scanf("%d", &Mat[i][j]);
Mat[i][j] += 1LL * Mat[i - 1][j] + Mat[i][j - 1] - Mat[i - 1][j - 1];
}
}
for(int l1 = 1; l1 < N; ++l1) {
for(int c1 = 1; c1 < N; ++c1) {
int p = bin_search(Mat[l1][c1]);
if(Suma[p] == Mat[l1][c1]) {
for(int l2 = l1 + 1; l2 <= N; ++l2) {
for(int c2 = c1 + 1; c2 <= N; ++c2) {
if(Try(l1, l2, c1, c2) == 1) {
cout << l1 << ' ' << l2 << ' ' << c1 << ' ' << c2 << '\n';
return 0;
}
}
}
}
}
}
cout << "N-aveti solutie :'(\n";
return 0;
}
int Try(int l1, int l2, int c1, int c2) {
long long VS[14];
VS[1] = Mat[l1][c1];
VS[2] = Mat[l1][c2] - VS[1];
VS[3] = Mat[l1][N] - VS[2] - VS[1];
VS[4] = Mat[l2][c1] - VS[1];
VS[5] = Mat[l2][c2] - VS[2] - VS[4] - VS[1];
VS[6] = Mat[l2][N] - VS[1] - VS[2] - VS[3] - VS[4] - VS[5];
VS[7] = Mat[N][c1] - VS[4] - VS[1];
VS[8] = Mat[N][c2] - VS[1] - VS[2] - VS[4] - VS[5] - VS[7];
VS[9] = Mat[N][N] - VS[1] - VS[2] - VS[3] - VS[4] - VS[5] - VS[6] - VS[7] - VS[8];
sort(VS + 1, VS + 10);
for(int i = 1; i < 10; ++i) {
if(VS[i] != Suma[i]) {
return 0;
}
}
return 1;
}
int bin_search(long long x) {
int put = 8;
int pos = 0;
while(put) {
if(pos + put <= 9) {
if(Suma[pos + put] <= x) {
pos += put;
}
}
put >>= 1;
}
return pos;
}