Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CIRCUITO - Circuito Bioquímico Digital

Um circuito bioquímico digital (CBD) é um artefato composto de um conjunto de pontos de processamento. Cada ponto de processamento é constituído por um minúsculo receptáculo para reagentes bioquímicos, feito de um substrato biológico que se comporta como um micro-circuito eletrônico digital. Dependendo do estado da reação no receptáculo, o substrato gera dois níveis de voltagem. Um leitor acoplado ao CBD é capaz de realizar a leitura de todos os pontos de processamento de um CDB num dado instante, interpretando os dois níveis de voltagem como 0 ou 1.

Um experimento com o CBD é realizado da seguinte maneira. Os pontos de processamento são carregados com as substâncias de interesse e reagentes apropriados e, a cada intervalo fixo de tempo (tipicamente alguns milisegundos), os pontos de processamento s ̃o lidos. Assim, o experimento resulta em uma seqüência de conjuntos (vetores) de bits, cada vetor correspondendo a uma medição do CBD.

Uma seqüência ininterrupta de bits 1 de um mesmo ponto de processamento ao longo do tempo é denominada de palito. O comprimento de um palito é o número de bits 1 que o compõe (note que o comprimento dos palitos de um experimento pode variar entre um e o número de medições efetuadas). Uma característica importante de um experimento com o CBD é a quantidade e o comprimento dos palitos gerados. A figura abaixo mostra o resultado de um experimento realizado com um CBD de seis pontos de processamento, em que foram efetuadas quatro mediçõs, contendo três palitos de comprimento um, um palito de comprimento dois e um palito de comprimento quatro.

0 1 0 1 1 0
0 0 0 1 0 0
0 1 0 1 0 1
0 1 0 1 0 0

Você foi contratado para escrever um programa que determine, dado o resultado de um experimento, quantos palitos de comprimento igual ou maior do que um certo valor foram gerados.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém três inteiros P, N e C que indicam respectivamente o número de pontos de processamento (1 ≤ P ≤ 1000), o número de medições efetuadas (1 ≤ N ≤ 1000) e o comprimento mínimo de palitos de interesse (1 ≤ C ≤ N). Cada uma das próximas N linhas contém seqüências de P dígitos {0, 1}, separados por um espaço em branco. O final da entrada é indicado por P = N = C = 0.

Saída

Para cada caso de teste da entrada seu programa deve produzir uma única linha da saída, contendo o número de palitos de comprimento maior ou igual a C produzidos pelo experimento.

Exemplo de entrada

2 2 2
1 1
1 1
4 5 3
0 1 0 1
1 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
0 0 0

Saída para os exemplos de entrada

2
2

Adicionado por:Wanderley Guimarăes
Data:2009-09-30
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Primeira fase da Maratona de Programação - 2006

hide comments
2014-08-22 02:08:26 Jefferson Carlos [UFCG]
Simples estratégia gulosa.
2012-09-14 03:27:04 Alex Paixão (UNIME)
Verifique no detalhe quando for maior que o pino solicitado...
2011-11-09 11:55:12 Pablo Goulart Silva
Também comparei minha resposta ŕ saída disponível no SPOJ, porém quando submeto o programa aparece sempre resposta errada.
2011-09-05 05:24:47 Marcos.Freitas [UNDB]
aff, meu arquivo de testes tá imenso e o algoritmo responde corretamente eles pra muitas colunas e linhas, mas o spoj diz que năo. "resposta errada"
2010-09-18 04:59:32 Bruno Pereira de Andrade [UNIVAS]
Comparei a resposta do meu programa com a saída disponibilizada no site da maratona, e as saídas batem, agora quando tento submeter ao spoj ganho "resposta errada", alguém poderia verificar isso?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.