#include <iostream>
#include <cmath>
#include <vector>
#include <string>

using namespace std;

//Opción 1: Calculo recursivo de e^x
double potencia(double x, int n) {
    if (n == 0) return 1;
    return x * potencia(x, n - 1);
}

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

double calcularExponencial(double x, int profundidad) {
    if (profundidad == 0) return 1;
    return potencia(x, profundidad) / factorial(profundidad) + calcularExponencial(x, profundidad - 1);
}

//Opción 2: Ordenar coches por potencia y marca
struct coche {
    string marca;
    string matricula;
    int potencia;
    int anio_matriculacion;
};

bool comparar(const coche& a, const coche& b) {
    if (a.potencia != b.potencia)
        return a.potencia < b.potencia;
    return a.marca < b.marca;
}

void merge(vector<coche>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<coche> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (comparar(L[i], R[j])) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(vector<coche>& arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

//Opción 3: Algoritmo de las 8 Reinas
const int N = 8;
int tablero[N];

bool esValido(int fila, int col) {
    for (int i = 0; i < fila; i++) {
        if (tablero[i] == col || abs(tablero[i] - col) == abs(i - fila))
            return false;
    }
    return true;
}

void resolver8Reinas(int fila) {
    if (fila == N) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout << (tablero[i] == j ? "Q " : ". ");
            }
            cout << endl;
        }
        cout << "------------------\n";
        return;
    }

    for (int col = 0; col < N; col++) {
        if (esValido(fila, col)) {
            tablero[fila] = col;
            resolver8Reinas(fila + 1);
        }
    }
}


int main() {
    int opcion;

    do {
        cout << "\n      MENU PRINCIPAL \n";
        cout << "1. Calculo recursivo de e^x\n";
        cout << "2. Ordenar coches por potencia y marca\n";
        cout << "3. Algoritmo de las 8 Reinas\n";
        cout << "4. Salir\n";
        cout << "Selecciona una opcion: ";
        cin >> opcion;

        if (opcion == 1) {
            double x;
            int profundidad;
            cout << "Introduce el valor de x: ";
            cin >> x;
            cout << "Introduce el limite de profundidad: ";
            cin >> profundidad;
            double resultado = calcularExponencial(x, profundidad);
            cout << "Resultado de e^" << x << " = " << resultado << endl;
        }

        else if (opcion == 2) {
            vector<coche> coches = {
                {"Volkswagen", "1234ABC", 110, 2018},
                {"Ford", "5678DEF", 130, 2016},
                {"Toyota", "4321ZYX", 110, 2020},
                {"Audi", "9876GHI", 150, 2019},
                {"BMW", "2468JKL", 130, 2017}
            };

            mergeSort(coches, 0, coches.size() - 1);

            cout << "\nCoches ordenados por potencia y marca:\n";
            for (const auto& c : coches) {
                cout << "Marca: " << c.marca
                     << ", Matricula: " << c.matricula
                     << ", Potencia: " << c.potencia
                     << ", Anio: " << c.anio_matriculacion << endl;
            }
        }

        else if (opcion == 3) {
            cout << "\nSoluciones para el problema de las 8 Reinas:\n";
            resolver8Reinas(0);
        }

    } while (opcion != 4);

    return 0;
}