THE SAMS' CONTEST

Problem 5

BACKGROUND

Moni is a brilliant student of BUET. After the last class of the current term (semester) he decided to watch the renowned film of the year 2003 "MATRIX RELOADED" that was displayed in the BUET AUDITORIUM. Yet he could not forget it. He became so much enthusiastic about the subject of Mathematics "Matrix" that he decided to make a computer version of every program of Matrix. As it is a huge subject he wants your help. Please write a program that calculates the inverse of a matrix.

Input

The input consists of several cases. Each case consists of a matrix. Consecutive cases are separated by a black line. Each element of the matrices given are separated from other members by spaces. The first line for each case is a number ,n, giving the order of the matrix. Input is terminated by a value of n=0.

Output

For each case your program should 1) if possible calculate the inverse of the matrix and print it with members of same row separated by a space and columns are printed in separate line 2) otherwise print a line Not possible . Print a black line after each test cases. I think you all know that a singular matrix has no inverse matrix. No pivoting is allowed. For output format see the sample output.

Sample Input

2
1 2
2 1

2
1 2
2 1

0

Sample Output

-0.333333 0.666667
0.666667 -0.333333

-0.333333 0.666667
0.666667 -0.333333

#include <stdio.h>
#include <math.h>
#define eps 1e-7
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        int m = 2*n, i, j, k, ch;
        double mx[n][m], tmp, c;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++)
                scanf("%lf", &mx[i][j]);
            for(j = n; j < m; j++)
                mx[i][j] = 0;
            mx[i][i+n] = 1;
        }
        for(i = 0; i < n; i++) {
            if(fabs(mx[i][i]) < eps)  break;
            for(j = 0; j < n; j++) {
                if(i == j)  continue;
                c = mx[j][i]/mx[i][i];
                for(k = i; k < m; k++)
                    mx[j][k] = mx[j][k] - mx[i][k]*c;
            }
        }
        if(i != n) {
            puts("Not possible\n");
            continue;
        }
        for(i = 0; i < n; i++, puts("")) {
            for(j = n; j < m; j++) {
                if(j != n)  putchar(' ');
                printf("%.6lf", mx[i][j]/mx[i][i]);
            }
        }
        puts("");
    }
    return 0;
}