UVALive 5029 Encoded Barcodes

Encoded Barcodes Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu Submit Status Practice UVALive 5029


All the big malls need a powerful system for the products retrieval. Now you are employed design a sub-system: reading the barcodes and return the matching products.

A barcode is an optical machine-readable representation of data, which shows certain data on certain products. A barcode consists of a series of bars with different widths. In our system, the barcodes have been scanned and the widths have been recorded. Every consecutive eight bars are considered as representing the ASCII code of a character, each bar for each bit. Ideally, there should be only two kinds of widths in the eight bars, and the width of the wider bar is twice of the narrower. The wider bar indicates 1, while the narrower indicates 0. However, due to the inaccuracy of printing and scanning, there will be an error of at most 5%. That is, if the pretended exact width is x, you may get a value in the range [0.95x, 1.05x].

For example, the width sequence ``10.0 20.0 10.0 10.0 10.0 10.0 10.0 20.0" is a valid barcode of our system, and it means (01000001)2, which is (65)10 and the corresponding character is ``A". Note that ``10.5 20.1 10.1 10.2 9.9 9.7 10.0 19.9" is also a valid barcode representing the same letter.

You are given the names of all the products and many queries. Every name contains lower-case letters only, and the length is no more than 30. The queries are represented as barcodes. For each query, you should decode it to a string S, and report the amount of products whose prefix is S. For the output may be very large, you only need to output the sum of all the queries for each case.


There are several test cases in the input. The first line of each case contains two integers N and M(1N10000, 1M2000), indicating the number of products and queries. Then N lines follow, indicating the names of the products. Note that the names may be duplicated. Then M query blocks follow. The first line of each query block is an integer K(0 K30) indicating the length of the query, then K lines follow, each line contains 8 positive float numbers, indicating the barcode for each character.

You can assume that the barcodes are always valid, and always represent lower-case letters.


Output one line for each test case, indicating the sum of all the query results as described above.

Explanation for the sample:

There is only one test case. The first query is ``a", and the answer is 3. The second query is ``ap", and the answer is 2. The third query is ``c", and the answer is 0. So the total sum is 3+2+0 = 5.

Sample Input

4 3 apple apple avatar book 1 1 2 2 1 1 1 1 2 2 1 2 2 1 1 1 1 2 10.1 20.1 19.9 20.0 10.2 9.8 9.9 10.0 1 1 2 2 1 1 1 2 2

Sample Output



/* 能力有限,只能是用暴力写的,看大神们都是用字典树写的,时间大约是100+ms 而暴力的却要800+ms,差距还是不小的。有空需要恶补一下。 */ #include #include #include #include #include #define maxn 11111 using namespace std; typedef long long ll; int main() { char s[10010][35]; double d[9]; memset(s,0,sizeof(s)); int n,m; while(scanf("%d%d",&n,&m)!=EOF) { int ans=0; for(int i=0;i=0;v--) { if(d[v]>mi) sum+=b; b*=2; } t[j]=sum; } //cout

点击复制链接 与好友分享!回本站首页
上一篇:hdu 4006 The kth great number (优先队列+STB+最小堆)
下一篇:UVA - 10003Cutting Sticks(递推)

UVALive 3942 Remember the Word


UVALive 6208

UVAlive 2911 Maximum(贪心)

UVALive 4329 Ping pong

uvalive 2322 Wooden Sticks(贪心)

UVALive 2326 Moving Tables 贪心

UVALive 3635 Pie 切糕大师 二分

UVALive 6135 Environment Protect

uvalive 4885 差分约束


UVALive 5029 Encoded Barcodes
ZOJ 3640 Help Me
UVALive 5029 Encoded Barcodes
CF 518C(Anya and
UVALive 5029 Encoded Barcodes
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-02-26 人气:1


Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.043 (s). 10 q(s)