Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Task: Bar Codes
发信站: 哈工大紫丁香 (2002年03月29日13:52:39 星期五), 站内信件

Task: Bar Codes
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: 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 tha
t 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) ord
er. 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 ea
ch contain some symbol in BC(n,k,m), represented by `0's and `1's as in Figu
re 2.
Output Data
On the first line of file OUTPUT.TXT your program should write the total num
ber of symbols in BC(n,k,m) (Subtask A). On each of the s following lines, i
t should write the rank of the corresponding symbol in the input file (Subta
sk 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

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]