Un problema de juez en línea que nadie vio en clase, atacado con el método completo: entender qué se pide, nombrar la función objetivo, demostrar que es monótona, acotar el rango, decidir si la solución existe, fijar la tolerancia y recién ahí escribir código. Cada tarjeta se abre cuando la anterior queda resuelta.
UVa 10341 — Solve It.
Enunciado:
https://vjudge.net/problem/UVA-10341
Enviar la solución:
https://vjudge.net/problem/UVA-10341
Resuelva la ecuación
p·e⁻ˣ + q·sen(x) + r·cos(x) + s·tan(x) + t·x² + u = 0
donde 0 ≤ x ≤ 1.
Entrada. Varios casos de prueba hasta EOF. Cada caso trae seis
enteros en una línea: p q r s t u, con
0 ≤ p, r ≤ 20 y −20 ≤ q, s, t ≤ 0.
Salida. Por cada caso, el valor de
x con 4 decimales, o la cadena No solution
cuando corresponda.
Fíjese en las restricciones de los coeficientes antes de seguir: parecen un detalle de formato y son el corazón del problema.
Cada línea trae seis enteros. ¿Qué son?
¿Cuál es la función sobre la que se va a buscar, y qué valor se busca?
La bisección solo funciona si f es
monótona en el rango. Nadie lo dice en el enunciado: hay que
demostrarlo, y la prueba se arma término a término. Para cada uno,
derive y decida qué hace en [0, 1] con la restricción que le impone el
enunciado.
t > 0, el término
t·x² subiría, la monotonía se caería y este problema pediría
otra técnica.
El rango viene regalado: [0, 1]. Pero
el enunciado admite responder No solution, así que hay algo
más que comprobar. ¿Cómo se decide si la solución existe?
| [a, b] | mitad | f(mitad) | Decisión |
|---|
El segundo caso es el que enseña: f(0) y f(1) son los dos positivos, la curva nunca cruza el cero dentro del rango y la respuesta no es un número.
El juez pide 4 decimales. ¿Qué ε conviene?
El esqueleto ya trae la forma que salió de las tarjetas anteriores. Lo que falta es justo lo que cada tarjeta decidió: complételo usted.
import math
def f(p, q, r, s, t, u, x):
# El lado izquierdo de la ecuacion, evaluado en x
# Transcriba la formula del enunciado
resultado = 0
return resultado
def resolver(p, q, r, s, t, u, eps):
# Tarjeta 5: la solucion existe solo si el cero queda encerrado.
# Escriba la condicion que descarta los casos sin solucion.
if ...:
resultado = None
else:
# Tarjeta 5: el rango lo fija el enunciado
a = ...
b = ...
# Tarjeta 7: el ciclo corre mientras el intervalo sea mas ancho que eps
while ...:
mitad = (a + b) / 2
# Tarjeta 4: f decrece. Decida que extremo se mueve en cada caso
if ...:
a = mitad
else:
b = mitad
# El valor que se devuelve es el centro del intervalo final
resultado = ...
return resultado
Ninguno de los huecos es de sintaxis: cada uno es una
decisión que ya tomó en las tarjetas anteriores. El del if
interno es el que separa a quien entendió la monotonía de quien copió la
plantilla de la clase.
De estos tres descuidos, ¿cuál produce un programa que compila, corre, no se cuelga y responde mal?
El problema no está resuelto hasta que el juez lo acepta.
https://vjudge.net/problem/UVA-10341
Antes de enviar
0.7071, No solution, 0.7554."%.4f", no el print por defecto.Si el veredicto no es Accepted
No solution sin comprobar.El mismo recorrido —entrada, función objetivo, monotonía demostrada, rango, existencia, tolerancia, código— sirve para los tres problemas de la sesión:
https://vjudge.net/problem/UVA-11909https://vjudge.net/problem/UVA-11909https://vjudge.net/problem/UVA-11646https://vjudge.net/problem/UVA-11646https://vjudge.net/problem/UVA-714https://vjudge.net/problem/UVA-714