Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2471
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2471
Quadrado
Por OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
Um quadrado quase mágico, de dimensões N × N, é um quadrado que obedece à seguinte condição. Existe um número inteiro positivo M tal que: para qualquer linha, a soma dos números da linha é igual a M; e para qualquer coluna, a soma dos números da coluna é também igual a M. O quadrado seria mágico, e não apenas quase mágico, se a soma das diagonais também fosse M. Por exemplo, a figura abaixo, parte (a), apresenta um quadrado quase mágico onde M = 21.
Laura construiu um quadrado quase mágico e alterou, propositalmente, um dos números! Nesta tarefa, você deve escrever um programa que, dado o quadrado quase mágico alterado por Laura, descubra qual era o número original antes da alteração e qual número foi colocado no lugar. Por exemplo, na parte (b) da figura, o número original era 1, que Laura alterou para 7.
Entrada
A primeira linha da entrada contém apenas um número N (3 ≤ N ≤ 50), representando a dimensão do quadrado. As N linhas seguintes contêm, cada uma, N números inteiros (entre 1 e 10000), definindo o quadrado. A entrada é garantidamente um quadrado quase mágico onde exatamente um número foi alterado.
Saída
Seu programa deve imprimir apenas uma linha contendo dois números: primeiro o número original e depois o número que Laura colocou no seu lugar.
| Exemplos de Entrada | Exemplos de Saída |
|
3 |
1 7 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define MAXN 52
int matriz[MAXN][MAXN];
int soma[MAXN][MAXN];
int acumulada[MAXN][MAXN];
int n;
int main() {
scanf("%d", &n);
for (int linha = 1; linha < = n; linha++) {
for (int coluna = 1; coluna < = n; coluna++) {
scanf("%d", &matriz[linha][coluna]);
soma[linha][coluna] =
soma[linha][coluna - 1] + matriz[linha][coluna];
}
}
for (int coluna = 1; coluna < = n; coluna++) {
for (int linha = 1; linha < = n; linha++) {
acumulada[linha][coluna] =
acumulada[linha - 1][coluna] + matriz[linha][coluna];
}
}
int moore = 0, escolhida = -1;
for (int linha = 1; linha < = n; linha++) {
if (moore == 0) {
escolhida = soma[linha][n];
moore = 1;
} else if (soma[linha][n] == escolhida) {
moore++;
} else
moore--;
}
for (int i = 1; i < = n; i++) {
for (int j = 1; j < = n; j++) {
if (soma[i][n] != escolhida && acumulada[n][j] != escolhida) {
printf("%d %d\n",
(2 * escolhida - acumulada[n][j] - soma[i][n]) / 2 +
matriz[i][j],
matriz[i][j]);
}
}
}
return 0;
}
Input
3 6 6
8 6 7
4 3 8
Output