(SPOJ) Quadrado mágico - Solution
Link to the problem: http://br.spoj.com/problems/MAGICO11/
In order to solve this problem, it is only necessary to check if the numbers are valid, if all the numbers between 1 and size^2 are being used exactly once and if the sums (row, column, diagonal) are equal.
import java.io.*;
import java.util.*;
class Main {
public static int reader(BufferedReader br) throws NumberFormatException, IOException {
int n;
int resp = 0;
while (true) {
n = br.read();
if (n >= '0' && n <= '9') {
break;
}
}
while (true) {
resp = resp*10 + n-'0';
n = br.read();
if (n < '0' || n > '9') {
break;
}
}
return resp;
}
public void process() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = reader(br);
int[][] matrix = new int[size][size];
int[] numbers = new int[size*size + 1];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
matrix[i][j] = reader(br);
if (matrix[i][j] > size*size) { // if it is not a valid value
System.out.println("0");
return;
}
numbers[matrix[i][j]] = 1;
}
}
br.close();
// check if all the values are present
for (int i = 1; i <= size*size; i++) {
if (numbers[i] == 0) {
System.out.println("0");
return;
}
}
int sumPart = 0;
HashSet<Integer> sum = new HashSet<>();
// check sum of lines
for (int i = 0; i < size; i++) {
sumPart = 0;
for (int j = 0; j < size; j++) {
sumPart += matrix[i][j];
}
sum.add(sumPart);
if (sum.size() > 1) {
System.out.println("0");
return;
}
}
// check sum of columns
for (int i = 0; i < size; i++) {
sumPart = 0;
for (int j = 0; j < size; j++) {
sumPart += matrix[j][i];
}
sum.add(sumPart);
if (sum.size() > 1) {
System.out.println("0");
return;
}
}
// check sum of diagonals
sumPart = 0;
for (int i = 0; i < size; i++) {
sumPart += matrix[i][i];
}
int col = size-1;
sumPart = 0;
for (int i = 0; i < size; i++) {
sumPart += matrix[i][col--];
}
sum.add(sumPart);
if (sum.size() > 1) {
System.out.println("0");
return;
}
System.out.println(sumPart);
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
In order to solve this problem, it is only necessary to check if the numbers are valid, if all the numbers between 1 and size^2 are being used exactly once and if the sums (row, column, diagonal) are equal.
import java.io.*;
import java.util.*;
class Main {
public static int reader(BufferedReader br) throws NumberFormatException, IOException {
int n;
int resp = 0;
while (true) {
n = br.read();
if (n >= '0' && n <= '9') {
break;
}
}
while (true) {
resp = resp*10 + n-'0';
n = br.read();
if (n < '0' || n > '9') {
break;
}
}
return resp;
}
public void process() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = reader(br);
int[][] matrix = new int[size][size];
int[] numbers = new int[size*size + 1];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
matrix[i][j] = reader(br);
if (matrix[i][j] > size*size) { // if it is not a valid value
System.out.println("0");
return;
}
numbers[matrix[i][j]] = 1;
}
}
br.close();
// check if all the values are present
for (int i = 1; i <= size*size; i++) {
if (numbers[i] == 0) {
System.out.println("0");
return;
}
}
int sumPart = 0;
HashSet<Integer> sum = new HashSet<>();
// check sum of lines
for (int i = 0; i < size; i++) {
sumPart = 0;
for (int j = 0; j < size; j++) {
sumPart += matrix[i][j];
}
sum.add(sumPart);
if (sum.size() > 1) {
System.out.println("0");
return;
}
}
// check sum of columns
for (int i = 0; i < size; i++) {
sumPart = 0;
for (int j = 0; j < size; j++) {
sumPart += matrix[j][i];
}
sum.add(sumPart);
if (sum.size() > 1) {
System.out.println("0");
return;
}
}
// check sum of diagonals
sumPart = 0;
for (int i = 0; i < size; i++) {
sumPart += matrix[i][i];
}
int col = size-1;
sumPart = 0;
for (int i = 0; i < size; i++) {
sumPart += matrix[i][col--];
}
sum.add(sumPart);
if (sum.size() > 1) {
System.out.println("0");
return;
}
System.out.println(sumPart);
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
Comments
Post a Comment