Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1486

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

Biochemical Digital Circuit

 

By Ricardo Anido, UNICAMP Brazil

Timelimit: 1

A biochemical digital circuit (BDC) is an artifact composed of a set of processing nodes. Each processing node is composed of a tiny receptacle for biochemical reagents, made of a biological substrate that acts as a digital electronic chip. Depending on the state of the reaction in the receptacle, the substrate generates two voltage levels. A reader coupled to the BDC is able to perform the reading of all the processing nodes of a BDC in a given instant, interpreting the two voltage levels as 0 or 1.

An experiment with the BDC is performed as follows. The processing nodes are loaded with substances of interest and appropriate reagents and, at every fixed interval of time (typically a few milliseconds), the processing nodes are read. Thus, the experiment results in a sequence of sets (vectors) of bits, each vector representing a measurement of the BDC.

An uninterrupted sequence of bits 1 of a same processing node along the time is called a toothpick. The length of a toothpick is the number of bits 1 that composes it (note that the length of the toothpick of an experiment may vary between one and the number of measurements made). An important feature of an experiment with the BDC is the amount and length of toothpicks generated. The figure below shows the result of an experiment conducted with a BDC of six processing nodes, in which four measurements were made, containing three toothpicks of length one, a toothpick of length two and one toothpick of length four.

You've been hired to write a program to determine, given the outcome of an experiment, how many toothpicks of length equal to or greater than a certain value were generated.

 

Input

 

The input contains several test cases. The first line of a test case contains three integers P, N and C respectively that indicates the number of processing nodes (1 ≤ P ≤ 1000), the number of measurements made (1 ≤ N ≤ 1000) and the minimum length of toothpicks of interest (1 ≤ CN). Each of the next N lines contains sequences P digits {0, 1}, separated by a space. The end of input is indicated by P = N = C = 0.

 

Output

 

For each test case in the input your program must produce one line of output, containing the number of toothpicks of length greater than or equal to C produced by the experiment.

 

 

 

Sample Input Sample Output

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

2
2

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
int vetor[1001][1001], m, n, p;
int main() {
    while (scanf("%d %d %d", &n, &m, &p) && (n || m || p)) {
        for (int i = 1; i  < = m; i++) {
            for (int j = 1; j  < = n; j++) {
                scanf("%d", &vetor[i][j]);
            }
        }
        int resp = 0;
        for (int i = 1; i  < = n; i++) {
            int jaforam = 0;
            for (int j = 1; j  < = m; j++) {
                if (vetor[j][i] == 1) {
                    jaforam++;
                } else {
                    resp += (jaforam >= p);
                    jaforam = 0;
                }
            }
            resp += (jaforam >= p);
        }
        printf("%d\n", resp);
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

Output

x
+
cmd
2
2
Advertisements

Demonstration


Previous
#1483 Beecrowd Online Judge Solution 1483 Animal Game Solution in C, C++, Java, Js and Python
Next
#1495 Beecrowd Online Judge Solution 1495 Football Solution in C, C++, Java, Js and Python