Cod sursa(job #1605554)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 19 februarie 2016 09:59:15
Problema Zone Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define DIM 515

int N, Suma[15], Mat[DIM][DIM];

int Try(int l1, int l2, int c1, int c2);

int main() {
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);

    scanf("%d\n", &N);

    for(int i = 1; i <= 9; ++i) {
        scanf("%d", &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] += Mat[i - 1][j] + Mat[i][j - 1] - Mat[i - 1][j - 1];
        }
    }

    for(int l1 = 1; l1 < N; ++l1) {
        for(int l2 = l1 + 1; l2 < N; ++l2) {
            for(int c1 = 1; c1 < N; ++c1) {
                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) {
    int 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;
}