Erasmús
Es conocida la afición existente entre los universitarios españoles al mus, un juego de cartas para cuatro personas con más de 200 años de historia que también es muy jugado en algunos países de Hispanoamérica e incluso en algunas regiones del sur de Francia.
Cuando esos españoles consiguen una beca erasmus para estudiar durante unos meses en otro país de Europa, es fácil entender, pues, que no falte una baraja de cartas entre su equipaje, por lo que pueda ocurrir. En su afán de evangelización muchos de estos estudiantes de erasmus intentan que el juego se extienda, y se empeñan en explicar las reglas a sus compañeros de otros países.
Como a buen seguro sabrás, al mus se juega por parejas, de forma que una pareja de jugadores se enfrenta a otra. Desgraciadamente, a la hora de hacer esas parejas la mayoría de las veces los españoles “se buscan” entre sí, de forma que las partidas terminan siendo competiciones entre países (juegan dos españoles contra dos italianos, por ejemplo).
En esta ocasión, sin embargo, un grupo de estudiantes de erasmus se ha propuesto formar parejas heterogéneas, por lo que no van a aceptar parejas cuyos dos componentes sean de la misma nacionalidad. A la vista de cuántos estudiantes hay de cada país, ¿cuántas parejas distintas pueden formarse?
Entrada
La entrada estará compuesta por varios casos de prueba terminados con una línea con un 0.
Cada caso de prueba tendrá dos líneas. En la primera aparecerá un único entero que indica el número de países totales representados (un número entre 1 y 100.000). La segunda línea contendrá un número por cada país, representando la cantidad de estudiantes de ese país que quieren jugar al mus. El número de estudiantes de cada país no excederá nunca 1.000.000.000.
Salida
Por cada caso de prueba, el programa escribirá el número de parejas distintas que pueden formarse sin que una pareja tenga a sus dos integrantes de la misma nacionalidad. Se garantiza que la respuesta no será nunca superior a 1.000.000.000.000.000.000.
Entrada de ejemplo
2
1 1
2
2 2
3
2 2 1
0
Salida de ejemplo
1
4
8
Solución propuesta
if __name__ == '__main__':
paises = int(input())
respuestas = []
while paises != 0:
estudiantes = [int(x) for x in list(input().split(' '))]
if paises == len(estudiantes):
parejas = 0
for posicion in range(len(estudiantes)):
parejas += (estudiantes[posicion]*(sum(estudiantes[posicion+1:len(estudiantes)])))
respuestas.append(parejas)
else:
respuestas.append("El número de países escritos no coincide con los indicados")
paises = int(input())
for x in respuestas:
print(x)
Al enfrentare a este problema lo primero que intenté fue recurrir a alguna fórmula de combinatoria de las que se estudian en bachillerato, sin embargo, la solución era y es bastante más sencilla de lo que parece.
Para contar el número de posibilidades lo que debemos tener claro es que da igual el orden de la pareja que se forme, es decir, imaginemos la siguientes situación: Pepe, Juan, Adam y George. En este caso, Pepe y Adam serían la misma pareja que Adam y Pepe, parece obvio pero es muy importante ya que se cuenta una sola combinación y no dos.
Por tanto, lo que debemos hacer es por cada número de jugadores de una nacionalidad pueden formar pareja con cualquier de todas las las siguientes, según nuestra lista. Eso se calcula con un simple producto. No hay que realizar las parejas con las nacionalidades ya pasadas porque ya las hemos contado antes.
Ahora bien, ¿cómo hacemos que dada una nacionalidad, es decir, una posición de una lista recuperemos el resto, pues muy fácil, con un slice, como ya hemos realizado otras veces. Una vez realizado el producto hay que sumarlo a la cuenta que ya tengamos.
Después del ejercicio de los árboles binarios de búsqueda, este ejercicio es pan comido.