daily pastebin goal
65%
SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2.  
  3. class Gauss {
  4.     public static int gcd(int a, int b) {
  5.         while (b != 0) {
  6.             int tmp = a % b;
  7.             a = b;
  8.             b = tmp;
  9.         }
  10.         return a;
  11.     }
  12.  
  13.     public static void main(String[] args) {
  14.         Scanner s = new Scanner(System.in);
  15.         int n = s.nextInt();
  16.         int m = n;
  17.         int[][] A_num_arr = new int[n][n];
  18.         int[][] A_den_arr = new int[n][n];
  19.         int[] b_num_arr = new int[n];
  20.         int[] b_den_arr = new int[n];
  21.         for (int i = 0; i < n; i++) {
  22.             for (int j = 0; j < m; j++) {
  23.                 A_num_arr[i][j] = s.nextInt();
  24.                 A_den_arr[i][j] = 1;
  25.             }
  26.             b_num_arr[i] = s.nextInt();
  27.             b_den_arr[i] = 1;
  28.         }
  29.  
  30.         int N = n;
  31.         for (int p = 0; p < N; p++) {
  32.  
  33.             int max = p;
  34.             for (int i = p + 1; i < N; i++) {
  35.                 if (Math.abs((double) A_num_arr[i][p] / A_den_arr[i][p]) > Math.abs((double) A_num_arr[max][p] / A_den_arr[max][p])) {
  36.                     max = i;
  37.                 }
  38.             }
  39.             int[] temp1 = A_num_arr[p];
  40.             A_num_arr[p] = A_num_arr[max];
  41.             A_num_arr[max] = temp1;
  42.             int[] temp2 = A_den_arr[p];
  43.             A_den_arr[p] = A_den_arr[max];
  44.             A_den_arr[max] = temp2;
  45.             int t1 = b_num_arr[p];
  46.             b_num_arr[p] = b_num_arr[max];
  47.             b_num_arr[max] = t1;
  48.             int t2 = b_den_arr[p];
  49.             b_den_arr[p] = b_den_arr[max];
  50.             b_den_arr[max] = t2;
  51.  
  52.             if (Math.abs((double) A_num_arr[p][p] / A_den_arr[p][p]) <= 1e-10) {
  53.                 System.out.println("No solution");
  54.                 return;
  55.             }
  56.  
  57.             for (int i = p + 1; i < N; i++) {
  58.                 int r_num = A_num_arr[i][p] * A_den_arr[p][p];
  59.                 int r_den = A_den_arr[i][p] * A_num_arr[p][p];
  60.                 b_num_arr[i] = b_num_arr[i] * r_den * b_den_arr[p] - b_den_arr[i] * r_num * b_num_arr[p];
  61.                 b_den_arr[i] = b_den_arr[i] * r_den * b_den_arr[p];
  62.                 int gcd = gcd(b_num_arr[i], b_den_arr[i]);
  63.                 b_num_arr[i] = b_num_arr[i] / gcd;
  64.                 b_den_arr[i] = b_den_arr[i] / gcd;
  65.                 for (int j = p; j < N; j++) {
  66.                     A_num_arr[i][j] = A_num_arr[i][j] * r_den * A_den_arr[p][j] - A_den_arr[i][j] * r_num * A_num_arr[p][j];
  67.                     A_den_arr[i][j] = A_den_arr[i][j] * r_den * A_den_arr[p][j];
  68.                     gcd = gcd(A_num_arr[i][j], A_den_arr[i][j]);
  69.                     A_num_arr[i][j] = A_num_arr[i][j] / gcd;
  70.                     A_den_arr[i][j] = A_den_arr[i][j] / gcd;
  71.                 }
  72.             }
  73.         }
  74.  
  75.         int[] x_num = new int[N];
  76.         int[] x_den = new int[N];
  77.         for (int i = N - 1; i >= 0; i--) {
  78.             int sum_num = 0;
  79.             int sum_den = 1;
  80.             for (int j = i + 1; j < N; j++) {
  81.                 sum_num = sum_num * A_den_arr[i][j] * x_den[j] + sum_den * A_num_arr[i][j] * x_num[j];
  82.                 sum_den = sum_den * A_den_arr[i][j] * x_den[j];
  83.                 int gcd = gcd(sum_num, sum_den);
  84.                 sum_num = sum_num / gcd;
  85.                 sum_den = sum_den / gcd;
  86.             }
  87.             x_num[i] = (b_num_arr[i] * sum_den - sum_num * b_den_arr[i]) * A_den_arr[i][i];
  88.             x_den[i] = b_den_arr[i] * sum_den * A_num_arr[i][i];
  89.             int gcd = gcd(x_num[i], x_den[i]);
  90.             x_num[i] = x_num[i] / gcd;
  91.             x_den[i] = x_den[i] / gcd;
  92.         }
  93.  
  94.         for (int i = 0; i < N; i++) {
  95.             if (x_den[i] < 0) {
  96.                 x_den[i] = x_den[i] * (-1);
  97.                 x_num[i] = x_num[i] * (-1);
  98.             }
  99.             System.out.println(x_num[i] + "/" + x_den[i]);
  100.         }
  101.     }
  102. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top