Introdução
Com o tempo tão bonito lá fora, você não está com a menor vontade de passar uma hora numa sala de aula.
Meio de mau humor, você entra na sala e repara num triângulo estranhamente satisfatório desenhado na lousa.
Enquanto espera o professor de matemática chegar, você não consegue deixar de notar alguns padrões no triângulo: os valores das bordas são todos 1, cada linha tem um valor a mais que a anterior e o triângulo é simétrico.
Que estranho!
Não muito depois de você se sentar, o professor entra na sala e explica que esse triângulo é o famoso triângulo de Pascal.
Ao longo da hora seguinte, o professor revela algumas coisas incríveis escondidas nesse triângulo:
- Ele pode ser usado para calcular de quantas maneiras você pode escolher K elementos entre N valores.
- Ele contém a sequência de Fibonacci.
- Se você colorir os números ímpares e pares de forma diferente, surge um padrão lindo chamado de triângulo de Sierpiński.
O professor pede que você e seus colegas pesquisem outros usos, e garante que existem muitos mais!
Nesse momento, o sinal da escola toca.
Você percebe que a última hora passou voando enquanto você aprendia sobre o triângulo de Pascal.
Você pega o notebook da mochila rapidinho e sai, para aproveitar tanto o sol quanto as maravilhas do triângulo de Pascal.
Instruções
Sua tarefa é produzir as primeiras N linhas do triângulo de Pascal.
O triângulo de Pascal é um array triangular de números inteiros positivos.
No triângulo de Pascal, a quantidade de valores em uma linha é igual ao número da linha (que começa em um).
Portanto, a primeira linha tem um valor, a segunda tem dois, e assim por diante.
A primeira linha (a do topo) tem um único valor: 1.
Os valores das linhas seguintes são calculados somando os números imediatamente à direita e à esquerda da posição atual na linha anterior.
Se a linha anterior não tiver um valor à esquerda ou à direita da posição atual (o que só acontece nas posições mais à esquerda e mais à direita), trate o valor dessa posição como zero (na prática, "ignorando-o" na soma).
Exemplo
Vamos ver as primeiras 5 linhas do triângulo de Pascal:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
A linha do topo tem um valor, que é 1.
Os valores mais à esquerda e mais à direita têm apenas uma posição anterior para considerar: a posição à sua direita, no primeiro caso, e à sua esquerda, no segundo.
Como o valor do topo é 1, conclui-se que todos os valores mais à esquerda e mais à direita também são 1.
Os outros valores têm duas posições para considerar.
Por exemplo, o valor do meio da quinta linha (1 4 6 4 1) é 6, já que os valores à sua esquerda e à sua direita na linha anterior são 3 e 3:
