#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

// Function to evaluate polynomial at x
double evaluatePolynomial(const vector<double>& coeffs, double x) {
    double result = 0;
    int degree = coeffs.size() - 1;
    for (int i = 0; i <= degree; ++i) {
        result += coeffs[i] * pow(x, degree - i);
    }
    return result;
}

// Function to evaluate derivative of polynomial at x
double evaluateDerivative(const vector<double>& coeffs, double x) {
    double result = 0;
    int degree = coeffs.size() - 1;
    for (int i = 0; i < degree; ++i) {
        result += coeffs[i] * (degree - i) * pow(x, degree - i - 1);
    }
    return result;
}

// Synthetic division to deflate polynomial
vector<double> syntheticDivision(const vector<double>& coeffs, double root) {
    int n = coeffs.size();
    vector<double> newCoeffs(n - 1);
    newCoeffs[0] = coeffs[0];
    for (int i = 1; i < n - 1; ++i) {
        newCoeffs[i] = coeffs[i] + newCoeffs[i - 1] * root;
    }
    return newCoeffs;
}

int main() {
    int degree;
    cout << "Enter the degree of the polynomial: ";
    cin >> degree;

    vector<double> coeffs(degree + 1);
    cout << "Enter the coefficients of the polynomial (from highest to lowest degree):\n";
    for (int i = 0; i <= degree; ++i) {
        cin >> coeffs[i];
    }

    double x0, E;
    cout << "Enter the initial guess (x0): ";
    cin >> x0;
    cout << "Enter the error tolerance (E): ";
    cin >> E;

    vector<double> currentCoeffs = coeffs;
    for (int n = degree; n > 1; --n) {
        double f_x0 = evaluatePolynomial(currentCoeffs, x0);
        double f_prime_x0 = evaluateDerivative(currentCoeffs, x0);
        double x1 = x0 - f_x0 / f_prime_x0;

        cout << fixed << setprecision(6);
        cout << "Iteration " << degree - n + 1 << ":\n";
        cout << "x0 = " << x0 << ", x1 = " << x1 << endl;

        if (fabs(x1 - x0) < E) {
            cout << "Root: " << x1 << endl;
            break;
        }

        currentCoeffs = syntheticDivision(currentCoeffs, x1);
        x0 = x1;
    }

    if (currentCoeffs.size() == 2) {
        double root = -currentCoeffs[0] / currentCoeffs[1];
        cout << "Final root: " << root << endl;
    }

    return 0;
}