Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2438

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2438

Quadradinho de 8

 

Por OBI - Olimpíada Brasileira de Informática 2013 BR Brazil

Timelimit: 1

Fernando ficou sabendo de um novo jogo chamado quadradinho de 8. Nesse jogo, é apresentado ao jogador uma fileira de quadrados, um do lado do outro. Em cada quadrado há um número escrito. Veja abaixo um exemplo de fileira de quadrados:

Para ganhar, o jogador deve escolher alguns quadrados de forma que eles juntos formem apenas um retângulo contíguo e que a soma de seus números seja divisível por 8. Na fileira de quadrados acima, o jogador ganha se escolher os quadrados com os números 6, 0 e 2. O jogador perde se escolher os quadrados com 3, 4 e 9, apesar da soma ser divisivel por 8, os quadrados não estão juntos, eles acabam formando dois retângulos separados.

Você deve estar pensando agora que Fernando quer sua ajuda para que você mostre a ele como ganhar o jogo, mas Fernando é um garoto muito esperto e sabe resolver o jogo rapidamente. Ele quer na verdade que você o ajude a descobrir de quantas formas é possível ganhar esse jogo.

 

Entrada

 

A entrada possui duas linhas. A primeira linha contém apenas um inteiro N (1 ≤ N ≤ 1000000) que indica o número de quadrados na fileira de um jogo. A segunda linha contém N inteiros indicando na ordem os números presentes nos quadrados da fileira de um jogo, (os números nos quadrados são inteiros não negativos menores ou iguais a 1000).

 

Saída

 

Seu programa deve imprimir uma única linha, contendo apenas um inteiro, o número de maneiras de ganhar o jogo apresentado na entrada. Se não for possível que o jogador ganhe o jogo, imprima 0.

 

 

 

Exemplos de Entrada Exemplos de Saída

6

3 4 6 0 2 9

3

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
long long resposta;
int n, vetor[1000001], sequencias[9], soma;
int main() {
    scanf("%d", &n);
    sequencias[0] = 1;
    for (int i = 1; i  < = n; i++) {
        int x;
        scanf("%d", &x);
        soma += x;
        resposta += sequencias[soma % 8];
        sequencias[soma % 8]++;
    }
    printf("%lld\n", resposta);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
6
3 4 6 0 2 9

Output

x
+
cmd
3
Advertisements

Demonstration


Previous
#2437 Beecrowd Online Judge Solution 2437 Distância de Manhattan Solution in C, C++, Java, Js and Python
Next
#2439 Beecrowd Online Judge Solution 2439 Cachecol da Vovó Vitória Solution in C, C++, Java, Js and Python