Los ganadores

Sin más preámbulos, los ganadores, junto a sus obras, son:

Chema Cortes con pet1-pych3m4.py:

n=input();d=1;r=""
while d<n:
 d+=1;s=0
 while n%d<1:n/=d;s+=1
 if s:r+=" x %d"%d+"^%d"%s*(s>1)
print r[3:]or n

Javier Mansilla con pet1-jmansilla.py :

s=input();_='';i=1
while s>i:
 c=0;i+=1
 while 1>s%i:c+=1;s/=i
 if c:_+=' x '+`i`+'^%i'%c*(c>1)

Oswaldo Hernández con pet1-hdzos.py:

n=input()
d,f="",1
while n>1:
 f+=1;r=0
 while n%f<1:r+=1;n/=f
 if r:d+=" x %s"%f+"^%s"%r*(r>1)

Mención especial

En esta oportunidad hemos considerado dar el premio a la entrada más tramposa a Darni, que en lugar de que renombremos su archivo pet1-darni.py pidió que mantengamos su seudónimo artístico ZT1pbnB1dCgpCnM9JycKZD0xCndoaWxlIGU+MToKCXA9MDtkKz0xCgl3aGlsZSBlJWQ8MTplLz1kO3ArPTEKCWlmIHA6cys9JyB4ICVkJyVkKyhwPjEpKignXiVkJyVwKQpwcmludCBlKnNbMzpdb3IgZQ==

Este es el contenido del archivo pet1-ZT1pbnB1dCgpCnM9JycKZD0xCndoaWxlIGU+MToKCXA9MDtkKz0xCgl3aGlsZSBlJWQ8MTplLz1kO3ArPTEKCWlmIHA6cys9JyB4ICVkJyVkKyhwPjEpKignXiVkJyVwKQpwcmludCBlKnNbMzpdb3IgZQ==.py:

import base64;exec(base64.decodestring(__file__[5:-3]))

Información adicional sobre la competencia puede encontrarse en http://python.org.ar/pyar/Proyectos/RevistaPythonComunidad/PET1/Desafio

Nuevo desafío

El nuevo desafío fue escrito por Alejandro Santos, quien adora resolver problemas, y esta semana estuvo mandando varios Quizz a la lista de PyAr.

Gracias a Matias "Tuute" Bellone por leer una revisión inicial del problema.

El número QQQ

QQQ es la red social más popular de país del país de Ainohtyp. Al estilo microblog, QQQ es una red social donde los usuarios pueden publicar solamente la palabra QQQ. Los usuarios también pueden tener de contactos a otros usuarios, pero se tienen que aceptar mutuamente.

Los administradores de la red social armaron un listado con los usuarios ordenado por la cantidad de contactos de cada uno, y el Rulo encabeza la lista teniendo la mayor cantidad de contactos.

Tu trabajo es hacer un programa para averiguar cuál es la mínima distancia entre cada persona con el Rulo. Eso es, la mínima cantidad de saltos que hay entre el Rulo y el resto. Si hay dos o más formas de llegar al Rulo, elegir la más corta.

Por ejemplo, si el Rulo es amigo de Juan y Pedro, Pedro es amigo de Carla, y Carla es amiga del Rulo, Carla tiene distancia 1 con el Rulo, y Juan y Pedro tienen ambos distancia 1 con el Rulo.

Es posible llegar desde el Rulo a Carla por medio de Pedro, pero como Carla es amiga del Rulo la mínima distancia es 1. Pero si Jorge es amigo de Pedro, entonces para llegar desde el Rulo a Jorge la mínima distancia es 2 ya que se tiene que pasar por Pedro.

Datos de entrada

Todos los datos se leen por entrada estándar.

Por cuestiones de privacidad los datos son anónimos, y la única información de los usuarios es su número de usuario dentro de la red.

En la primer línea hay dos números N y M que dicen la cantidad de usuarios y la cantidad de relaciones que hay en la red social, respectivamente.

Los usuarios se numeran de forma consecutiva y sin descartar ningún usuario desde el 1 en adelante, siendo Rulo el usuario número 1. En las M líneas siguiente hay dos números que indican una relación entre dos usuarios.

Algunos usuarios tienen cero contactos o no hay forma de armar la cadena de contactos al Rulo.

Datos de salida

Imprimir por salida estándar N lineas con dos números separados por un único espacio en blanco. El primer número es el número de usuario, y el segundo número es la mínima distancia hacia el Rulo.

En caso de no poder calcular la distancia con el Rulo, mostrar el caracter "X".

Ejemplo

Entrada:

8 7
1 2
1 3
1 4
2 5
3 5
5 6
4 6
7 8

Salida:

1 0
2 1
3 1
4 1
5 2
6 2
7 X
8 X

Los participantes deben enviar su solución como un archivo .py (con la forma pet2-USERNAME.py) y esta será ejecutado con python 2.7 en la computadora de Alejandro. El ganador del desafío será aquel que logre la solución que pase una batería de pruebas especialmente confeccionada en el menor tiempo posible.

Enviá tu solución a revistapyar@netmanagers.com.ar poniendo DESAFIO2 en el título del mail antes del 30/05/2011.

Suerte y happy brain squshing!

Aclaraciones y Feedback

Eventuales aclaraciones y feedback para los participantes será dado a través de la wiki: http://python.org.ar/pyar/Proyectos/RevistaPythonComunidad/PET2/Desafio