Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán cho CNTT] Quy tắc dấu Descartes

    Cho đa thức hệ số thực P(x)P(x)P(x) (hệ số theo bậc giảm dần). Theo quy tắc dấu Descartes:

    • Số nghiệm thực dương (kể cả bội) không vượt quá số lần đổi dấu trong dãy hệ số của P(x)P(x)P(x) (bỏ qua hệ số 0), và sai khác với số đó một số chẵn.
    • Số nghiệm thực âm tối đa bằng số lần đổi dấu trong dãy hệ số của P(−x)P(-x)P(−x).

    Hãy in cận trên số nghiệm dương và cận trên số nghiệm âm (tức là hai số đổi dấu nói trên).

    Ví dụ: P(x)=x3−x2−x+1P(x) = x^3 - x^2 - x + 1P(x)=x3−x2−x+1: dãy dấu +,−,−,++,-,-,++,−,−,+ đổi dấu 2 lần → tối đa 2 nghiệm dương. Với P(−x)=−x3−x2+x+1P(-x) = -x^3 - x^2 + x + 1P(−x)=−x3−x2+x+1: dãy −,−,+,+-,-,+,+−,−,+,+ đổi 1 lần → tối đa 1 nghiệm âm.

    • Định dạng đầu vào:

      Dòng 1: nnn. Dòng 2: n+1n+1n+1 hệ số theo bậc giảm dần.

    • Ràng buộc đầu vào:

      1≤n≤301 \le n \le 301≤n≤30; ∣ai∣≤104|a_i| \le 10^4∣ai​∣≤104; an≠0a_n \ne 0an​=0.

    • Định dạng đầu ra:

      Hai số nguyên: cận trên số nghiệm dương và cận trên số nghiệm âm.

    Ví dụ:

    Đầu vào:

    3
1 -1 -1 1

    Đầu ra:

    2 1

    Giải thích:

    P(x) đổi dấu 2 lần (dương<=2); P(-x) đổi dấu 1 lần (âm<=1).

    Đang tải editor...