## IOI '95 Practice Task 3 - Bar Codes

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 8M

Problem type
##### IOI '95 - Eindhoven, Netherlands

A bar-code symbol consists of alternating dark and light bars, starting with a dark bar on the left. Each bar is a number of units wide. Figure 1 shows a bar-code symbol consisting of bars that extend over units. Figure 1: Four fences and some of their letter strings (joints not to scale)

In general, the bar code  is the set of all symbols with bars that together extend over exactly units, each bar being at most units wide. For instance, the symbol in Figure 1 belongs to  but not to  .

0: 1000100  |  8: 1100100
1: 1000110  |  9: 1100110
2: 1001000  | 10: 1101000
3: 1001100  | 11: 1101100
4: 1001110  | 12: 1101110
5: 1011000  | 13: 1110010
6: 1011100  | 14: 1110100
7: 1100010  | 15: 1110110
Figure 2: All symbols of BC(7, 4, 3)

Figure 2 shows all 16 symbols in  . Each 1 represents a dark unit, each 0 a light unit. The symbols appear in lexicographic (dictionary) order. The number on the left of the colon (:) is the rank of the symbol. The symbol in Figure 1 has rank in  .

#### Input Specification

The first line of input contains the numbers , , and  . On the second line is a number  . The following lines each contain some symbol in  , represented by 0s and 1s as in Figure 2.

#### Output Specification

On the first line of output your program should write the total number of symbols in  (Subtask A). On each of the following lines, it should write the rank of the corresponding symbol in the input (Subtask B).

#### Sample Input

7 4 3
5
1001110
1110110
1001100
1001110
1000100

#### Sample Output

16
4
15
3
4
0

## Comments

There are no comments at the moment.