import java.util.Scanner; /** * This class realizes the calculation * of the expense of energy more shortly * to liberate the space to the train. * It calculates all the possibilities * finding the best play. * It print the expense of energy more * down and the number of the way (column) * that expires with this expense of energy. * @author Diego Orozco */ public class Solution { /** * Gets data from standard input */ private Scanner input = null; // Reference that save the number of rows private int row = 0; // Reference that save the number of column private int column = 0; // Reference that save the matrix of the ways of the train private int train[][] = null; // Reference that save the matrix of the lowest number of expense of energy private int numberMove[][] = null; /** * Start the execution of the solution * @param args Command line arguments */ public static void main(String args[]) { Solution solution = new Solution(); solution.run(); } /** * Run the solution. This method is called from main() */ public void run() { this.input = new Scanner(System.in); // save the number of rows this.row = input.nextInt(); // save the number of columns this.column = input.nextInt(); // create the matrix of the ways of the train this.train = new int [row][column]; // create the matrix of the lowest number of expense of energy this.numberMove = new int [column][2]; // read a matrix from standard input readData(input); // check if there are 0 in every row if ( validMatrix() ) { // realize the calculation to liberate the way for the train freeColumn(); // variable that save the smallest number int smallerNumber = findSmaller(numberMove); // print the smallest number System.out.print(smallerNumber + " "); // print the columns with fewer movements printColumn(smallerNumber); } } /** * read a matrix from standard input * this method read data for fill to matrix of the ways of the train. * @param input */ public void readData(Scanner input) { // read all values for the matrix for (int rows = 0; rows < this.row; rows++) { // read all values for current row for (int cols = 0; cols < this.column; cols++) { train[rows][cols] = input.nextInt() ; } } } /** * check if there are 0 in every row * In case of zeros do not exist, * it is print by standard exit "Invalid row N" * where N is the line without Zero * @return boolean true if the matrix has zeros */ public boolean validMatrix() { boolean isValid = true; for (int rows = 0; rows < this.train.length; rows++) { int isZero = 0; for (int cols = 0; cols < this.column; cols++) { if ( this.train[rows][cols] == 0 ) { isZero++; } } if ( isZero == 0 ) { System.out.println("Invalid row " + (rows + 1)); isValid = false; } } return isValid; } /** * realize the calculation to liberate the way * for the train. The above mentioned calculation * is realized by means of the calculation of the * zero most near to the column position in the * one that is. * The calculation is done from left side to right * and from right to left side */ public void freeColumn() { // It takes the control of the column for (int column = 0; column < this.column; column++) { // variable that take the control of the movements int move = 0; // It takes the control of the row for (int row = 0; row < this.row; row++) { // if in this position it is zero, it is not done at all if (this.train[row][column]==0) { } // if in this position it is not zero else { // calculate the nearest zero in this position of left side to right int posiLeft = findZeroLeft (row, column); // calculate the nearest zero in this position of right side to left int posiRight = findZeroRight (row, column); // calculate the difference and the quantity of movements from the left side int left = Math.abs(column - posiLeft); // To calculate the difference and the quantity of movements from the right side int right = Math.abs(posiRight - column); // Determines who carries less energy if ( left > right ) { // move += right; } else { move += left; } } } // save in the matrix the column and the quantity of movements needed to liberate the way this.numberMove [column][0] = column; this.numberMove [column][1] = move; } } /** * calculate the nearest zero in this position of left side to right * @param row Row in the one that is the calculation to liberate the way * @param column Column in the one that is the calculation to liberate the way * @return quantity of movements needed to liberate the way */ public int findZeroLeft(int row, int column) { int posi = 1000; for (int index = 0; index < column; index++) { if ( this.train[row][index] == 0 ) { posi = index; } } return posi; } /** * calculate the nearest zero in this position of right side to left * @param row Row in the one that is the calculation to liberate the way * @param column Column in the one that is the calculation to liberate the way * @return quantity of movements needed to liberate the way */ public int findZeroRight(int row, int column) { int posi = 1000; if (column + 1 < this.column ) { for (int index = column; index < this.column; index++) { if ( this.train[row][index] == 0 ) { return index; } } } return posi; } /** * It searches in the matrix that stores the * quantity of necessary movements to liberate * the way, the minor number of movements between * all the columns * @param numberMove matrix that save of the * lowest number of expense of energy * @return minor number found in the matrix */ public int findSmaller (int numberMove[][]) { // Variable that stores the minor number of the matrix int smaller = 1000; for (int rows = 0; rows < this.column; rows++) { if ( this.numberMove[rows][1] < smaller ) { // update the variable because a smaller number was found smaller = numberMove[rows][1]; } } return smaller; } /** * It searches between the columns stored in the matrix, * the columns that realize the minor number of movements * and them it print * @param number */ public void printColumn(int number) { for (int rows = 0; rows < this.column; rows++) { if ( this.numberMove[rows][1] == number ) { // print the candidate(s) with the minor number of the movements System.out.print((numberMove[rows][0] + 1) + " "); } } } }