Pagini recente » Cod sursa (job #2046838) | Cod sursa (job #848111) | Cod sursa (job #1392729) | Cod sursa (job #2448041) | Cod sursa (job #849050)
Cod sursa(job #849050)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("zone.in");
ofstream g("zone.out");
#define nmax 513
#define Cifmax (1<<14)
#define ll long long
ll aux[10], s[nmax][nmax];
int n, a[10];
vector<int> lista[10];
char S[Cifmax];
int poz = 0;
void buf(int &nr){
nr = 0;
while( (S[poz]<'0' || S[poz]>'9') && S[poz] != '-') {
++poz;
if (poz == Cifmax){
fread(S, 1, Cifmax, stdin);
poz = 0;
}
}
int semn = 1;
if (S[poz] == '-'){
++poz; semn = -1;
if (poz == Cifmax){
fread(S, 1, Cifmax, stdin);
poz = 0;
}
}
while( S[poz] >= '0' && S[poz]<='9' ){
nr = nr * 10 + (S[poz] - '0');
++poz; if (poz == Cifmax){
fread(S, 1, Cifmax, stdin);
poz = 0;
}
}
}
void citeste(){
buf(n);
for(int i=1; i<=9; ++i) buf(a[i]);
sort(a+1, a+10);
int x; int ord = 0;
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
++ord; buf(x);
s[i][j] = s[i-1][j] + s[i][j-1] -s[i-1][j-1] + (ll)x;
for(int k=1; k<=9; ++k){
if (s[i][j] == a[k]){
lista[k].push_back(ord); break;
}
}
}
}
}
int fax(int x){
if (x <= n) return 1;
if (x % n == 0) return x/n;
return x/n+1;
}
int fay(int y){
y = y % n;
if (y == 0) return n;
return y;
}
inline bool baga_sume(int poz, int x1, int y1, int x4, int y4){
//poz e luata
int x2 = x1; int y2 = y4;
int x3 = x4; int y3 = y1;
aux[0] = 0;
aux[1] = s[x1][y1];
aux[2] = s[x2][y2] - s[x1][y1];
aux[3] = s[x2][n] - s[x2][y2];
aux[4] = s[x3][y3] - s[x1][y1];
aux[5] = s[x4][y4] - s[x2][y2] - s[x3][y3] + s[x1][y1];
aux[6] = s[x4][n] - s[x2][n] - s[x4][y4] + s[x2][y2];
aux[7] = s[n][y1] - s[x4][y1];
aux[8] = s[n][y4] - s[x4][y4] - s[n][y1] + s[x3][y3];
aux[9] = s[n][n] - s[x4][n] - s[n][y4] + s[x4][y4];
sort(aux+1, aux+10);
for(int i=1; i<=9; ++i){
if (aux[i] != a[i]) return 0;
}
return 1;
}
void rezolva(){
for(int i=2; i<n; ++i){
for(int j=2; j<n; ++j){// (i,j) e coltul dreapta jos al patratului din centru
for(int k=1; k<=9; ++k){
for(int w=0; w<lista[k].size(); ++w){
int x = fax(lista[k][w]); int y = fay(lista[k][w]);
if (x >= 1 && y >= 1 && x < i && y < j){
if (baga_sume(k, x, y, i, j) == 1){
g << x << " " << i << " " << y << " "<<j << "\n";
return;
}
}
}
}
}
}
}
int main(){
freopen("zone.in", "r", stdin);
citeste();
rezolva();
g.close();
return 0;
}