Changing the Sitting Arrangement
Source: aizu

Problem C
Changing the Sitting Arrangement

You are the teacher of a class of n2 pupils at an elementary school. Seats in the classroom are set up in a square shape of n rows (row 1 through row n) by n columns (column 1 through column n).

You are planning a change in the sitting arrangement. In order for your pupils to interact with many different pupils, you want to make those currently on adjacent seats have remote seats.

There is at least one sitting arrangement such that every pair of pupils currently on adjacent seats have seats with the Manhattan distance of no less than ⌊n / 2⌋ between them. Your task is to find such an arrangement. Here, ⌊x⌋ represents the largest integer less than or equal to x. The Manhattan distance of two seats are the sum of the absolute difference of their row numbers and that of their column numbers. Adjacent seats mean those with the Manhattan distance 1.

For example, in the first dataset of Sample Input (n = 4), pupils at the four adjacent seats of the pupil no. 10 are those numbered 6, 9, 11, and 14. In the Output for the Sample Input corresponding to this, their seats have Manhattan distances 3, 3, 2, and 3 from the seat of the pupil no. 10, all of which are ⌊ 4 / 2 ⌋ = 2 or greater. This condition also holds for all the other pupils.

Input

The input consists of multiple datasets, each in the format below. The number of datasets does not exceed 50.

n
a11 a12 ⋯ a1n
a21 a22 ⋯ a2n
 ⋮
an1 an2 ⋯ ann


Here, n is the number of rows and also columns of the seats in the classroom (2 ≤ n ≤ 50). The following n lines denote the current sitting arrangement. Each aij gives the ID number of the pupil currently sitting in the i-th row from the back and the j-th column from the left, as seen from the teacher's desk. aij's are integers 1 through n2, without duplicates.

The end of the input is indicated by a line consisting of a single zero.

Output

For each dataset, output a sitting arrangement satisfying the condition stated above in the same format as in the input. If there are two or more such arrangements, any of them will do.

Sample Input
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
7
1 8 15 22 29 36 43
2 9 16 23 30 37 44
3 10 17 24 31 38 45
4 11 18 25 32 39 46
5 12 19 26 33 40 47
6 13 20 27 34 41 48
7 14 21 28 35 42 49
0

Output for the Sample Input
6 1 14 8
16 13 11 9
4 10 2 12
5 3 15 7
4 20 18 44 12 16 36
23 38 40 48 7 39 26
29 9 14 35 37 2 49
13 46 30 5 45 43 24
42 33 17 22 19 27 47
1 3 21 25 11 15 41
31 6 8 34 28 32 10


C++ solution:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(i=0;i<N;i++)
#define ll long long

int main(void){
    vector<ll>ans;
    ll i,j,k;

    for(;;){
        ll N;
        ll A[50][50];
        ll P[50];
        cin>>N;
        if(N==0)break;
        j=0;
        for(i=1;i<N;i+=2){
            P[j]=i;j++;
        }
        for(i=0;i<N;i+=2){
            P[j]=i;j++;
        }
        rep(i,N)rep(j,N)cin>>A[i][j];
        rep(i,N){
            rep(j,N)cout<<A[P[i]][P[j]]<<' ';
            cout<<endl;
        }
    }

    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	for {
		scanner.Scan()
		line := scanner.Text()
		if line == "0" {
			break
		}
		n, err := strconv.Atoi(line)
		if err != nil {
			fmt.Println("Error reading n:", err)
			continue
		}
		a := make([][]string, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			row := scanner.Text()
			a[i] = strings.Fields(row)
		}
		b := make([][]string, n)
		for j := 0; j < n; j++ {
			var l []string
			for i := 1; i < n; i += 2 {
				l = append(l, a[j][i])
			}
			for i := 0; i < n; i += 2 {
				l = append(l, a[j][i])
			}
			b[j] = l
		}
		for j := 1; j < n; j += 2 {
			fmt.Println(strings.Join(b[j], " "))
		}
		for j := 0; j < n; j += 2 {
			fmt.Println(strings.Join(b[j], " "))
		}
	}
}

Java solution:
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt();
            if (n == 0) break;
            scanner.nextLine(); // consume the newline after n
            
            String[][] original = new String[n][n];
            for (int i = 0; i < n; i++) {
                String line = scanner.nextLine().trim();
                String[] parts = line.split("\\s+");
                for (int j = 0; j < n; j++) {
                    original[i][j] = parts[j];
                }
            }
            
            String[][] rearranged = new String[n][n];
            for (int i = 0; i < n; i++) {
                int index = 0;
                // First add even columns (1-based, so 1, 3, etc. which are 0, 2 in 0-based)
                for (int j = 1; j < n; j += 2) {
                    rearranged[i][index++] = original[i][j];
                }
                // Then add odd columns (0, 2, etc. in 0-based)
                for (int j = 0; j < n; j += 2) {
                    rearranged[i][index++] = original[i][j];
                }
            }
            
            // Print rows in the order: odd rows (1-based) first, then even
            for (int i = 1; i < n; i += 2) {
                System.out.println(String.join(" ", rearranged[i]));
            }
            for (int i = 0; i < n; i += 2) {
                System.out.println(String.join(" ", rearranged[i]));
            }
        }
        scanner.close();
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];
let currentLine = 0;

rl.on('line', (line) => {
    if (line.trim() === '0') {
        rl.close();
    } else {
        inputLines.push(line.trim());
    }
});

rl.on('close', () => {
    processInput();
});

function processInput() {
    let idx = 0;
    while (idx < inputLines.length) {
        const n = parseInt(inputLines[idx], 10);
        if (isNaN(n)) {
            idx++;
            continue;
        }
        idx++;
        const matrix = [];
        for (let i = 0; i < n && idx < inputLines.length; i++) {
            const row = inputLines[idx].split(/\s+/);
            matrix.push(row);
            idx++;
        }
        
        const b = [];
        for (let j = 0; j < n; j++) {
            const l = [];
            for (let i = 1; i < n; i += 2) {
                l.push(matrix[j][i]);
            }
            for (let i = 0; i < n; i += 2) {
                l.push(matrix[j][i]);
            }
            b.push(l);
        }
        
        const output = [];
        for (let j = 1; j < n; j += 2) {
            output.push(b[j].join(' '));
        }
        for (let j = 0; j < n; j += 2) {
            output.push(b[j].join(' '));
        }
        
        console.log(output.join('\n'));
    }
}

Python solution:
while 1:
    n = int(input())
    if n == 0:
        break 
    a = []
    b = []
    for i in range(n):
        a.append(list(map(str,input().split())))
    for j in range(n):
        l = []
        for i in range(1,n,2):
            l.append(a[j][i])
        b.append(l)
    for j in range(n):
        for i in range(0,n,2):
            b[j].append(a[j][i])
    for j in range(1,n,2):
        print(" ".join(b[j]))
    for j in range(0,n,2):
        print(" ".join(b[j]))

Ruby solution:
while true
  # Read n safely
  input = gets
  break if input.nil? || input.strip == '0'
  
  n = input.to_i
  next if n <= 0  # Skip invalid inputs

  # Read the current seating arrangement
  original = []
  n.times do
    row = gets
    original << row.strip.split
  end

  # Create the new arrangement by interleaving columns
  rearranged = []
  original.each do |row|
    # Take odd-indexed columns first (1-based), then even-indexed
    new_row = row.values_at(*(1...row.size).step(2)) + row.values_at(*(0...row.size).step(2))
    rearranged << new_row
  end

  # Reorder rows: odd-indexed first, then even-indexed
  output_rows = rearranged.values_at(*(1...n).step(2)) + rearranged.values_at(*(0...n).step(2))

  # Format the output
  output_rows.each do |row|
    puts row.join(' ')
  end
end