3288 - Pascal's Triangle: Sum of Levels

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3288 - Pascal's Triangle: Sum of Levels

Post by ymondelo20 » 5 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
isaac
Posts: 83
Joined: 4 years ago
Gender: None specified

Re: 3288 - Pascal's Triangle: Sum of Levels

Post by isaac » 4 years ago

Vease que la suma de los elementos de la i-esima fina (conteo en base cero), es 2^i. Esto es facil de probar matematicamente. Inicialmente es 1, lo que corresponde con 2^0. La siguiente fila se obtiene duplicando este 1. La tercera fila se obtiene haciendo el mismo procedimiento, pero en caso que dos elementos ocupen la misma posicion, se sustituyen por la suma de ellos. Ejemplo:


1 ==> 1
1 1 ==> 1 1
1 1+1 1 ==> 1 2 1
1 1+(1+1) (1+1)+1 1 ==> 1 3 3 1

Como cada fila se obtiene duplicando la fila anterior y comienza en 1, se puede decir que la n-esima fila es 2^n.

Post Reply

Return to “Problem set”