#!/usr/bin/env python3 from fractions import Fraction import math def main(): # lze přepínat mezi Gaussovou a Gaussovou-Jordanovou eliminací method = GaussianElimination # method = GaussJordanElimination rows = parse_input() method.elimination(rows) if not has_solution(rows): print("N") elif is_regular(rows): print("J") print(*method.find_regular_solution(rows)) else: print("P") for row in method.find_parametric_solution(rows): print(*row) def parse_input(): """Načte vstupní data. Vrátí seznam řádků. Na každém řádku jsou koeficienty neznámých a pravá strana. """ d = int(input()) rows = [] for _ in range(d): row = list(map(int, input().split())) rows.append(row) return rows class GaussianElimination: @staticmethod def elimination(rows): """Provede Gaussovu eliminaci. Upraví řádky v `rows` tak, aby v levé spodní části byly nuly. """ # i je index prvního řádku, který můžeme upravovat # j je index aktuálního sloupce d = len(rows) i = 0 for j in range(d): best_i = find_optimal_row(rows, i, j) if best_i is None: # přeskoč daný sloupec a pokračuj se stejným i continue swap_rows(rows, i, best_i) # vynuluj prvky for k in range(i + 1, d): rows[k] = eliminated_row(rows[k], rows[i], j) i += 1 @staticmethod def find_regular_solution(rows): """Spočítá jednoznačné řešení.""" d = len(rows) solution = [None for _ in range(d)] for i in reversed(range(d)): row = rows[i] x = Fraction(row[-1]) # převedeme již spočítané neznámé na pravou stranu for j in range(i + 1, d): x -= row[j] * solution[j] solution[i] = x / row[i] return solution @staticmethod def find_parametric_solution(rows): """Spočítá parametrické řešení. Vrátí jej ve vektorovém zápisu. """ # interně pracuje s rovnicovým zápisem, nikoli vektorovým # každý seznam popisuje jednu neznámou # prvních d prvků udává koeficienty parametrů, poslední prvek konstantní hodnotu d = len(rows) def zero_vec(): return [Fraction(0) for _ in range(d + 1)] solution = [None for _ in range(d)] j = d - 1 # index právě počítané neznámé for i in reversed(range(d)): row = rows[i] first_unknown = first_not_equal(row, 0) # index první neznámé na řádku if first_unknown == None: continue while first_unknown < j: # zavedení nového parametru solution[j] = zero_vec() solution[j][j] = Fraction(1) j -= 1 # spočítání hodnoty neznámé x = zero_vec() x[-1] = Fraction(row[-1]) # stejně jako ve find_regular_solution for k in range(j + 1, d): x = vec_sub(x, vec_mul(solution[k], row[k])) solution[j] = vec_div(x, row[first_unknown]) j -= 1 return convert_solution_to_vector_form(solution) class GaussJordanElimination: @staticmethod def elimination(rows): """Provede Gaussovu-Jordanovu eliminaci. """ # i je index prvního řádku, který můžeme upravovat # j je index aktuálního sloupce d = len(rows) i = 0 for j in range(d): best_i = find_optimal_row(rows, i, j) if best_i is None: # přeskoč daný sloupec a pokračuj se stejným i continue swap_rows(rows, i, best_i) # vynuluj prvky nad i pod aktuálním řádkem for k in range(d): if k != i: rows[k] = eliminated_row(rows[k], rows[i], j) i += 1 @staticmethod def find_regular_solution(rows): """Spočítá jednoznačné řešení.""" d = len(rows) solution = [None for _ in range(d)] for i in reversed(range(d)): row = rows[i] solution[i] = Fraction(row[-1], row[i]) return solution @staticmethod def find_parametric_solution(rows): """Spočítá parametrické řešení. Vrátí jej ve vektorovém zápisu. """ d = len(rows) solution_constants = [0 for _ in range(d)] solution_parameters = [[0 for _ in range(d)] for _ in range(d)] # indexy prvních neznámých na řádku first_unknown_indexes = [first_not_equal(row, 0) for row in rows] j = d - 1 # index právě počítané neznámé for i in reversed(range(d)): row = rows[i] first_unknown_index = first_unknown_indexes[i] if first_unknown_index == None: continue while first_unknown_index < j: # zavedení nového parametru solution_parameters[j][j] = 1 for k in range(i+1): param = first_unknown_indexes[k] param_coef = rows[k][param] solution_parameters[j][param] = -Fraction(rows[k][j], param_coef) j -= 1 # neznámá # stejně jako ve find_regular_solution solution_constants[j] = Fraction(row[-1], row[j]) j -= 1 return [solution_constants] + solution_parameters # * pomocné funkce def find_optimal_row(rows, i_begin, j): """Najde řádek, který je nejvhodnější pro výměnu s řádkem `i_begin`. Hledá řádek, jehož prvek ve sloupci `j` je nenulový a má nejmenší absolutní hodnotu. Prochází pouze řádky `i_begin` a níže. Vrátí index řádku nebo `None`, pokud jsou všechny prvky nulové. """ best_i = None for i in range(i_begin, len(rows)): el = rows[i][j] if el == 0: continue if best_i is None or abs(el) < abs(rows[best_i][j]): best_i = i return best_i def eliminated_row(row_k, row_i, j): """Vrátí řádek `row_k` po vynulování prvku ve sloupci `j`. Vynulování se provede odečtením řádku `row_i`. """ el_i = row_i[j] el_k = row_k[j] if el_k == 0: return row_k # vynásob oba řádky tak, aby se odpovídající prvky rovnaly el_target = lcm(abs(el_i), abs(el_k)) row_i = vec_mul(row_i, el_target // el_i) row_k = vec_mul(row_k, el_target // el_k) return vec_sub(row_k, row_i) def convert_solution_to_vector_form(solution): """Převede řešení z rovnicového do vektorového zápisu. """ vector_form = [] # konstanty nezávislé na parametrech constants = [unknown[-1] for unknown in solution] vector_form.append(constants) # parametry for i in range(len(solution)): coefficients = [unknown[i] for unknown in solution] vector_form.append(coefficients) return vector_form def is_regular(rows): """Zjistí, jestli má soustava jednoznačné řešení.""" # součástí řádku je i pravá strana, proto -2 return rows[-1][-2] != 0 def has_solution(rows): """Zjistí, jestli má soustava alespoň jedno řešení.""" if is_regular(rows): return True return rows[-1][-1] == 0 def swap_rows(rows, i1, i2): rows[i1], rows[i2] = rows[i2], rows[i1] def vec_sub(x, y): """Odečte dva vektory.""" assert len(x) == len(y) return [x[i] - y[i] for i in range(len(x))] def vec_mul(x, a): """Vynásobí vektor skalárem.""" return [x[i] * a for i in range(len(x))] def vec_div(x, a): """Vydělí vektor skalárem.""" return [x[i] / a for i in range(len(x))] def lcm(a, b): """Spočítá nejmenší společný násobek.""" return a * b // math.gcd(a, b) def first_not_equal(x, a): """Vrátí index prvního prvku, který se nerovná `a`.""" for i in range(len(x)): if x[i] != a: return i return None if __name__ == "__main__": main()