Autores: Vicente Opazo, Martín Andrighetti

Tiempo límite: 2 segundos

Memoria límite: 256 megabytes

En el campo de la inteligencia artificial es común representar ideas y conceptos como vectores en un espacio de alta dimensionalidad. Formalmente, a cada concepto \(a\) le asignamos un vector \(E_{a}\), llamado el embedding de \(a\). Por ejemplo, si usaramos un espacio de dimensionalidad \(n= 4\), el vector asociado al concepto de “rojo” sería un vector de \(4\) elementos, por ejemplo \(E_{rojo} = (0.5, 1, -3, 0)\). Otros conceptos tendrían sus propios vectores asociados, por ejemplo el concepto de “felicidad” podría representarse por el vector \(E_{felicidad} = (0, -1, -2, 5)\).

Representar conceptos de esta manera nos permite hacer varias cosas interesantes. Por ejemplo, podemos mezclar varios vectores. Dado \(k\) vectores \(E_{1}, E_{2}, \ldots , E_{k}\), podemos elegir \(k\) números \(0 \le x_{1}, x_{2}, \ldots , x_{k}\le 1\) tal que \(x_{1} + x_{2} + \ldots + x_{k}= 1\), y la mezcla resultante será \(x_{1}E_{1} + x_{2}E_{2} + \ldots + x_{k}E_{k}\). Intuitivamente, al mezclar vectores el resultado será un vector intermedio, donde cada vector \(E_{i}\) aporta al resultado final en proporción a \(x_{i}\). Por esta razón, llamamos a los números \(x_{1}, \ldots , x_{k}\) como los pesos de la mezcla.

Dado \(n+ 2\) vectores \(E_{1}, E_{2}, \ldots , E_{n+2}\), cada uno con \(n\) elementos, tu misión es:

1. Separar los \(n+ 2\) vectores en dos grupos, \(A\) y \(B\). Ni \(A\) ni \(B\) pueden estar vacíos. 2. Mezclar los vectores en \(A\) usando pesos a tu elección para obtener un vector \(z\). 3. Mezclar los vectores en \(B\) usando pesos a tu elección para obtener el mismo vector \(z\).

Pablo Messina, la eminencia en machine learning, ya demostró que esto siempre se puede hacer, pero dejó la implementación como ejercicio para el lector. ¿Puedes implementarlo?

Entrada

La primera línea contiene el entero \(n\) (\(1 \le n\le 500\)), representando la cantidad de elementos por vector.

Luego hay \(n+ 2\) líneas adicionales. La \(i\)-ésima de estas líneas contiene \(n\) números reales \(a_{i,1}, a_{i,2}, \ldots , a_{i,n}\) (\(-1000 \le a_{i,j}\le 1000\)). Estos números representan el vector de \(n\) elementos \(E_{i}= (a_{i,1}, a_{i,2}, \ldots , a_{i,n})\).

Salida

En la primera línea imprime una palabra de \(n+ 2\) caracteres, donde el \(i\)-ésimo caracter es “A” si el \(i\)- ésimo vector pertenece al grupo \(A\), o “B” si el \(i\)-ésimo vector pertenece al grupo \(B\). Siempre debe haber al menos un caracter “A” y al menos un caracter “B”, porque los grupos no pueden estar vacíos.

Luego imprime \(n+ 2\) líneas. En la \(i\)-ésima de estas líneas, imprime un único número real: el peso \(x_{i}\) asociado al vector \(E_{i}\). Este peso \(x_{i}\) corresponde al peso de \(E_{i}\) en la mezcla de \(A\) si el vector pertenece a \(A\). En caso contrario, el vector pertenece a \(B\) y el peso \(x_{i}\) corresponde al peso de \(E_{i}\) en la mezcla de \(B\).

Debes asegurar lo siguiente:

• \(0 \le x_{i}\le 1\) para \(i= 1, 2, \ldots , n+ 2\).
• Si \(A_{1}, \ldots , A_{k}\) son los índices de los vectores pertenecientes a \(A\), entonces \(x_{A_{1}} + \ldots + x_{A_{k}}\approx 1\).
• Si \(B_{1}, \ldots , B_{m}\) son los índices de los vectores pertenecientes a \(B\), entonces \(x_{B_{1}} + \ldots + x_{B_{m}}\approx 1\).
• Los resultados de ambas mezclas deben ser aproximadamente iguales. Es decir, se debe cumplir que \(x_{A_{1}}E_{A_{1}} + \ldots + x_{A_{k}}E_{A_{k}}\approx x_{B_{1}}E_{B_{1}} + \ldots + x_{B_{m}}E_{B_{m}}\).

Para este problema, dos números son aproximadamente iguales si su diferencia absoluta o relativa es a lo más \(10^{-4}\). Es decir, \(a\approx b\) si y sólo si \(|a-b| \le 10^{-4}\) ó \(\frac{|a-b|}{\min(|a|,|b|)} \le 10^{-4}\). Dos vectores son aproximadamente iguales si cada par de componentes son aproximadamente iguales.

Entrada 1

1
-1.5
2.5
0.5

Salida 1

AAB
0.500000000000
0.500000000000
1.000000000000

Entrada 2

4
0.50 1.00 -3.00 0.00
0.00 -1.00 -2.00 5.00
-5.00 0.50 4.50 0.00
4.50 2.00 5.00 -3.50
2.00 2.00 2.50 5.00
3.00 1.00 3.00 -1.50

Salida 2

BBBBAA
0.000426075841
0.289305496378
0.029825308905
0.680443118875
0.086919471666
0.913080528334