Task: Bar Codes
- Return to IOI '95 Problems
Figure 1: Bar-code symbol over 7 units (see top) with 4 bars (see bottom)
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: 1110110Figure 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 Data
The first line of file INPUT.TXT contains the numbers n, k, and m (1<=n,k,m<=33). On the second line is a number s (0<=s<=100). The following s lines each contain some symbol in BC(n,k,m), represented by `0's and `1's as in Figure 2.Output Data
On the first line of file OUTPUT.TXT 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 file (Subtask B).Example Input and Output
Figure 3 gives possible input and output files for the example above.____________ _____________ |INPUT.TXT | |OUTPUT.TXT | |__________| |___________| |7 4 3 | |16 | |5 | |4 | |1001110 | |15 | |1110110 | |3 | |1001100 | |4 | |1001110 | |0 | |1000100 | |___________| |__________|Figure 3: Example input and output