#P2631. Barcodes

Barcodes

题目背景

code-11 是一种条形码编码系统,用来将一个字符串编码为条形码。

题目描述

在这种编码系统中

可以使用的字符仅有数字0 到9 以及"-"号,以及特殊的start/stop 字符放在条形码的开头

和结尾。对于每个字符,都对应了一个长度为5 的01 串如下所示,对应到条形码中,每个

条形码都是由黑白相隔的条带组成的,且第一个条带为黑色。条带分为宽和窄两种,宽带的宽度为窄带的两倍,0 表示窄的,1 表示宽的条带。

character Encoding

0 00001

1 10001

2 01001

3 11000

4 00101

5 10100

6 01100

7 00011

8 10010

9 10000

  •                        00100
    

Start/Stop 00110

而每两个相邻的字符之间一定是一个白色窄带作为分隔。

为了能够检测条形码的正确性,我们加入两个检测数字C 和K,加在条形码的末尾(在

stop 之前)。设需编码的字符串为c1...cn,则C 为:

n ( ∑ ((n-i)mod 10 +1)*w(ci)) mod 11

 i=1

K 为:

n+1 ( ∑ ((n-i)mod 10 +1)*w(ci)) mod 11

  i=1

而cn+1 即为C。其中w(ci)为每个字符的权重。0 到9 即为0 到9。"-"为10。

举个例子,对于字符串123-45,C 和K 分别等于5 和2,则条形码为123-4552,并在前

后加上start 和stop 符号。

在实际应用中,通过探测器探测出每个条带的宽度后,通过解析软件将条形码还原为原本的字符串。

由于条形码方向并未固定,所以软件必须自己判断这个条形码是从左至右的还是从右至左的。 现在,你的任务是扫描并解析一个条形码。你所拥有的信息为每个条带的宽度,但由于设备总是会有误差的,所以,宽带宽度不一定严格的是窄带的宽度的两倍,你的程序需要能够容忍5%的误差。

输入格式

由于输出的特殊情况较多,所以采用多组测试数据。 输入第一行包括一个整数T表示测试数据的组数,对于每组数据首先是一个整数n表示该条形码有多少条带。接着n个整数d1..dn以空格隔开表示了每个条带的宽度。再次强调你并不知道这个条形码是从左至右的还是从右至左的,你需要正着和反着都判断一遍。 T <= 20, n <= 150, di<=200。

输出格式

对于每组数据输出一行。 输出时分如下几种情况。若该条形码合法,则输出解析所得的原字符串,不包括检测字符C和K。若可以成功解析但是检测字符C错了,则输出"bad C"。若C也是对的,但K是错的,则输出"bad K"。对于剩下所有情况输出bad code。

3 
59 
10 20 20 10 10 10 20 10 10 20 10 10 10 10 20 10 20 10 10 10 20 10 20 10 20 10 20 10 10 10 10 10 20 10 10 10 10 10 10 20 20 10 20 10 10 20 10 10 20 10 10 10 20 10 10 20 20 10 10 
35 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
35 
10 10 20 20 10 10 20 10 10 10 20 10 10 20 10 10 20 10 10 10 20 10 20 10 20 10 10 10 10 10 10 10 20 20 10
123-45 
bad code
bad K

提示

注意A相对于B误差<=%5是指|A-B|/B<=5% 本题是指宽带相对于窄带。