OIG - Kwadrat magiczny

Przerabiam sobie zadania z OIG i utknąłem na tym http://www.main.edu.pl/user.phtml?op=showtask&task=kwa&con=OIG4. Rozwiązanie oparłem na wzorze z http://pl.wikipedia.org/wiki/Kwadrat_magiczny_%28matematyka%29, niby banalne, ale main wyrzuca mi integer out of range, co chyba znaczy, że mój program daje wyniki ujemne dla niektórych pól. Jeśli się komuś chce to prosiłbym o pomoc w rozwiązaniu, oto kod:

#include <cstdio>

using namespace std;

typedef long long int LL;

const int MAX_SIZE = 1000 + 5;

LL A[MAX_SIZE][MAX_SIZE];
LL val[MAX_SIZE];

int n;

void read()
{
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			scanf("%lld", &A[i][j]);
}

void fill()
{
	LL max;
	
	if(A[0][0] != 0 && A[n - 1][n - 1] != 0)
		max = ((A[0][0] + A[n - 1][n - 1]) * (LL)n) / 2;
	else
		max = ((A[0][n - 1] + A[n - 1][0]) * (LL)n) / 2;
	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			val[i] += A[i][j];
		
	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(A[i][j] == 0)
			{
				A[i][j] = max - val[i];
				break;
			}
}

void print()
{
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
			printf("%lld ", A[i][j]);
			
		printf("\n");
	}
}

int main()
{
	read();
	fill();
	print();
	
	return 0;
}

a gdzie zerowanie tablicy val?
Po co to +5 dla MAX_SIZE?

To +5 na wszelki wypadek (pamięci dużo nie zżera), a zerować nie trzeba, bo tablica zadeklarowania jest globalnie.

Oto przykładowy test, dla którego mój program daje złą odpowiedź:

10
164 0 153 21 10 27 67 105 72 223
49 107 159 421 22 0 4 121 71 47
219 93 86 80 95 127 74 68 33 0
150 172 84 118 110 119 77 0 51 17
0 43 31 50 76 41 433 53 160 45
42 298 89 1 0 36 52 87 63 91
55 28 37 56 20 101 0 416 35 106
115 69 0 113 151 90 82 7 98 108
100 8 14 102 143 104 62 39 0 208
38 24 180 0 132 356 3 2 197 30

Mój out:

164 128 153 21 10 27 67 105 72 223 
49 107 159 421 22 -31 4 121 71 47 
219 93 86 80 95 127 74 68 33 95 
150 172 84 118 110 119 77 72 51 17 
38 43 31 50 76 41 433 53 160 45 
42 298 89 1 211 36 52 87 63 91 
55 28 37 56 20 101 116 416 35 106 
115 69 137 113 151 90 82 7 98 108 
100 8 14 102 143 104 62 39 190 208 
38 24 180 8 132 356 3 2 197 30 

A więc mój program działa dobrze tylko, coś jest nie tak ze wzorem:

n - liczba wierszy
X, Y - dowolne dwie liczby ułożone symetrycznie względem środka kwadratu
W podanym teście widać, że sumy dowolnych liczb X i Y, jakie weźmiemy nie są jednakowe. Wszędzie gdzie szukałem przy tym wzorze nie było żadnego założenia, kiedy jest prawdziwy... Chyba zacznę myśleć nad innym rozwiązaniem tego zadania.

Porównując z angielską wiki, to na polskiej jest błąd!
Kwadraty z liczbami pierwszymi (n=5) nie spełniają tego wzoru.

Prawidłowy wynik to:

164 168 153 21  10  27  67  105 72  223
49  107 159 421 22  9   4   121 71  47
219 93  86  80  95  127 74  68  33  135
150 172 84  118 110 119 77  112 51  17
78  43  31  50  76  41  433 53  160 45
42  298 89  1   251 36  52  87  63  91
55  28  37  56  20  101 156 416 35  106
115 69  177 113 151 90  82  7   98  108
100 8   14  102 143 104 62  39  230 208
38  24  180 48  132 356 3   2   197 30

Suma magiczna to 1010.
Metoda jest prosta i łatwo ją wymyślić.

Czy mógłbym cię prosić o podpowiedź (nie kod) jak to zrobić, bo nie wymyśliłem niczego...

1. sprawdzasz przekątne
   a. może się zdarzyć, że jedna przekątna jest kompletna -> problem trywialny
   b. liczysz ile danych brakuje na przekątnych (na później)
2. zapamiętujesz pozycje pustych pól
3. liczysz sumy wierszy i znajdujesz maximum.
4. uzupełniasz puste pola tak by sumy wierszy miały tą samą wartość (na początek policzone maksimum).
5. ponownie liczysz sumę przekątnych.
6. znając:
   • obecną sumę dla poszczególnych wierszy
   • sumę dla przekątnych
   • ilość nieznanych pól na przekątnych (patrz 1b)
     Można policzyć jaką wartość trzeba dodać do każdego nieznanego pola, by sumy się zgodziły.

Męczyłem się z tym zadaniem 2 dni i w końcu się udało, wielkie dzięki