Given an N-by-P table of bits, count the runs of consecutive 1s in each column whose length is at least C.
Easy3MatrixSimulationImplementationInterviewNo attempts yetTime limit1sMemory limit512 MBA digital biochemical circuit (DBC) is a device built from a set of processing points. One processing point is a tiny receptacle for biochemical reagents, and the receptacle is made of a biological substrate that behaves like a digital electronic microcircuit. Depending on the state of the reaction inside the receptacle, the substrate puts out one of two voltage levels. A reader attached to the circuit samples every processing point at a given instant and reads the two voltage levels as 0 and 1.
An experiment runs like this. First every processing point is loaded with the substance of interest and the matching reagents. Then, at a fixed time interval (a few milliseconds is typical), every processing point is read. The result of the experiment is therefore a sequence of bit vectors, one vector per measurement.
An unbroken run of 1 bits from the same processing point along the time axis is called a stick. The length of a stick is the number of 1 bits in it, so a length is anything from 1 up to the number of measurements taken. The number of sticks an experiment produces and their lengths are an important property of that experiment. The table below is the result of an experiment on a circuit with six processing points in which four measurements were taken. It holds three sticks of length 1, one stick of length 2 and one stick of length 4.
0 1 0 1 1 0
0 0 0 1 0 0
0 1 0 1 0 1
0 1 0 1 0 0
Write a program that, given the result of an experiment, counts how many sticks of length at least a given threshold were produced.
The input holds several test cases. The first line of a test case holds three integers P, N and C. P is the number of processing points (1≤P≤1000), N is the number of measurements taken (1≤N≤1000), and C is the minimum stick length of interest (1≤C≤N). Each of the next N lines holds P digits, each 0 or 1, separated by single spaces. The j-th digit on the i-th line is the value read from processing point j at measurement i. The end of the input is marked by a line with P=N=C=0.
For each test case, print one line holding the number of sticks of length greater than or equal to C that the experiment produced.