IOI '95 Practice Task 3 - Bar Codes

View as PDF

Submit solution

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 4 bars that extend over 1 + 2 + 3 + 1 = 7 units.

Figure 1: Four fences and some of their letter strings (joints not to scale)

In general, the bar code BC (n, k, m) is the set of all symbols with k bars that together extend over exactly n units, each bar being at most m units wide. For instance, the symbol in Figure 1 belongs to BC (7, 4, 3) but not to BC (7, 4, 2).

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 BC (7, 4, 3). 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 4 in BC (7, 4, 3).

Input Specification

The first line of input contains the numbers n, k, and m (1 \le n, k, m \le 33). On the second line is a number s (0 \le s \le 100). The following s lines each contain some symbol in BC (n, k, m), 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 BC (n, k, m) (Subtask A). On each of the s 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.