NC15532 Carrera Feliz

Resumen del Problema

Se pregunta la probabilidad de que al finalizar una carrera en una pista circular de longitud x (en sentido horario), un corredor haya cubierto una distancia de k metros o más. Hay dos puntos de control aleatorios. El corredor debe pasar primero por el punto de control 1 y luego por el punto de control 2. Si llega al punto 2 antes que al punto 1, debe completar una vuelta para pasar por el punto 1 y luego continuar hasta el punto 2 para registrarse.

Enfoque de la Solución

Este problema de probabilidad se resuelve analizando los casos según la relación entre la distancia k y la longitud de la pista x. Se asume que las posiciones de los dos puntos de control se eligen uniformemente al azar en la pista. La distancia total recorrida dependerá de las posiciones relativas de los puntos de control y el orden en que se visitan.

• Si k ≤ x (la distancia objetivo es menor o igual a una vuelta): Hay dos casos con probabilidad 0.5 cada uno: el punto de control 1 está antes que el punto 2, o viceversa. Si el punto 1 está antes del 2, la distancia mínima es P2 - P1. Si el punto 2 está antes del 1, la distancia mínima es x - P1 + P2 (una vuelta). Si la distancia P2 - P1 es menor que k, el corredor tendría que dar una vuelta extra, lo que siempre superaría k. La fórmula en el código maneja estos escenarios de manera compacta.
• Si x < k ≤ 2x (la distancia objetivo está entre una y dos vueltas): En este caso, la distancia siempre será P2 - P1 si P1 < P2, o x - P1 + P2 + x si P2 < P1. La fórmula provista calcula la probabilidad directamente para este rango.
• Si k > 2x (la distancia objetivo es mayor que dos vueltas): Es imposible alcanzar esta distancia, por lo que la probabilidad es 0.

La solución se basa en fórmulas matemáticas específicas que representan las áreas de éxito en un espacio de probabilidad bidimensional (posiciones de P1 y P2 en [0, x) x [0, x)).

Código de Ejemplo

#include <iostream>
#include <iomanip> // Para setprecision

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int numCasos;
    std::cin >> numCasos;

    while (numCasos--) {
        double distanciaObjetivo, longitudPista;
        std::cin >> distanciaObjetivo >> longitudPista;

        double probabilidadFinal = 0.0;

        if (distanciaObjetivo <= longitudPista) {
            // Caso 1: La distancia objetivo es menor o igual a la longitud de la pista.
            // Si el punto 1 está después del punto 2 (prob. 0.5), la distancia recorrida será (longitudPista - P1 + P2).
            // Esta distancia siempre será >= longitudPista, y por lo tanto >= distanciaObjetivo.
            // Entonces, en este 50% de los casos, la condición se cumple.
            probabilidadFinal = 0.5;

            // Para el otro 50% (punto 1 antes del punto 2), la distancia recorrida es (P2 - P1).
            // Necesitamos que (P2 - P1) >= distanciaObjetivo.
            // La siguiente fórmula calcula la probabilidad de este subcaso y se suma.
            probabilidadFinal += (longitudPista - distanciaObjetivo) / longitudPista *
                                 (longitudPista + distanciaObjetivo) / (2.0 * longitudPista);

        } else if (distanciaObjetivo <= 2.0 * longitudPista) {
            // Caso 2: La distancia objetivo está entre una y dos veces la longitud de la pista.
            // La fórmula es más compleja y se deriva de la geometría del problema.
            probabilidadFinal = (2.0 * longitudPista - distanciaObjetivo) / longitudPista *
                                (2.0 * longitudPista - distanciaObjetivo) / (2.0 * longitudPista);
        }
        // Si distanciaObjetivo > 2 * longitudPista, probabilidadFinal permanece en 0.0, lo cual es correcto.

        std::cout << std::fixed << std::setprecision(2) << probabilidadFinal << std::endl;
    }
    return 0;
}

POJ2096 Recolectando Errores

Resumen del Problema

Se tienen N categorías de errores por ubicación y M categorías por tipo. Cada día se encuentra un error. Se pregunta el número esperado de días para encontrar al menos un error de cada una de las N ubicaciones y M tipos.

Enfoque de la Solución

Este es un problema clásico de Programación Dinámica Probabilística (DP). Definimos E[i][j] como el número esperado de días restantes para encontrar todos los errores, dado que ya hemos encontrado i ubicaciones únicas y j tipos únicos de errores. Nuestro objetivo es calcular E[0][0].

Las transiciones de estado se basan en el error que se encuentra al día sigueinte:

• Ya se encontró la ubicación (i de N) y el tipo (j de M): probabilidad (i/N) * (j/M). El estado no cambia: E[i][j].
• Ya se encontró la ubicación (i de N), pero el tipo es nuevo (j de M): probabilidad (i/N) * (1 - j/M). El estado cambia a E[i][j+1].
• La ubicación es nueva (i de N), pero ya se encontró el tipo (j de M): probabilidad (1 - i/N) * (j/M). El estado cambia a E[i+1][j].
• La ubicación es nueva (i de N) y el tipo es nuevo (j de M): probabilidad (1 - i/N) * (1 - j/M). El estado cambia a E[i+1][j+1].

La ecuación de recurrencia es:

E[i][j] = 1 + P_viejo_viejo * E[i][j] + P_viejo_nuevo * E[i][j+1] + P_nuevo_viejo * E[i+1][j] + P_nuevo_nuevo * E[i+1][j+1]

Donde 1 representa el día actual. Reorganizando la ecuación para despejar E[i][j]:

E[i][j] * (1 - P_viejo_viejo) = 1 + P_viejo_nuevo * E[i][j+1] + P_nuevo_viejo * E[i+1][j] + P_nuevo_nuevo * E[i+1][j+1]

E[i][j] = (1 + P_viejo_nuevo * E[i][j+1] + P_nuevo_viejo * E[i+1][j] + P_nuevo_nuevo * E[i+1][j+1]) / (1 - P_viejo_viejo)

La base de la recursión es E[N][M] = 0 (ya se han encontrado todos los errores). Utilizaremos memoización para evitar recálculos.

Código de Ejemplo

#include <iostream>
#include <vector>
#include <iomanip> // Para setprecision

const int MAX_N_M = 1005; // Máximo número de ubicaciones o tipos
double memo[MAX_N_M][MAX_N_M];
bool visitado[MAX_N_M][MAX_N_M]; // Para controlar la memoización

int totalUbicaciones, totalTipos;

double calcularEsperanza(int ubicacionesHalladas, int tiposHallados) {
    // Si ya hemos alcanzado el objetivo, el valor esperado de días adicionales es 0.
    if (ubicacionesHalladas == totalUbicaciones && tiposHallados == totalTipos) {
        return 0.0;
    }
    // Si ya se ha calculado este estado, devolvemos el valor memoizado.
    if (visitado[ubicacionesHalladas][tiposHallados]) {
        return memo[ubicacionesHalladas][tiposHallados];
    }

    // Un día pasa en cada paso.
    double esperanzaActual = 1.0;

    // Calcular probabilidades de encontrar el siguiente error:
    double probUbicacionExistente = (double)ubicacionesHalladas / totalUbicaciones;
    double probTipoExistente = (double)tiposHallados / totalTipos;

    // Caso 1: La ubicación y el tipo del error ya se han encontrado.
    // P(ubicación existente, tipo existente)
    double pExistenteExistente = probUbicacionExistente * probTipoExistente;
    esperanzaActual += pExistenteExistente * calcularEsperanza(ubicacionesHalladas, tiposHallados); // Estado no cambia

    // Caso 2: La ubicación existe, pero el tipo es nuevo.
    // P(ubicación existente, tipo nuevo)
    double pExistenteNuevo = probUbicacionExistente * (1.0 - probTipoExistente);
    esperanzaActual += pExistenteNuevo * calcularEsperanza(ubicacionesHalladas, tiposHallados + 1); // Estado cambia a (x, y+1)

    // Caso 3: La ubicación es nueva, pero el tipo existe.
    // P(ubicación nueva, tipo existente)
    double pNuevoExistente = (1.0 - probUbicacionExistente) * probTipoExistente;
    esperanzaActual += pNuevoExistente * calcularEsperanza(ubicacionesHalladas + 1, tiposHallados); // Estado cambia a (x+1, y)

    // Caso 4: La ubicación y el tipo son nuevos.
    // P(ubicación nueva, tipo nuevo)
    double pNuevoNuevo = (1.0 - probUbicacionExistente) * (1.0 - probTipoExistente);
    esperanzaActual += pNuevoNuevo * calcularEsperanza(ubicacionesHalladas + 1, tiposHallados + 1); // Estado cambia a (x+1, y+1)

    // La ecuación original es E[x][y] = 1 + P1*E[x][y] + P2*E[x][y+1] + P3*E[x+1][y] + P4*E[x+1][y+1]
    // Despejando E[x][y]: E[x][y] * (1 - P1) = 1 + P2*E[x][y+1] + P3*E[x+1][y] + P4*E[x+1][y+1]
    // E[x][y] = (1 + P2*E[x][y+1] + P3*E[x+1][y] + P4*E[x+1][y+1]) / (1 - P1)
    // Mi esperanzaActual ya suma los términos 1, P2*E[...], P3*E[...], P4*E[...].
    // Solo necesito dividir por (1 - P1)
    
    // Marcar como visitado y almacenar el resultado.
    visitado[ubicacionesHalladas][tiposHallados] = true;
    return memo[ubicacionesHalladas][tiposHallados] = esperanzaActual / (1.0 - pExistenteExistente);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> totalUbicaciones >> totalTipos;

    // Inicializar la tabla de memoización y el array de visitados.
    // memset(memo, 0, sizeof(memo)); // Se puede usar si se garantiza que E[i][j] nunca será 0 para estados no objetivo.
    // Para mayor robustez, se recomienda inicializar con un valor que no sea un resultado válido, ej. -1, y usar un array 'visitado'.

    std::cout << std::fixed << std::setprecision(4) << calcularEsperanza(0, 0) << std::endl;

    return 0;
}

NC210477 El Magnate del Juego

Resumen del Problema

Un jugador avanza en un tablero con N posiciones, cada una con un puntaje asociado. El jugador comienza en la posición 1. Se lanza un dado de 6 caras, y si sale x, el jugador avanza x pasos desde la posición actual i a i+x. Si i+x excede N, el dado se vuelve a lanzar hasta obtener un resultado válido. El juego termina al llegar a la posición N. Se busca el puntaje esperado total.

Enfoque de la Solución

Este problema de valor esperado se modela con Programación Dinámica. Definimos E[pos] como el puntaje esperado que se obtendrá desde la posición pos hasta el final del juego. El objetivo es calcular E[1].

La base de la recursión es E[N] = puntajes[N], ya que al llegar a la posición N, el juego termina y solo se obtiene el puntaje de esa posición.

Para cualquier otra posición pos < N, el jugador lanza un dado. Las posibles tiradas son 1, 2, 3, 4, 5, 6. Sin embargo, si una tirada x llevaría al jugador a una posición pos + x > N, esa tirada se ignora y el dado se vuelve a lanzar. Esto significa que solo las tiradas que llevan a pos + x ≤ N son válidas.

Sea C el número de tiradas válidas (es decir, min(N - pos, 6)). Cada una de estas tiradas tiene una probabilidad de 1/C. Por lo tanto, el valor esperado desde pos es:

E[pos] = puntajes[pos] + (1/C) * (E[pos+1] + E[pos+2] + ... + E[pos+C])

Utilizaremos memoización para almacenar los resultados de E[pos] y evitar recálculos.

Código de Ejemplo

#include <iostream>
#include <vector>
#include <numeric> // Para std::iota si se usa
#include <algorithm> // Para std::min
#include <iomanip> // Para std::fixed y std::setprecision

const int MAX_POSICIONES = 1000005; // n puede ser hasta 10^6
double puntajes[MAX_POSICIONES];
double memo[MAX_POSICIONES];
bool visitado[MAX_POSICIONES]; // Para control de memoización

int numPosiciones;

double obtenerPuntajeEsperado(int posicionActual) {
    // Si la posición actual excede el tablero, no hay más puntaje. (No debería ocurrir con la lógica de relanzar el dado)
    if (posicionActual > numPosiciones) {
        return 0.0;
    }
    // Caso base: Si estamos en la posición final, retornamos su puntaje.
    if (posicionActual == numPosiciones) {
        return puntajes[posicionActual];
    }
    // Si ya hemos calculado este estado, devolvemos el valor memoizado.
    if (visitado[posicionActual]) {
        return memo[posicionActual];
    }

    double sumaExpectativasSiguientes = 0.0;
    // El número de tiradas válidas del dado, no excediendo la posición final.
    int tiradasValidas = std::min(numPosiciones - posicionActual, 6);

    // Sumar el puntaje esperado de todas las posibles posiciones futuras válidas.
    for (int i = 1; i <= tiradasValidas; ++i) {
        sumaExpectativasSiguientes += obtenerPuntajeEsperado(posicionActual + i);
    }

    // El puntaje esperado es el puntaje de la posición actual más el promedio de las expectativas futuras.
    double resultado = puntajes[posicionActual] + (sumaExpectativasSiguientes / tiradasValidas);

    // Memoizar el resultado antes de retornarlo.
    visitado[posicionActual] = true;
    memo[posicionActual] = resultado;
    return resultado;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> numPosiciones;

    for (int i = 1; i <= numPosiciones; ++i) {
        std::cin >> puntajes[i];
    }

    // Inicializar el array de visitados a false (no visitado).
    // memset(visitado, false, sizeof(visitado)); // En C++, vector<bool> es especializado y no funciona con memset, o usar std::fill.
    // Para arrays normales como bool visitado[], memset sí funciona.

    std::cout << std::fixed << std::setprecision(8) << obtenerPuntajeEsperado(1) << std::endl;

    return 0;
}
</bool>

NC210481 Juego de Dados

Resumen del Problema

Se tienen tres dados con k1, k2, k3 caras respectivamente. El puntaje inicial es 0. En cada tirada, se obtienen x, y, z. Si (x,y,z) es igual a una combinación especial (a,b,c), el puntaje se reinicia a 0. De lo contrario, el puntaje se incrementa en x+y+z. Se desea saber el número esperado de tiradas para que el puntaje sea mayor que n.

Enfoque de la Solución

Sea E[s] el número esperado de tiradas adicionales para alcanzar un puntaje mayor que n, dado que el puntaje actual es s. Nuestro objetivo es encontrar E[0].

La ecuación de recurrencia para E[s] (donde s ≤ n) es:

E[s] = 1 + P_reset * E[0] + Σ (P_sum[k] * E[s+k])

Donde:

• 1 representa la tirada actual.
• P_reset es la probabilidad de que la tirada (x,y,z) sea (a,b,c), lo que reinicia el puntaje a 0. Esto es 1 / (k1 * k2 * k3).
• P_sum[k] es la probabilidad de que la suma de los dados sea k (y la combinación no sea (a,b,c)), llevando a un nuevo puntaje s+k. Si s+k > n, entonces E[s+k] = 0 (ya se alcanzó el objetivo).

Esta ecuación presenta un problema: E[0] aparece en el lado derecho. Para resolver esto, utilizamos una técnica de Programación Dinámica lineal. Definimos E[s] en la forma E[s] = A[s] * E[0] + B[s].

Sustituyendo esto en la ecuación de recurrencia:

A[s] * E[0] + B[s] = 1 + P_reset * E[0] + Σ (P_sum[k] * (A[s+k] * E[0] + B[s+k]))

Reorganizando para agrupar términos con E[0]:

A[s] * E[0] + B[s] = E[0] * (P_reset + Σ (P_sum[k] * A[s+k])) + (1 + Σ (P_sum[k] * B[s+k]))

Esto nos da las siguientes recurrencias para A[s] y B[s]:

• A[s] = P_reset + Σ (P_sum[k] * A[s+k])
• B[s] = 1 + Σ (P_sum[k] * B[s+k])

Calculamos P_sum[k] para todas las posibles sumas k. Luego, calculamos A[s] y B[s] en orden descendente, desde s=n hasta s=0. Para s > n, A[s] = 0 y B[s] = 0.

Finalmente, cuando tenemos A[0] y B[0], podemos resolver para E[0]:

E[0] = A[0] * E[0] + B[0]

E[0] * (1 - A[0]) = B[0]

E[0] = B[0] / (1 - A[0])

Código de Ejemplo

#include <iostream>
#include <vector>
#include <numeric>
#include <iomanip>
#include <algorithm> // Para std::min

// Maxima suma posible de los dados. Asumimos k1,k2,k3 son pequeños (ej. hasta 6)
// Si k1,k2,k3 fueran 6, 6, 6, la suma máxima es 18. p[20] es suficiente.
// Si son mayores, este tamaño debe ajustarse.
const int MAX_SUMA_DADOS = 60; // Un tamaño más robusto si k1, k2, k3 pueden ser mayores (ej. hasta 20)
double probSuma[MAX_SUMA_DADOS];

const int MAX_PUNTUACION = 555; // n puede ser hasta 550
double coefA[MAX_PUNTUACION];
double coefB[MAX_PUNTUACION];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int puntuacionObjetivo;
    int carasDado1, carasDado2, carasDado3;
    int valA, valB, valC; // Valores de la combinación de reinicio

    std::cin >> puntuacionObjetivo >> carasDado1 >> carasDado2 >> carasDado3 >> valA >> valB >> valC;

    // Calcular P_reset: probabilidad de que la tirada sea (a,b,c) y reinicie el puntaje.
    // Esta es probSuma[0] en el código original, que es un poco confuso.
    // Usaremos un término separado para la probabilidad de reseteo.
    double probReinicio = 1.0 / (static_cast<double>(carasDado1) * carasDado2 * carasDado3);

    // Calcular probSuma[k]: probabilidad de que la suma de los dados sea 'k' (sin resetear el puntaje).
    // Suma mínima de 3 dados es 3, máxima es carasDado1 + carasDado2 + carasDado3.
    for (int sumaK = 3; sumaK <= carasDado1 + carasDado2 + carasDado3; ++sumaK) {
        int countCombinaciones = 0;
        for (int d1 = 1; d1 <= carasDado1; ++d1) {
            for (int d2 = 1; d2 <= carasDado2; ++d2) {
                int d3 = sumaK - d1 - d2;
                if (d3 >= 1 && d3 <= carasDado3) {
                    // Si esta combinación es la de reinicio, no la contamos para probSuma[k].
                    if (!(d1 == valA && d2 == valB && d3 == valC)) {
                        countCombinaciones++;
                    }
                }
            }
        }
        probSuma[sumaK] = static_cast<double>(countCombinaciones) / (static_cast<double>(carasDado1) * carasDado2 * carasDado3);
    }

    // Calcular coefA y coefB usando DP en orden descendente.
    // Para puntajes > puntuacionObjetivo, coefA y coefB son 0.
    for (int s = puntuacionObjetivo; s >= 0; --s) {
        for (int sumaK = 3; sumaK <= carasDado1 + carasDado2 + carasDado3; ++sumaK) {
            int siguientePuntaje = s + sumaK;
            // Si el siguiente puntaje excede el objetivo, E[siguientePuntaje] = 0, así que A y B para ese estado son 0.
            // Esto se maneja implícitamente porque coefA y coefB están inicializados a 0.
            // Para puntajes > puntuacionObjetivo, no contribuirán al sumatorio recursivo.
            if (siguientePuntaje > puntuacionObjetivo) {
                 // Si se supera el objetivo, A[siguientePuntaje] y B[siguientePuntaje] son efectivamente 0,
                 // por lo que no contribuyen al sumatorio.
                 // No necesitamos añadir nada aquí, ya que el default es 0.
            } else {
                coefA[s] += probSuma[sumaK] * coefA[siguientePuntaje];
                coefB[s] += probSuma[sumaK] * coefB[siguientePuntaje];
            }
        }
        // Añadir los términos para la probabilidad de reinicio y el +1 de la tirada actual.
        coefA[s] += probReinicio;
        coefB[s] += 1.0;
    }

    // Resolver E[0] = B[0] / (1 - A[0])
    double resultadoEsperado = coefB[0] / (1.0 - coefA[0]);

    std::cout << std::fixed << std::setprecision(10) << resultadoEsperado << std::endl;

    return 0;
}

NC210487 La Cafetería

Resumen del Problema

Una cola de N personas, con el jugador en la posición M. Cuando la primera persona en la cola llega a la ventanilla, pueden ocurrir cuatro cosas:

• p1: La persona espera (ventana vacía). La cola no cambia.
• p2: La persona olvida su tarjeta, va al final de la cola. La cola tiene N personas, el resto avanza.
• p3: La persona es atendida con éxito. La cola tiene N-1 personas.
• p4: La cafetería cierra. El juego termina.

Se pregunta la probabilidad de que la cafetería cierre mientras el jugador está en una de las primeras k posiciones de la cola.

Enfoque de la Solución

Este problema se aborda con Programación Dinámica. El estado dp[i][j] representará la probabilidad de que la cafetería cierre cuando la cola tiene i personas y el jugador está en la posición j, *y que además la posición j sea ≤ k*. El objetivo es caclular la suma de dp[longitudColaInicial][j] para j desde 1 hasta k.

Primero, normalizamos las probabilidades, ya que el caso p1 (espera) implica que el turno no avanza, lo que se puede ver como una "repetición" de la acción. Las probabilidades de los eventos "útiles" (no esperar) son:

• probOlvidaNorm = p2 / (1 - p1) (probabilidad de olvidar la tarjeta, dado que no esperamos)
• probExitoNorm = p3 / (1 - p1) (probabilidad de ser atendido, dado que no esperamos)
• probCierreNorm = p4 / (1 - p1) (probabilidad de que la cafetería cierre, dado que no esepramos)

La suma de probOlvidaNorm + probExitoNorm + probCierreNorm es 1.

Definimos también un array probOlvidarNVeces[x] como (probOlvidaNorm)^x, que representa la probabilidad de que las x personas que están al frente olviden su tarjeta consecutivamente. Esto será útil para el caso en que el jugador se mueve al final de la cola.

Las transiciones para dp[i][j]:

• **Calculando contribucionTransicion[j]:** Esta variable temporal acumula las probabilidades de cierre que no dependen del evento de que la persona de enfrente olvide su tarjeta.

  • Si el jugador está en una posición j ≤ k: contribucionTransicion[j] = dp[i-1][j-1] * probExitoNorm + probCierreNorm (la persona de enfrente fue atendida, el jugador avanza de j-1 a j, o la cafetería cierra ahora).
  • Si el jugador está en una posición j > k: contribucionTransicion[j] = dp[i-1][j-1] * probExitoNorm (la cafetería no puede cerrar "con contribución" si el jugador está fuera de las primeras k posiciones).

• **Calculando dp[i][i] (jugador en la última posición):** Cuando el jugador está en la última posición, esto significa que la persona de enfrente (en posición i-1) olvidó su tarjeta, y la de i-2 olvidó, etc., hasta que el jugador llega al final. Este es un caso de recurrencia lineal similar al problema de los dados. Se resuelve sumando las contribuciones de cada posible posición j donde el jugador podría haber estado antes de moverse al final, ponderadas por la probabilidad de que las (i-j) personas entre el jugador y el frente olviden su tarjeta. Es una sumatoria Σ (probOlvidarNVeces\[i-j\] \* contribucionTransicion\[j\]), todo dividido por (1 - probOlvidarNVeces\[i\]) (para manejar las recursiones de tipo E = A\*E + B).

• **Calculando dp[i][1] (jugador en la primera posición):** El jugador llega a la primera posición si la persona que estaba delante (en posición 1) olvidó su tarjeta (transición de dp[i][i], donde el jugador estaba en el final de la cola de tamaño i), o si la cafetería cierra directamente mientras el jugador está en la posición 1 (contribución probCierreNorm, si 1 ≤ k).

  dp[i][1] = dp[i][i] * probOlvidaNorm + (1 <= k ? probCierreNorm : 0.0)

• **Calculando dp[i][j] para 1 < j < i (jugador en posiciones intermedias):** El jugador está en la posición j. Esto ocurre si la persona en j-1 olvidó su tarjeta y el jugador avanzó de j-1 a j (dp[i][j-1] * probOlvidaNorm), o si la transición fue desde contribucionTransicion[j] (alguien fue servido o cerró la cafetería).

  dp[i][j] = dp[i][j-1] * probOlvidaNorm + contribucionTransicion[j]

La solución se construye iterando sobre la longitud de la cola i y luego sobre la posición del jugador j.

Código de Ejemplo

#include <iostream>
#include <vector>
#include <iomanip> // Para setprecision
#include <numeric> // Para std::iota, no usado directamente
#include <algorithm> // Para std::min/max

const int MAX_PERSONAS = 2010;
double probCierrePosicion[MAX_PERSONAS][MAX_PERSONAS]; // dp[i][j]: prob de cierre con 'i' personas y jugador en 'j'
double contribucionTransicion[MAX_PERSONAS]; // c[j]: contribución que no depende de que el de enfrente olvide su tarjeta
double probOlvidarNVeces[MAX_PERSONAS]; // p[x]: (probOlvidaNorm)^x

const double EPS = 1e-10; // Para comparar doubles con 0

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int longitudColaInicial, posicionJugadorInicial, limitePrimerasPosiciones;
    double pEspera, pOlvidaTarjeta, pExito, pCierre; // Probabilidades originales

    std::cin >> longitudColaInicial >> posicionJugadorInicial >> limitePrimerasPosiciones >> pEspera >> pOlvidaTarjeta >> pExito >> pCierre;

    // Si la probabilidad de cierre es insignificante, la respuesta es 0.
    if (pCierre < EPS) {
        std::cout << std::fixed << std::setprecision(5) << 0.0 << std::endl;
        return 0;
    }

    // Normalizar las probabilidades sin el evento de 'espera' (p1).
    // Si ocurre p1, el estado no cambia, es como si no pasara nada y se repite la tirada.
    double probOlvidaNorm = pOlvidaTarjeta / (1.0 - pEspera);
    double probExitoNorm = pExito / (1.0 - pEspera);
    double probCierreNorm = pCierre / (1.0 - pEspera);

    // Calcular probOlvidarNVeces[x] = (probOlvidaNorm)^x
    // Representa la probabilidad de que 'x' personas consecutivas olviden su tarjeta.
    probOlvidarNVeces[0] = 1.0;
    for (int x = 1; x <= longitudColaInicial; ++x) {
        probOlvidarNVeces[x] = probOlvidarNVeces[x - 1] * probOlvidaNorm;
    }

    // Caso base para una cola de 1 persona:
    // El jugador siempre está en la posición 1.
    // probCierrePosicion[1][1] = probCierreNorm / (1 - probOlvidaNorm) si 1 <= limitePrimerasPosiciones
    // La fórmula es la suma de una serie geométrica: probCierreNorm + probOlvidaNorm*probCierreNorm + ...
    if (1 <= limitePrimerasPosiciones) {
        probCierrePosicion[1][1] = probCierreNorm / (1.0 - probOlvidaNorm);
    } else {
        probCierrePosicion[1][1] = 0.0;
    }


    // Llenar la tabla DP
    // i: tamaño actual de la cola (desde 1 hasta longitudColaInicial)
    // j: posición del jugador en la cola (desde 1 hasta i)
    for (int i = 1; i <= longitudColaInicial; ++i) {
        // Calcular contribucionTransicion[j] para la cola de tamaño 'i'
        for (int j = 1; j <= i; ++j) {
            if (j == 1) { // Si el jugador está en la primera posición
                // Si la cafetería cierra y el jugador está en la primera posición (1 <= k), se suma probCierreNorm.
                // Si j=1, dp[i-1][j-1] sería dp[i-1][0], que no es un estado válido.
                // contribucionTransicion[1] es solo la probabilidad de cierre si el jugador está en posición 1 y 1<=k.
                contribucionTransicion[j] = (1 <= limitePrimerasPosiciones ? probCierreNorm : 0.0);
            } else { // Si el jugador está en una posición j > 1
                // La persona de enfrente fue atendida. El jugador avanza de j-1 a j.
                // Si la cafetería cierra y el jugador está en la posición j (j <= k), se suma probCierreNorm.
                contribucionTransicion[j] = probCierrePosicion[i - 1][j - 1] * probExitoNorm;
                if (j <= limitePrimerasPosiciones) {
                    contribucionTransicion[j] += probCierreNorm;
                }
            }
        }

        // Calcular probCierrePosicion[i][i] (jugador en la última posición)
        // Similar al problema del juego de dados, usando la técnica de recurrencia lineal.
        // sum_{j=1 to i} probOlvidarNVeces[i-j] * contribucionTransicion[j]
        double sumaContribuciones = 0.0;
        for (int j = 1; j <= i; ++j) {
            sumaContribuciones += probOlvidarNVeces[i - j] * contribucionTransicion[j];
        }
        probCierrePosicion[i][i] = sumaContribuciones / (1.0 - probOlvidarNVeces[i]);

        // Calcular probCierrePosicion[i][j] para j desde 1 hasta i-1
        // (1er elemento ya está calculado para dp[1][1] y el loop para i=1)
        if (i > 1) {
            // El jugador está en la posición 1.
            // O la persona anterior (de posición 1 en la cola actual) olvidó su tarjeta y el jugador estaba en la última posición (dp[i][i]),
            // O la cafetería cierra ahora (si 1 <= k).
            probCierrePosicion[i][1] = probCierrePosicion[i][i] * probOlvidaNorm;
            if (1 <= limitePrimerasPosiciones) {
                probCierrePosicion[i][1] += probCierreNorm;
            }

            // Calcular probCierrePosicion[i][j] para posiciones intermedias (j de 2 a i-1)
            for (int j = 2; j < i; ++j) {
                // El jugador en posición j puede venir de:
                // 1. La persona en posición j-1 (actual) olvidó su tarjeta, y el jugador estaba en posición j-1.
                // 2. La contribución directa de un cierre o una persona atendida (contribucionTransicion[j]).
                probCierrePosicion[i][j] = probCierrePosicion[i][j - 1] * probOlvidaNorm + contribucionTransicion[j];
            }
        }
    }

    // La pregunta es la probabilidad de que el jugador esté en las primeras 'k' posiciones cuando cierra.
    // Esto significa sumar probCierrePosicion[longitudColaInicial][j] para j=1 a k.
    double resultadoFinal = 0.0;
    for (int j = 1; j <= limitePrimerasPosiciones; ++j) {
        // Asegurarse de que j no exceda la longitud actual de la cola
        if (j <= longitudColaInicial) {
            resultadoFinal += probCierrePosicion[longitudColaInicial][j];
        }
    }
    
    // Si la posición inicial del jugador (m) es mayor que k, entonces no podrá estar en las primeras k posiciones, por lo que la prob es 0.
    // La lógica de la DP ya maneja esto, ya que contribucionTransicion[j] no suma probCierreNorm si j > k.
    // Entonces, probCierrePosicion[i][j] para j > k será 0 (si no hay ninguna contribución de cierre).
    // Por lo tanto, el sumatorio correctamente dará 0 si el jugador inicialmente estaba en una posición > k.
    // De lo contrario, sumará los valores relevantes.

    std::cout << std::fixed << std::setprecision(5) << resultadoFinal << std::endl;

    return 0;
}