canuc80k6301·2/32

Ba Trạng Thái Của Hệ

Nộp bài trên LQDOJ

Bài 63 · Gaussian Elimination

Cho hệ phương trình tuyến tính theo ẩn thực. Bạn phải xác định chính xác hệ thuộc một trong ba trường hợp: vô nghiệm, có vô số nghiệm, hoặc có nghiệm duy nhất. Trong trường hợp cuối, hãy tìm toàn bộ nghiệm.

Input

  • Dòng đầu chứa số nguyên .
  • Mỗi dòng trong dòng tiếp theo chứa số nguyên. số đầu là hệ số của ; số cuối là hằng số ở vế phải.

Output

  • Nếu hệ vô nghiệm, in .
  • Nếu hệ có vô số nghiệm, in .
  • Nếu hệ có nghiệm duy nhất, với mỗi in một dòng theo dạng , trong đó giá trị có đúng hai chữ số sau dấu chấm. Giá trị làm tròn thành phải được in là .

Constraints

  • .
  • .
  • .

Scoring

  • Subtask ( số điểm): .
  • Subtask ( số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

2
1 1 5
2 -1 1

Output

x1=2.00
x2=3.00

Giải thích: Hai phương trình độc lập nên hệ có nghiệm duy nhất; giải chúng cho và , vì thế không dùng hai mã kết quả hoặc .

Lời giải tóm tắt
  • Ý tưởng: Khử Gauss có chọn pivot và lưu số pivot thu được. Sau khi khử, một hàng có toàn bộ hệ số bằng không nhưng vế phải khác không chứng minh rank(A)<rank([A|b]), nên hệ vô nghiệm. Nếu không có hàng mâu thuẫn mà số pivot nhỏ hơn n, ít nhất một ẩn tự do tồn tại và hệ có vô số nghiệm. Chỉ khi đủ n pivot mới đọc được nghiệm duy nhất.
  • Ý tưởng: Thời gian O(n^3), bộ nhớ O(n^2).