Las Vegas P61999

Tu coche te ha dejado tirado en Las Vegas. Para poder seguir viajando necesitas comprarte un coche de segunda mano, pero los k dólares que tienes no te alcanzan para pagar los 1000$ que te piden por él. Viendo tu situación, el vendedor se ofrece a apostar contra ti exactamente r rondas de cara o cruz. En cada ronda, tú eliges una cantidad t de dólares para apostar, entre 0 y el total de dólares que tengas en ese instante. Si pierdes (hay un 50% de posibilidades) el vendedor se queda con la cantidad t que habías apostado; si ganas, recuperas el doble de lo apostado (los t dólares apostados, más t dólares adicionales).

Sabiendo que tu objetivo final es conseguir los 1000$ para comprar el coche, se te pide que encuentres qué cantidad de dinero deberías apostar en cada tirada para tener la máxima probabilidad de conseguirlo.

Entrada

Cada entrada esta formada por una cantidad arbitraria de situaciones, no mayor de 20000. Cada situación se da en una línea con dos números separados por un espacio: la cantidad de dólares 0≤ k≤ 1000 que tienes en ese instance, y el número de rondas 1≤ r≤ 10 que tienes por delante. Dispones de un segundo de CPU para resolver cada entrada.

Salida

Para cada situación, escribe una línea con dos números: la cantidad t de dólares que deberías apostar, y la probabilidad que tienes de conseguir el coche si juegas las r apuestas del mejor modo posible, en forma de fracción irreductible. En caso que varias cantidades t dieran idénticas probabilidades, escribe la menor.

Observación

Siempre hay que jugar las r rondas, aunque ya hayas conseguido los 1000 dólares. Esto no representa ningún problema, porque puedes elegir apostar 0 dólares. Del mismo modo, si no tienes ninguna posibilidad de alcanzar los 1000 dólares, deberías apostar también 0, ya que es la menor apuesta dentro de todas las posibles. Estudia los ejemplos dados para asegurarte que entiendes correctamente el enunciado del problema.

Puntuación

• Test1:   Entradas donde todos los casos son r=1.  5 Puntos 

• Test2:   Entradas donde todos los casos son r=1, 2.  15 Puntos 

• Test3:   Entradas donde 1≤ r≤ 10.  80 Puntos