Solução Quadradinho de 8

0 Flares Facebook 0 0 Flares ×

Seja (i, j) o intervalo compreendido entre as posições i e j (inclusive) da fileira de quadradinhos. Note que a soma desse intervalo pode ser obtida se pegarmos a soma de todos os números até a posição j (1, j) e dela subtrairmos a soma de todos os números até a posição imediatamente anterior à posição i (1, i-1). Para ilustrar isso melhor, observe a imagem, onde fica claro que SOMA C = SOMA A - SOMA B

 

quadradinho de 8

Desse modo, escolher duas posições i e j de modo que a soma dos números no intervalo compreendido entre elas seja congruente a zero (módulo 8) é o mesmo que escolher as posições i e j de modo que a diferença entre os intervalos (1, i-1) e (1, n) seja congruente a zero (módulo 8), ou seja, ambos os intervalos devem ter a mesma soma (módulo 8). Desse modo, basta olharmos, para cada posição j do vetor, quantas posições anteriores i têm a soma do intervalo (1, i) congruente à soma (1, j), pois a soma dos elementos de i+1 até j será congruente a zero (módulo 8).

Assim, vamos criar um vetor qtd. Para cada resto r,o valor de qtd[r] guardará quantas posições i da fileira apresentam a soma de todos os quadradinhos até tal posição (intervalo (1, i)) congruente a r (módulo 8), no momento em que lemos o valor de determinada posição. Desse modo vamos criar uma variável resposta com valor zero, e vamos declarar o vetor qtd global para que todos os seus valores recebam 0. A posição 0 d vetor deve receber valor 1, pois a soma do intervalo (0, 0) já começa antes de lermos qualquer número da fileira e é congruente a zero (módulo 8).

Vamos ler então cada um dos números da entrada. Vamos criar uma variável soma que representará a soma atual dos números da fileira, começando, portanto, com valor 0. Vamos agora ler os valores dos números. Para cada número x lido, atualizamos a soma da fileira adicionando o valor de x a soma. Agora, verificamos o resto de soma no módulo 8 ("soma%=8;") e olhamos quantas posições anteriores à que estamos são tais que a soma de todos os números até ela deixa resto soma na divisão por 8. Para cada uma dessas posições, podemos criar um novo intervalo de soma congruente a 0 (módulo 8), logo adicionamos essa quantidade (qtd[soma]) à resposta com o comando "resp+=qtd[soma];".  Depois disso, deveos guardar que encontramos uma nova posição (a atual) em que a soma de todos os números até ela deixa resto soma na divisão por 8, com o comando "qtd[soma]++;" Quando tivermos lido todos os números da entrada, basta imprimirmos uma única linha com o valor de resposta. Como observação final, note que a resposta pode ser muito grande, bem maior que 2 bilhões (pois em uma análise bem simples, podemos somar n vezes as n posições da fileira, e vai até 10^6, logo deve ser declarada como long long int). Segue o código comentado para melhor entendimento:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: