小 W, del departamento de ingeniería de software, está haciendo un examen de dibujo técnico, pero solo ha traído una regla cuyas marcas se han borrado con los años y un compás. Sin otra alternativa, recurre a ti, que tienes una capacidad extraordinaria para las construcciones geométricas. Ayúdalo a completar el dibujo con rapidez y precisión usando una regla sin graduar y un compás.

Simplifiquemos el problema. Supongamos que 小 W ya dispone de un sistema de coordenadas y una longitud unidad. Necesita que construyas la longitud $L_0$, es decir, que obtengas el punto $(L_0,0)$.

Puedes realizar las siguientes tres operaciones:

1. $\mathrm{line}(A,B)$: trazar la recta que pasa por los puntos $A$ y $B$.
2. $\mathrm{circle}(O,A,B)$: trazar una circunferencia con centro en $O$ y radio igual a la distancia entre $A$ y $B$.
3. $\mathrm{intersect}(i,j)$: marcar todos los puntos de intersección de las figuras $i$ y $j$. Si hay varios, se marcan todos.

Inicialmente, 小 W te proporciona el origen $O(0,0)$, que es el punto número $0$. La longitud unidad la da el punto número $1$, situado en $(1,0)$. También proporciona el eje $x$ (figura número $0$) y el eje $y$ (figura número $1$).

Todos los puntos y figuras nuevos obtenidos durante las operaciones reciben los siguientes números consecutivos.

Si el número actual es $n$, el punto producido por una operación $\mathrm{intersect}$ recibe el número $n+1$.

Si las dos figuras no se cortan, no se produce ningún punto nuevo.

Si hay dos puntos de intersección, el de menor coordenada $x$ (o menor coordenada $y$ si las coordenadas $x$ son iguales) recibe el número $n+1$, y el otro recibe $n+2$.

Obtén el punto $(L_0,0)$ e indica su número. No necesitas obtener el valor exacto, pero tanto la diferencia respecto al valor exacto como el número de operaciones utilizadas influyen en tu puntuación.

Entrada

Esta es una tarea de entrega de archivos de salida. Todos los archivos de entrada draw1.in~draw10.in están en el directorio de la tarea.

Cada dato de entrada $x_0$ es una expresión de Python. El operador ** representa la potenciación: por ejemplo, 3 ** 2 representa $3^2$ y 2 ** 0.5 representa $\sqrt{2}$.

Para ofrecer mayor precisión, los números de la expresión se convierten al tipo decimal, es decir, decimales de alta precisión. Por ejemplo, Decimal(2) representa $2$.

Se garantiza que entre números y símbolos, y entre símbolos, hay un espacio de separación.

El resultado del código Python es el número que se pide construir.

Ten en cuenta que el resultado calculado directamente con Python es aproximado, mientras que se pide el valor exacto: el valor con el que se compara el resultado del participante es el exacto.

También proporcionamos el archivo draw.pdf, que presenta de forma legible la expresión de cada caso.

Salida

Para los 10 archivos de entrada draw1.in~draw10.in, debes entregar los archivos de salida correspondientes draw1.out~draw10.out.

La primera línea de cada archivo de salida contiene un entero $n$, el número de operaciones. Las siguientes $n$ líneas contienen una operación cada una. Los formatos de las tres operaciones son:

line: L A B
circle: C O A B
intersect: I i j

Los parámetros tienen el significado descrito en el enunciado.

La última línea del archivo de salida contiene un entero que indica el número del punto obtenido al final.

Ejemplos

Entrada 1

Decimal( 2 ) ** ( Decimal( 1 ) / Decimal( 2 ) )

Salida 1

5
C 0 0 1
I 1 2
C 0 1 3
L 1 3
I 0 3
5

Nota

Las cinco operaciones del ejemplo tienen el siguiente significado:

1. Trazar una circunferencia con centro en $O$ y radio unidad. Es la figura número $2$.
2. Tomar las intersecciones de la figura número $2$ (la circunferencia) con el eje $y$. Los puntos son el número $2$, en $(0,-1)$, y el número $3$, en $(0,1)$.
3. Trazar una circunferencia con centro en $O$ y radio igual a la distancia entre los puntos $1$ y $3$. Es la figura número $3$.
4. Unir los puntos $(1,0)$ y $(0,1)$. La recta obtenida es la figura número $4$.
5. Tomar las intersecciones de la figura número $3$ (la circunferencia) con el eje $x$. Los puntos son el número $4$, en $(-\sqrt{2},0)$, y el número $5$, en $(\sqrt{2},0)$.

Por tanto, el punto número $5$ es el punto que se necesita obtener.

Subtareas

Para los 10 archivos de entrada draw1.in~draw10.in, proporcionamos los archivos de parámetros de puntuación draw1.ans~draw10.ans, respectivamente.

Cada archivo de parámetros tiene diez líneas, cada una con dos números $c_i,x_i$. Si la diferencia absoluta entre la abscisa $x$ del punto final $(x,0)$ y $L_0$ no supera $10^{-x_i}$, y el número de operaciones satisface $n \le c_i$, se obtienen $i$ puntos.

La evaluación toma la puntuación más alta entre todas las condiciones satisfechas. Si no se satisface ninguna, se obtienen 0 puntos.

Cómo probar tu archivo de salida

Proporcionamos la herramienta checker para comprobar si tu archivo de salida es aceptable. Para usarla, abre una terminal y ejecuta el siguiente comando para entrar en el directorio de la tarea:

cd draw

Después ejecuta:

./checker <case_no>

Aquí, case_no es el número del caso de prueba. Por ejemplo:

./checker 3

comprueba si draw3.out es aceptable.

Tras ejecutar el programa, checker muestra el resultado de la comprobación del archivo de salida proporcionado. Los posibles resultados incluyen:

1. Terminación anormal: error desconocido.
2. Invalid parameters for checker.: los parámetros pasados a checker no son válidos.
3. Input/Output file does not exist.: no existe el archivo de entrada o de salida.
4. Output invalid: el archivo de salida es incorrecto; puede mostrarse información concreta sobre el error.
5. Correct! Your answer is n. Your score is s.: la salida es aceptable, se han utilizado $n$ operaciones y la puntuación del caso es $s$.

Más funciones

checker también puede comprobar archivos de entrada y salida arbitrarios. Para ello, ejecuta en la terminal:

cd draw
./checker <input_file> <output_file> <ans_file>

input_file, output_file y ans_file son, respectivamente, los nombres de los archivos de entrada, salida y referencia de puntuación.

Por ejemplo:

./checker draw3.in draw3.out draw3.ans

comprueba si draw3.out es aceptable.

La opción -w muestra las coordenadas de cada punto generado. Cada línea tiene el formato:

id x y

Los campos representan, respectivamente, el número del punto, su coordenada $x$ y su coordenada $y$. Se utiliza así:

./checker -w <input_file> <output_file> <ans_file>

o bien:

./checker -w <case_no>

Por ejemplo:

./checker -w draw3.in draw3.out draw3.ans

La opción -i también muestra la salida del participante, para facilitar la depuración. Se utiliza así:

./checker -i <input_file> <output_file> <ans_file>

o bien:

./checker -i <case_no>

Por ejemplo:

./checker -i draw3.in draw3.out draw3.ans

La opción -e prec permite especificar la precisión (número de cifras significativas) de los cálculos de checker. Si no se utiliza, el valor predeterminado de $\mathrm{prec}$ es $200$. Se utiliza así:

./checker -e <prec> <input_file> <output_file> <ans_file>

o bien:

./checker -e <prec> <case_no>

Por ejemplo:

./checker -e 50 draw3.in draw3.out draw3.ans

Las opciones -e prec, -w e -i pueden combinarse en cualquier orden. Por ejemplo:

./checker -w -i -e 50 draw3.in draw3.out draw3.ans

Pista

Podemos utilizar Python para obtener un valor aproximado de la expresión. En concreto, tras iniciar Python en la terminal, introduce:

from math import *
from decimal import *
getcontext().prec = 100

Después copia la expresión del archivo de entrada (el código Python) en esa ventana de la terminal y pulsa Intro para obtener un valor aproximado. Puedes sustituir el 100 del código anterior por la precisión que desees.

Advertencias especiales

Si utilizas archivos de entrada generados por ti para depurar, un tamaño excesivo puede provocar errores en checker. Si ocurre, prueba con datos más pequeños.

Conserva debidamente los archivos de entrada draw.in, tus archivos de salida draw.out y los archivos de parámetros de puntuación draw*.ans, y haz copias de seguridad a tiempo para evitar borrarlos por accidente.