Cuál es el último?
Submit solution
Points:
100 (partial)
Time limit:
1.0s
Memory limit:
256M
Author:
Problem types
Allowed languages
C, C++, Go, Java, Python, VB
Inicialmente se tiene un conjunto , con los elementos .
Mientras el conjunto tenga al menos dos elementos, se realizará una de las siguientes dos operaciones con probabilidad cada una:
Se elimina el mayor elemento de S.
Se elimina el menor elemento de S.
Diga para cada elemento de , cual es la probabilidad de que él sea el elemento que quede en el conjunto al final de todas las operaciones.
Se puede notar que esta probabilidad se puede expresar de la forma , donde y son coprimos, y , imprima módulo , .
Recuerde que , si y son coprimos.
Subtareas
Subtarea 1: (25 puntos)
Subtarea 2: (35 puntos)
Subtarea 3: (40 puntos)
Entrada
n
Salida
P_1 P_2 P_3 ... P_n
P_i es la probabilidad de que el elemento que quede en el conjunto sea .
Ejemplo de entrada
3
Ejemplo de salida
250000002 500000004 250000002
Las probabilidades son , , .
Comments