- Na matriz de
abaixo, quatro números ao longo de uma linha diagonal foram marcadas em negrito. O produto desses números é 26 *
*
.
0802229738150040007504050778521250779108
4949994017811857608717409843694804566200
8149317355791429937140675388300349133665
5270952304601142692468560132567137023691
2231167151676389419236542240402866331380
2447326099034502447533537836842035171250
3298812864236710263840675954706618386470
6726206802621220956394396308409166499421
2455580566739926971778789683148834896372
2136230975007644204535140061339734313395
7817532822753167159403800462161409535692
1639054296353147555888240017542436298557
8656004835718907054444374460215851541758
1980816805944769287392138652177704895540
0452088397359916079757321626267933279866
8836688757622072034633674655123263935369
0442167338253911249472180846293240627636
2069364172302388346299698267598574043616
2073352978319001743149714886811623570554
0170547183515469169233486143520189196748
Qual é o maior produto de quatro números adjacentes em qualquer direção (cima, baixo, esquerda, direita, ou na diagonal) na matriz de 20x20?
0802229738150040007504050778521250779108 | |
4949994017811857608717409843694804566200 | |
8149317355791429937140675388300349133665 | |
5270952304601142692468560132567137023691 | |
2231167151676389419236542240402866331380 | |
2447326099034502447533537836842035171250 | |
3298812864236710263840675954706618386470 | |
6726206802621220956394396308409166499421 | |
2455580566739926971778789683148834896372 | |
2136230975007644204535140061339734313395 | |
7817532822753167159403800462161409535692 | |
1639054296353147555888240017542436298557 | |
8656004835718907054444374460215851541758 | |
1980816805944769287392138652177704895540 | |
0452088397359916079757321626267933279866 | |
8836688757622072034633674655123263935369 | |
0442167338253911249472180846293240627636 | |
2069364172302388346299698267598574043616 | |
2073352978319001743149714886811623570554 | |
0170547183515469169233486143520189196748 |
Passo 1
O enunciado pede para encontrar, numa matriz 20×20 de inteiros, o maior produto de quatro números adjacentes em qualquer direção (horizontal, vertical ou nas duas diagonais). Vamos usar a ideia de varrer todas as posições possíveis e manter uma variável “maxProduto” com o maior valor encontrado.
Passo 2
Primeiro a gente precisa transformar cada linha de 40 dígitos em uma lista de 20 números inteiros. Como cada número ocupa sempre 2 dígitos (com zeros à esquerda quando necessário), basta dividir a string de cada linha em pares de caracteres e converter para inteiro, formando a matriz
com
.
Passo 3
Para a direção horizontal, fazemos laços em
até 19 e
até 16 e calculamos o produto de quatro termos consecutivos:
. Se
, atualizamos
.
Passo 4
Para a direção vertical, fazemos laços em
até 16 e
até 19 e calculamos
, atualizando
quando encontrar um valor maior.
Passo 5
Para a diagonal principal (de cima para baixo e da esquerda para a direita), laços em
até 16 e
até 16, com
. Novamente, comparamos e atualizamos o máximo.
Passo 6
Para a diagonal secundária (de cima para baixo e da direita para a esquerda), laços em
até 19 e
até 16, com
, sempre atualizando o maior produto encontrado.
Passo 7
Depois de percorrer todas as direções e todas as janelas de quatro elementos, a variável
conterá o maior produto possível na matriz.
Resposta
70600674